「UVa 11297」Census

发表于 |
字数统计: 741 | 阅读时长 ≈ 4

给定一个$n\times n$的矩阵，支持单点修改，查询子矩阵最大值和子矩阵最小值。

链接

UVa 11297

题解

经典的二维带修RMQ问题。
一个暴力的思想是建$500$棵线段树，对于修改就在对应的线段树上修改，对于查询的时候就一行一行的查询，每一次把答案与之前的答案合并一下就好了qwq。
这样子做的时间复杂度是$O(qn\log n)$，不会TLE，但是跑的极慢，在测的时候跑了$1070$ms，没有树套树跑的快……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=551;
struct SegmentTree{
    ll l,r,minn,maxn;  
};
SegmentTree tree[MAXN][MAXN<<2];
ll size,qcnt,lx,ly,rx,ry,x,y,val,minn,maxn;
char ch;
ll num[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void update(ll dim,ll node)
{
    tree[dim][node].maxn=max(tree[dim][node<<1].maxn,tree[dim][(node<<1)|1].maxn);
    tree[dim][node].minn=min(tree[dim][node<<1].minn,tree[dim][(node<<1)|1].minn);
}
inline void create(ll dim,ll l,ll r,ll node)
{
    tree[dim][node].l=l,tree[dim][node].r=r;
    if(l==r)
    {
        tree[dim][node].minn=tree[dim][node].maxn=num[l];
        return;
    }
    ll mid=(l+r)>>1;
    create(dim,l,mid,node<<1);
    create(dim,mid+1,r,(node<<1)|1);
    update(dim,node);
}
inline void changePoint(ll dim,ll pos,ll val,ll node)
{
    if(tree[dim][node].l==tree[dim][node].r)
    {
        tree[dim][node].minn=tree[dim][node].maxn=val;
        return;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1;
    if(pos<=mid)
    {
        changePoint(dim,pos,val,node<<1);
    }
    else
    {
        changePoint(dim,pos,val,(node<<1)|1);
    }
    update(dim,node);
}
inline ll queryMax(ll dim,ll l,ll r,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        return tree[dim][node].maxn;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1,res=0;
    if(l<=mid)
    {
        res=max(res,queryMax(dim,l,r,node<<1));
    }
    if(r>mid)
    {
        res=max(res,queryMax(dim,l,r,(node<<1)|1));
    }
    return res;
}
inline ll queryMin(ll dim,ll l,ll r,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        return tree[dim][node].minn;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1,res=0x7fffffff;
    if(l<=mid)
    {
        res=min(res,queryMin(dim,l,r,node<<1));
    }
    if(r>mid)
    {
        res=min(res,queryMin(dim,l,r,(node<<1)|1));
    }
    return res;
}
int main()
{
    size=read();
    for(register int i=1;i<=size;i++)
    {
        for(register int j=1;j<=size;j++)
        {
            num[j]=read();
        }
        create(i,1,size,1);
    }
    qcnt=read();
    for(register int i=0;i<qcnt;i++)
    {
        cin>>ch;
        if(ch=='q')
        {
            lx=read(),ly=read(),rx=read(),ry=read();
            maxn=0,minn=0x7fffffff;
            for(register int j=lx;j<=rx;j++)
            {
                maxn=max(maxn,queryMax(j,ly,ry,1));
                minn=min(minn,queryMin(j,ly,ry,1));
            }
            printf("%d %d\n",maxn,minn);
        }
        else
        {
            x=read(),y=read(),val=read();
            changePoint(x,y,val,1);
        }
    }
}