今天突然想写个树套树爽一爽（1810ms）
写的是树状数组套线段树（动态开节点）
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
int sum[maxnode],ls[maxnode],rs[maxnode],ToT;
void update(int& y,int l,int r,int& pos,int& v)
{
if(!y) y=++ToT;
sum[y]+=v;if(l==r) return;
int mid=l+r>>;
if(pos<=mid) update(ls[y],l,mid,pos,v);
else update(rs[y],mid+,r,pos,v);
}
int ans;
void query(int& y,int l,int r,int& ql,int& qr)
{
if(ql<=l&&r<=qr) {ans+=sum[y];return;}
if(!y) return;
int mid=l+r>>;
if(ql<=mid) query(ls[y],l,mid,ql,qr);
if(qr>mid) query(rs[y],mid+,r,ql,qr);
}
int n,root[maxn],lastans;
void add(int x,int y,int v)
{
for(;x<=;x+=x&-x) update(root[x],,,y,v);
}
int query(int x,int ql,int qr)
{
ans=;
for(;x;x-=x&-x) query(root[x],,,ql,qr);
return ans;
}
int tp[],x1[],x2[],y1[],y2[],v[];
int tmp[],tot;
int main()
{
read();n=read();int m;
for(int i=;;i++)
{
tp[i]=read();
if(tp[i]==) {m=i;break;}
else if(tp[i]==) x1[i]=read(),y1[i]=read(),v[i]=read();
else x1[i]=read(),y1[i]=read(),x2[i]=read(),y2[i]=read(),tmp[++tot]=x2[i];
tmp[++tot]=x1[i];
}
sort(tmp+,tmp+tot+);
for(int i=;i<=m;i++) x1[i]=lower_bound(tmp+,tmp+tot+,x1[i])-tmp,x2[i]=lower_bound(tmp+,tmp+tot+,x2[i])-tmp;
tot=;for(int i=;i<=m;i++) tmp[++tot]=y1[i],tmp[++tot]=y2[i];sort(tmp+,tmp+tot+);
for(int i=;i<=m;i++) y1[i]=lower_bound(tmp+,tmp+tot+,y1[i])-tmp,y2[i]=lower_bound(tmp+,tmp+tot+,y2[i])-tmp;
for(int i=;i<=m;i++)
{
if(tp[i]==) break;
else if(tp[i]==) add(x1[i],y1[i],v[i]);
else printf("%d\n",query(x2[i],y1[i],y2[i])-query(x1[i]-,y1[i],y2[i]));
}
return ;
}
竟然还要离散TAT(maxnode开到2*10^8会RE，开到2.5*10^8会MLE)
这是之前写的CDQ分治（328ms）
代码难看勿喷
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
char ch;int sig;
inline void read(int& x)
{
ch=getchar(); sig=; x=;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') sig=-,ch=getchar();
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
x*=sig;
}
const int maxn=;
struct Query
{
int t,x,y,v,id;
bool operator < (const Query& ths) const
{
return x<ths.x||(x==ths.x&&y<ths.y)||(x==ths.x&&y==ths.y&&t<ths.t);
}
}A[maxn],t1[maxn];
int ans[];
int w,s;
int C[];
void update(int x,int v)
{
for(;x<=w;x+=x&-x) C[x]+=v;
}
int query(int x)
{
int ret=;
for(;x;x-=x&-x) ret+=C[x];
return ret;
}
void solve(int L,int R)
{
if(L==R) return;
int m1=,m2=,M=L+R>>;
solve(L,M);
solve(M+,R);
for(int i=L;i<=M;i++) if(A[i].t==) t1[m1++]=A[i];
if(!m1) return;
m2=m1;
for(int i=M+;i<=R;i++) if(A[i].t==) t1[m2++]=A[i];
if(m2==m1) return;
sort(t1,t1+m2);
for(int i=;i<m2;i++)
{
if(t1[i].t==) update(t1[i].y,t1[i].v);
else ans[t1[i].id]+=t1[i].v*query(t1[i].y);
}
for(int i=;i<m2;i++) if(t1[i].t==) update(t1[i].y,-t1[i].v);
}
int main()
{
scanf("%d%d",&s,&w);
int x1,y1,x2,y2,t,a,tot=,n=;
while()
{
read(t);
if(t==) break;
if(t==)
{
read(x1); read(y1); read(a);
A[++tot]=(Query){t,x1,y1,a,};
}
else
{
read(x1); read(y1); read(x2); read(y2);
ans[++n]=(x2-x1+)*(y2-y1+)*s;
A[++tot]=(Query){t,x1-,y1-,,n};
A[++tot]=(Query){t,x2,y2,,n};
A[++tot]=(Query){t,x1-,y2,-,n};
A[++tot]=(Query){t,x2,y1-,-,n};
}
}
solve(,tot);
for(int i=;i<=n;i++) printf("%d\n",ans[i]);
return ;
}
YY了一个k-d树（625ms）
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int lc[maxn],rc[maxn],x[maxn],y[maxn],mxx[maxn],mxy[maxn],mnx[maxn],mny[maxn],sum[maxn];
void maintain(int r)
{
mxx[r]=max(x[r],max(mxx[lc[r]],mxx[rc[r]]));
mnx[r]=min(x[r],min(mnx[lc[r]],mnx[rc[r]]));
mxy[r]=max(y[r],max(mxy[lc[r]],mxy[rc[r]]));
mny[r]=min(y[r],min(mny[lc[r]],mny[rc[r]]));
}
int x1,y1,x2,y2,v,ToT;
void insert(int& r,int d)
{
if(!r) r=++ToT,x[r]=mxx[r]=mnx[r]=x1,y[r]=mny[r]=mxy[r]=y1;
sum[r]+=v;
if(x[r]==x1&&y[r]==y1) return;
if(!d)
{
if(x1<=x[r]) insert(lc[r],d^);
else insert(rc[r],d^);
}
else
{
if(y1<=y[r]) insert(lc[r],d^);
else insert(rc[r],d^);
}
maintain(r);
}
int query(int r,int d)
{
if(!r) return ;
if(mnx[r]>=x1&&mxx[r]<=x2&&mny[r]>=y1&&mxy[r]<=y2) return sum[r];
int ret=;
if(x[r]<=x2&&x[r]>=x1&&y[r]<=y2&&y[r]>=y1) ret+=sum[r]-sum[lc[r]]-sum[rc[r]];
if(!d)
{
if(x1<=x[r]) ret+=query(lc[r],d^);
if(x2>x[r]) ret+=query(rc[r],d^);
}
else
{
if(y1<=y[r]) ret+=query(lc[r],d^);
if(y2>y[r]) ret+=query(rc[r],d^);
}
return ret;
}
int main()
{
read();int n=read(),root=;
mxx[]=mxy[]=-1e9;mnx[]=mny[]=1e9;
for(;;)
{
int tp=read();
if(tp==) break;
else if(tp==)
{
x1=read();y1=read();v=read();
insert(root,);
}
else
{
x1=read();y1=read();x2=read();y2=read();
printf("%d\n",query(root,));
}
}
return ;
}
最后写了写树状数组套Treap（1919ms）
#include<cstdio>
#include<cctype>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
struct Node
{
Node* ch[];
int r,s,v,v2,sum;
void maintain() {s=ch[]->s+ch[]->s+;sum=v2+ch[]->sum+ch[]->sum;}
}nodes[maxn],*null=&nodes[];
int ToT;
void rotate(Node* &o,int d)
{
Node* k=o->ch[d^];o->ch[d^]=k->ch[d];k->ch[d]=o;
o->maintain();k->maintain();o=k;
}
void insert(Node* &o,int v,int v2)
{
if(o==null)
{
o=&nodes[++ToT];
o->r=rand();o->s=;o->v=v;o->v2=o->sum=v2;
o->ch[]=o->ch[]=null;
}
else
{
int d=v>o->v;
insert(o->ch[d],v,v2);
if(o->ch[d]->r>o->r) rotate(o,d^);
else o->maintain();
}
}
int query(Node* &o,int v)
{
if(o==null) return ;
if(v<=o->v) return query(o->ch[],v);
return o->ch[]->sum+o->v2+query(o->ch[],v);
}
Node* root[maxn];int n;
void add(int x,int y,int v)
{
for(;x<=n;x+=x&-x) insert(root[x],y,v);
}
int query(int x,int y1,int y2)
{
int ret=;
for(;x;x-=x&-x) ret+=query(root[x],y2+)-query(root[x],y1);
return ret;
}
int main()
{
srand(time());null->s=null->sum=;
read();n=read();
for(int i=;i<=n;i++) root[i]=null;
for(;;)
{
int tp=read();
if(tp==) break;
if(tp==)
{
int x=read(),y=read(),v=read();
add(x,y,v);
}
else
{
int x1=read(),y1=read(),x2=read(),y2=read();
printf("%d\n",query(x2,y1,y2)-query(x1-,y1,y2));
}
}
return ;
}