题目大意
维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
题目分析
这道题其实也是三维偏序的变种。
关于三维偏序可以看这两篇文章：传送门1、传送门2。
为什么这道题是三维偏序呢？我们来胡乱分析分析。
首先矩阵可以被拆分为四条线段。
看似是一个二维偏序。
而二维偏序我们可以按照$x$维排序后$y$维用树状数组进行维护。
具体方案是：全部减掉比$x1$小的且在$y$范围内点的权值，全部加上比$x2$小且在$y$范围内点的权值。（前缀和）
然而本题有修改操作，这导致我们暗中添加了一个维度：时间。
因为修改、询问与时间有关，这就将问题变为了一个三维偏序。
我们可以按照$x$维排序然后CDQ分治时间维，用树状数组维护$y$维解决本问题。
代码
本代码使用三维偏序普适框架：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
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=2000005,maxq=200005*4;
int n;
struct BIT {
int c[maxn];
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
void clear(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=0;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;
struct Point {
int x,y,v,id,time,opt;
Point() {}
Point(int _x,int _y,int _v,int _i,int _t,int _o):x(_x),y(_y),v(_v),id(_i),time(_t),opt(_o) {}
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&time<b.time);
}
} q[maxq],tmp[maxq];
int Ans[maxq];
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
int lst=Left,rst=mid+1;
for(int i=Left; i<=Right; i++)
if(q[i].time<=mid)tmp[lst++]=q[i];
else tmp[rst++]=q[i];
for(int i=Left; i<=Right; i++)q[i]=tmp[i];
CDQBinary(Left,mid);
int j=Left;
for(int i=mid+1; i<=Right; i++) {
while(j<=mid&&q[j]<q[i]) {
if(q[j].opt==1)bit.add(q[j].y,q[j].v);
j++;
}
if(q[i].opt==2)Ans[q[i].id]+=q[i].v*bit.sum(q[i].y);
}
for(int i=Left; i<=mid; i++)
if(q[i].opt==1)bit.clear(q[i].y,0);
CDQBinary(mid+1,Right);
merge(q+Left,q+mid+1,q+mid+1,q+Right+1,tmp);
int tot=0;
for(int i=Left; i<=Right; i++)q[i]=tmp[tot++];
}
int k,m=0,opt[maxq],s[maxq],cnt=0;
int main() {
k=Get_Int();
n=Get_Int();
while(true) {
opt[++m]=Get_Int();
if(opt[m]==1) {
int x=Get_Int(),y=Get_Int(),a=Get_Int();
q[++cnt]=Point(x,y,a,m,cnt,1);
} else if(opt[m]==2) {
int x1=Get_Int(),y1=Get_Int(),x2=Get_Int(),y2=Get_Int();
q[++cnt]=Point(x2,y2,1,m,cnt,2);
q[++cnt]=Point(x1-1,y2,-1,m,cnt,2);
q[++cnt]=Point(x2,y1-1,-1,m,cnt,2);
q[++cnt]=Point(x1-1,y1-1,1,m,cnt,2);
s[m]=(x2-x1+1)*(y2-y1+1);
} else break;
}
sort(q+1,q+cnt+1);
CDQBinary(1,cnt);
for(int i=1; i<=m; i++)
if(opt[i]==2)printf("%d\n",Ans[i]+s[i]*k);
return 0;
}
本代码未使用普适框架，代码更简单：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
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=2000005,maxq=200005*4;
int n;
struct BIT {
int c[maxn];
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;
struct Point {
int x,y,v,id,time,opt;
Point() {}
Point(int _x,int _y,int _v,int _i,int _t,int _o):x(_x),y(_y),v(_v),id(_i),time(_t),opt(_o) {}
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&time<b.time);
}
} q[maxq],tmp[maxq];
int Ans[maxq];
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
for(int i=Left; i<=Right; i++)
if(q[i].time<=mid&&q[i].opt==1)bit.add(q[i].y,q[i].v);
else if(q[i].time>mid&&q[i].opt==2)Ans[q[i].id]+=q[i].v*bit.sum(q[i].y);
for(int i=Left; i<=Right; i++)
if(q[i].time<=mid&&q[i].opt==1)bit.add(q[i].y,-q[i].v);
int lst=Left,rst=mid+1;
for(int i=Left; i<=Right; i++)
if(q[i].time<=mid)tmp[lst++]=q[i];
else tmp[rst++]=q[i];
for(int i=Left; i<=Right; i++)q[i]=tmp[i];
CDQBinary(Left,mid);
CDQBinary(mid+1,Right);
}
int k,m=0,opt[maxq],s[maxq],cnt=0;
int main() {
k=Get_Int();
n=Get_Int();
while(true) {
opt[++m]=Get_Int();
if(opt[m]==1) {
int x=Get_Int(),y=Get_Int(),a=Get_Int();
q[++cnt]=Point(x,y,a,m,cnt,1);
} else if(opt[m]==2) {
int x1=Get_Int(),y1=Get_Int(),x2=Get_Int(),y2=Get_Int();
q[++cnt]=Point(x2,y2,1,m,cnt,2);
q[++cnt]=Point(x1-1,y2,-1,m,cnt,2);
q[++cnt]=Point(x2,y1-1,-1,m,cnt,2);
q[++cnt]=Point(x1-1,y1-1,1,m,cnt,2);
s[m]=(x2-x1+1)*(y2-y1+1);
} else break;
}
sort(q+1,q+cnt+1);
CDQBinary(1,cnt);
for(int i=1; i<=m; i++)
if(opt[i]==2)printf("%d\n",Ans[i]+s[i]*k);
return 0;
}
