对操作序列分块，每S次暴力重建主席树。
当S=sqrt(n*log(n))时，复杂度为O(m*sqrt(n*log(n)))。
在线的。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 500001
#define M 200001
struct Point{int x,y,z;};
bool operator < (const Point &a,const Point &b){return a.x<b.x;}
Point t[M];
int en;
struct Node
{
int v,lc,rc;
}T[N*20];
int e,root[M],bel[N],re;
int m,n;
int op[M],xa[M],ya[M],xb[M],yb[M],val[M];
void Insert(int pre,int cur,int p,int v,int l,int r)
{
if(l==r)
{
T[cur].v=T[pre].v+v;
return;
}
int m=(l+r>>1);
if(p<=m)
{
T[cur].lc=++e;
T[cur].rc=T[pre].rc;
Insert(T[pre].lc,T[cur].lc,p,v,l,m);
}
else
{
T[cur].rc=++e;
T[cur].lc=T[pre].lc;
Insert(T[pre].rc,T[cur].rc,p,v,m+1,r);
}
T[cur].v=T[T[cur].lc].v+T[T[cur].rc].v;
}
int Query(int pre,int cur,int ql,int qr,int l,int r)
{
if(ql<=l&&r<=qr) return T[cur].v-T[pre].v;
int m=(l+r>>1),res=0;
if(ql<=m) res+=Query(T[pre].lc,T[cur].lc,ql,qr,l,m);
if(m<qr) res+=Query(T[pre].rc,T[cur].rc,ql,qr,m+1,r);
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;;++i)
{
scanf("%d",&op[i]);
if(op[i]==1) scanf("%d%d%d",&xa[i],&ya[i],&val[i]);
else if(op[i]==2)
{
scanf("%d%d%d%d",&xa[i],&ya[i],&xb[i],&yb[i]);
if(xa[i]>xb[i]) swap(xa[i],xb[i]);
if(ya[i]>yb[i]) swap(ya[i],yb[i]);
}
else break;
}
int sz=(int)sqrt((double)n*log2((double)n));
for(int i=1;;++i)
{
if(op[i]==3) break;
else if(op[i]==2)//query
{
int ans=Query(bel[xa[i]-1],bel[xb[i]],ya[i],yb[i],1,n);
for(int j=(i%sz==0||sz==1)?i-sz+1:i/sz*sz+1;j<=i;++j)
if(op[j]==1&&xa[j]>=xa[i]&&xa[j]<=xb[i]&&ya[j]>=ya[i]&&ya[j]<=yb[i])
ans+=val[j];
printf("%d
",ans);
}
if(i%sz==0||sz==1)//Rebuild
{
for(int j=1;j<=e;++j) T[j].v=0;
e=en=re=0;
for(int j=1;j<=i;++j)
if(op[j]==1)
t[++en]=(Point){xa[j],ya[j],val[j]};
sort(t+1,t+en+1);
for(int j=1;j<t[1].x;++j) bel[j]=0;
for(int j=1;j<=en;++j)
{
++re;
root[re]=++e;
if(j==en||t[j].x!=t[j+1].x)
{
bel[t[j].x]=e;
int End=(j==en)?n:t[j+1].x-1;
for(int k=t[j].x+1;k<=End;++k)
bel[k]=e;
}
Insert(root[re-1],root[re],t[j].y,t[j].z,1,n);
}
}
}
return 0;
}