树状数组 · ooliver

树状数组 P3605 [USACO17JAN] Promotion Counting P 很模板的一道树上树状数组，计算遍历子树后的变化就可以了，代码： #include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m; vector g[N]; int a[N],tr[N],cnt[N],p[N]; void change(int x,int k){ while(x>n; for(int i=1;i>p[i]; a[i]=p[i]; } sort(p+1,p+1+n); for(int i=1;i>u; g[u].push_back(i); } dfs1(1); for(int i=1;i `#include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m; vectorint> g[N]; int a[N],tr[N],cnt[N],p[N]; void change(int x,int k){ while(x tr[x]+=k; x+=lowbit(x); } } int query(int x){ int t=0; while(x){ t+=tr[x]; x-=lowbit(x); } return t; } void dfs1(int x){ cnt[x]-=(query(n)-query(a[x])); for(int i=0;ig[x].size();i++) dfs1(g[x][i]); cnt[x]+=(query(n)-query(a[x])); change(a[x],1); } signed main(){ cin>>n; for(int i=1;i cin>>p[i]; a[i]=p[i]; } sort(p+1,p+1+n); for(int i=1;ia[i]=lower_bound(p+1,p+1+n,a[i])-p; for(int i=2;i int u; cin>>u; g[u].push_back(i); } dfs1(1); for(int i=1;icnt[i] return 0; }` P1972 [SDOI2009] HH 的项链考虑离线处理，对每次查询按右端点大小排序。然后从左到右枚举每个贝壳，如果之前出现了相同的贝壳种类，由于右端点排序的性质，当前贝壳一定会查询到，所以给当前贝壳加一，给之前的贝壳减一，来消除区间求和找到它的影响即可。代码： #include using namespace std; #define lowbit(x) x&-x const int N=1e6+5; int n,m; int tr[N],a[N],last[N],ans[N]; struct ask{ int l,r,id; }q[N]; void change(int x,int k){ while(x>n; for(int i=1;i>a[i]; cin>>m; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+1+m,cmp); int l=0; for(int i=1;i `#include using namespace std; #define lowbit(x) x&-x const int N=1e6+5; int n,m; int tr[N],a[N],last[N],ans[N]; struct ask{ int l,r,id; }q[N]; void change(int x,int k){ while(x tr[x]+=k; x+=lowbit(x); } } int query(int x){ int t=0; while(x){ t+=tr[x]; x-=lowbit(x); } return t; } bool cmp(ask x,ask y){return x.ry.r;} signed main(){ cin>>n; for(int i=1;i>a[i]; cin>>m; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+1+m,cmp); int l=0; for(int i=1;i while(lq[i].r){ l++; if(last[a[l]]) change(last[a[l]],-1); last[a[l]]=l; change(l,1); } ans[q[i].id]=query(q[i].r)-query(q[i].l-1); } for(int i=1;ians[i] return 0; }` P4113 [HEOI2012] 采花思路和上一题很相似，只不过题目改成了区间内同颜色数量大于 2 的颜色个数。一样的离线+排序，发现从左往右找找到第二个同颜色的点才会对答案有贡献，所以对于当前点，上一个同颜色的点 +1，上上一个同颜色的点 -1 消除影响即可。代码： #include using namespace std; #define lowbit(x) x&-x const int N=2e6+5; int n,m,c; int tr[N],a[N],last[N],last2[N],ans[N]; struct ask{ int l,r,id; }q[N]; void change(int x,int k){ while(x>n>>c>>m; for(int i=1;i>a[i]; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+1+m,cmp); int l=0; for(int i=1;i `#include using namespace std; #define lowbit(x) x&-x const int N=2e6+5; int n,m,c; int tr[N],a[N],last[N],last2[N],ans[N]; struct ask{ int l,r,id; }q[N]; void change(int x,int k){ while(x tr[x]+=k; x+=lowbit(x); } } int query(int x){ int t=0; while(x){ t+=tr[x]; x-=lowbit(x); } return t; } bool cmp(ask x,ask y){return x.ry.r;} signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>c>>m; for(int i=1;i>a[i]; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+1+m,cmp); int l=0; for(int i=1;i while(lq[i].r){ l++; if(!last[a[l]]){ last[a[l]]=l; continue; } change(last[a[l]],1); if(last2[a[l]]) change(last2[a[l]],-1); last2[a[l]]=last[a[l]],last[a[l]]=l; } ans[q[i].id]=query(q[i].r)-query(q[i].l-1); } for(int i=1;ians[i]"\n"; return 0; }` P4054 [JSOI2009] 计数问题二维树状数组模板题，建 c 个树状数组即可，代码： #include using namespace std; #define lowbit(x) x&-x const int N=105; int n,m,q; int tr[N][N*3][N*3],a[N*3][N*3]; void change(int c,int x,int y,int k){ for(int i=x;i=1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) t+=tr[c][i][j]; return t; } signed main(){ cin>>n>>m; for(int i=1;i>a[i][j]; change(a[i][j],i,j,1); } cin>>q; while(q--){ int op; cin>>op; if(op==1){ int x,y,c; cin>>x>>y>>c; change(a[x][y],x,y,-1); change(a[x][y]=c,x,y,1); } else{ int x1,x2,y1,y2,c; cin>>x1>>x2>>y1>>y2>>c; cout `#include using namespace std; #define lowbit(x) x&-x const int N=105; int n,m,q; int tr[N][N*3][N*3],a[N*3][N*3]; void change(int c,int x,int y,int k){ for(int i=x;ilowbit(i)) for(int j=y;jlowbit(j)) tr[c][i][j]+=k; } int query(int c,int x,int y){ int t=0; for(int i=x;i>=1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) t+=tr[c][i][j]; return t; } signed main(){ cin>>n>>m; for(int i=1;ifor(int j=1;j cin>>a[i][j]; change(a[i][j],i,j,1); } cin>>q; while(q--){ int op; cin>>op; if(op==1){ int x,y,c; cin>>x>>y>>c; change(a[x][y],x,y,-1); change(a[x][y]=c,x,y,1); } else{ int x1,x2,y1,y2,c; cin>>x1>>x2>>y1>>y2>>c; coutquery(c,x2,y2)-query(c,x1-1,y2)-query(c,x2,y1-1)+query(c,x1-1,y1-1)"\n"; } } return 0; }` P4514 上帝造题的七分钟这题需要直接对二维差分数组进行前缀和，设 aa 为原数组，dd 为差分数组，sumsum 为前缀和数组，有： a[x][y]=∑i=1x∑j=1yd[i][j]sum[x][y]=∑i=1x∑j=1ya[i][j]\begin{aligned} a[x][y]=\sum^{x}{i=1}\sum^{y}{j=1}d[i][j] \ sum[x][y]=\sum^{x}{i=1}\sum^{y}{j=1}a[i][j] \ \end{aligned} sum[x][y]=∑i=1x∑j=1y∑k=1i∑l=1jd[k][l]=∑i=1x∑j=1y(x−i+1)(y−j+1)d[i][j]=∑i=1x∑j=1yi⋅j⋅d[i][j]−(y+1)∑i=1x∑j=1yi⋅d[i][j]−(x+1)∑i=1x∑j=1yj⋅d[i][j]+(x+1)(y+1)∑i=1x∑j=1yd[i][j] \begin{aligned} &sum[x][y] \ =&\sum^{x}{i=1}\sum^{y}{j=1}\sum^{i}{k=1}\sum^{j}{l=1}d[k][l] \ =&\sum^{x}{i=1}\sum^{y}{j=1}(x-i+1)(y-j+1)d[i][j] \ =&\sum^{x}{i=1}\sum^{y}{j=1}i\cdot j\cdot d[i][j] -(y+1)\sum^{x}{i=1}\sum^{y}{j=1}i\cdot d[i][j] -(x+1)\sum^{x}{i=1}\sum^{y}{j=1}j\cdot d[i][j] +(x+1)(y+1)\sum^{x}{i=1}\sum^{y}{j=1}d[i][j] \end{aligned} 然后维护四个二维树状数组即可。 #include using namespace std; #define lowbit(x) x&-x const int N=2050; int n,m; char op; int a,b,c,d,delta; int tr1[N][N],tri[N][N],trj[N][N],trij[N][N]; void add(int x,int y,int k){ for(int i=x;i0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) res+=(x+1)*(y+1)*tr1[i][j]-(x+1)*trj[i][j]-(y+1)*tri[i][j]+trij[i][j]; return res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>op){ if(op=='X') cin>>n>>m; else if(op=='L'){ cin>>a>>b>>c>>d>>delta; add(a,b,delta),add(a,d+1,-delta),add(c+1,b,-delta),add(c+1,d+1,delta); } else if(op=='k'){ cin>>a>>b>>c>>d; cout `#include using namespace std; #define lowbit(x) x&-x const int N=2050; int n,m; char op; int a,b,c,d,delta; int tr1[N][N],tri[N][N],trj[N][N],trij[N][N]; void add(int x,int y,int k){ for(int i=x;ilowbit(i)) for(int j=y;jlowbit(j)) tr1[i][j]+=k,tri[i][j]+=k*x,trj[i][j]+=k*y,trij[i][j]+=k*x*y; } int check(int x,int y){ int res=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) res+=(x+1)*(y+1)*tr1[i][j]-(x+1)*trj[i][j]-(y+1)*tri[i][j]+trij[i][j]; return res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>op){ if(op=='X') cin>>n>>m; else if(op=='L'){ cin>>a>>b>>c>>d>>delta; add(a,b,delta),add(a,d+1,-delta),add(c+1,b,-delta),add(c+1,d+1,delta); } else if(op=='k'){ cin>>a>>b>>c>>d; coutcheck(c,d)-check(a-1,d)-check(c,b-1)+check(a-1,b-1)"\n"; } else break; } return 0; } `