BZOJ1176 Mokia

题面

传送门 维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000. 操作一为增加,操作二为查询

题解

一看w2×106,M1.6×105,Q1×104w\le 2\times 10^6,M\le 1.6\times 10^5,Q \le 1\times 10^4就知道不能直接二维线段树或二维数状数组爆搞了。空间O(w2)O(w^2)就算离散化也是O((M+4Q)2)O((M+4Q)^2)

我们把每一个操作二拆成四个查询操作,每个查询操作(x,y)(x,y)代表查询i=1xj=1ywi,j\sum_{i=1}^x\sum_{j=1}^yw_{i,j},其中wi,jw_{i,j}表示(i,j)(i,j)格子的权值。

设按顺序第i个操作的x坐标为XiX_i,y坐标为YiY_i(修改的格子位置或查询的(x,y))

发现修改操作a对查询操作b有影响当且仅当a<b,XaXb,YaYba<b,X_a \le X_b,Y_a \le Y_b全部满足。

这就是个三维偏序啊。

直接来一波CDQ分治

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
/*
Author: CNYALI_LK
LANG: C++
PROG: 1176.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int w=0,base=1;
char c;
while(!isdigit(c=getchar())){if(c=='-')base=-base;}
while(isdigit(c)){w=w*10+c-'0';c=getchar();}
return w*base;
}
int s,w;
struct cz{
int a,b,c,d,tim,ans;
cz (int t=0,int u=0,int o=0,int i=0,int p=0){
a=u;b=o;c=i;d=p;tim=t;
ans=0;
}
};
cz a[233333],b[233333];
int tp[233333];
int cx[2333333];
int c[233333],ans[233333];
#define lowbit(x) (x&(-x))
void add(int x,int y){
while(x<=w){
c[x]+=y;
x+=lowbit(x);
}
}
int sum(int x){
int cnt=0;
while(x){
cnt+=c[x];
x^=lowbit(x);
}
return cnt;
}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int s1=l,s2=mid+1,t=l-1;
while(s2<=r){
while(s1<=mid&&a[s1].b<=a[s2].b){
b[++t]=a[s1];
if(!tp[a[s1].tim])add(a[s1].c,a[s1].d);
++s1;
}
if(tp[a[s2].tim])a[s2].ans+=sum(a[s2].c);
b[++t]=a[s2];
++s2;
}
for(int i=l;i<s1;++i)if(!tp[a[i].tim])add(a[i].c,-a[i].d);
while(s1<=mid){b[++t]=a[s1];++s1;}
for(int i=l;i<=r;++i)a[i]=b[i];
}
int main(){
#ifdef cnyali_lk
freopen("1176.in","r",stdin);
freopen("1176.out","w",stdout);
#endif
int t,al,b,c,d,n=0,m=0,l=0;
s=read();w=read();
while((t=read())^3){
al=read();b=read();c=read();
if(t==1){
a[++n]=cz(++m,t,al,b,c);
cx[b]=1;
tp[m]=0;
}
else{
d=read();
a[++n]=cz(++m,t,c,d,1);
a[++n]=cz(m,t,al-1,b-1,1);
a[++n]=cz(m,t,c,b-1,-1);
a[++n]=cz(m,t,al-1,d,-1);
cx[d]=cx[b-1]=1;
tp[m]=1;
}
}
for(int i=0;i<=w;++i)if(cx[i])cx[i]=++l;
w=l;
for(int i=1;i<=n;++i)a[i].c=cx[a[i].c];
cdq(1,n);
// for(int i=1;i<=n;++i)printf("%d(%d,%d,%d,%d) -> %d\n",a[i].tim,a[i].a,a[i].b,a[i].c,a[i].d,a[i].d*a[i].ans);
for(int i=1;i<=n;++i)ans[a[i].tim]+=a[i].d*(a[i].ans+a[i].b*a[i].c*s);
for(int i=1;i<=m;++i)if(tp[i])printf("%d\n",ans[i]);
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解
|

博客使用Disqus作为评论系统