线段树的题目，拿来练第一道splay维护区间。
像这种基本的操作修改查询，我现在应该能在20分钟手写好splay再用10分钟调试，基本上不靠模版30分钟应该能出。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define key_val ch[ch[rt][1]][0] #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100010; const int INF=1e9+10; int n,m; int a[maxn]; int L,R,c;char op[5]; int key[maxn],pre[maxn],sz[maxn],ch[maxn][2],rt,tot1; int s[maxn],tot2; int val[maxn]; ll add[maxn],sum[maxn]; void newnode(int &r,int fa,int v) { if(tot2) r=s[tot2--]; else r=++tot1; key[r]=0; add[r]=sum[r]=0; val[r]=v; sz[r]=1; MS0(ch[r]); pre[r]=fa; } void down(int r) { if(add[r]){ val[r]+=add[r]; add[ch[r][0]]+=add[r]; add[ch[r][1]]+=add[r]; sum[ch[r][0]]+=add[r]*sz[ch[r][0]]; sum[ch[r][1]]+=add[r]*sz[ch[r][1]]; add[r]=0; } } void up(int r) { sz[r]=sz[ch[r][0]]+sz[ch[r][1]]+1; sum[r]=sum[ch[r][0]]+sum[ch[r][1]]+val[r]; } void rot(int x,int kind) { int y=pre[x]; down(x);down(y); ch[y][kind^1]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; up(y); } void splay(int x,int goal) { down(x); while(pre[x]!=goal){ if(pre[pre[x]]==goal) rot(x,ch[pre[x]][0]==x); else{ int y=pre[x],z=pre[y]; int kind=ch[y][0]==x,one=0; if(ch[y][0]==x&&ch[z][0]==y) one=1; if(ch[y][1]==x&&ch[z][1]==y) one=1; if(one) rot(y,kind),rot(x,kind); else rot(x,kind),rot(x,kind^1); } } if(goal==0) rt=x; up(x); } void rto(int k,int goal) { int r=rt; down(r); while(sz[ch[r][0]]!=k){ if(k<sz[ch[r][0]]) r=ch[r][0]; else k-=sz[ch[r][0]]+1,r=ch[r][1]; down(r); } splay(r,goal); } ll query(int l,int r) { rto(l-1,0); rto(r+1,rt); return sum[key_val]; } void update(int l,int r,int c) { rto(l-1,0); rto(r+1,rt); add[key_val]+=c; sum[key_val]+=c*sz[key_val]; } void build(int &x,int l,int r,int fa) { if(l>r) return; int m=(l+r)>>1; newnode(x,fa,a[m]); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); up(x); } void Init() { tot1=rt=0; key[0]=pre[0]=sz[0]=ch[0][0]=ch[0][1]=0; add[0]=sum[0]=0; newnode(rt,0,-INF); newnode(ch[rt][1],rt,INF); sz[rt]=2; build(key_val,1,n,ch[rt][1]); up(ch[rt][1]); up(rt); } int main() { freopen("in.txt","r",stdin); while(cin>>n>>m){ REP(i,1,n) scanf("%d",&a[i]); Init(); while(m--){ scanf("%s",op); if(op[0]=='Q'){ scanf("%d%d",&L,&R); printf("%I64d ",query(L,R)); } else{ scanf("%d%d%d",&L,&R,&c); update(L,R,c); } } } return 0; }
更新。。。上面的rto写得有问题。。。。虽然不知道在poj为什么过了。。。但是下面这样写才是正解。。。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define key_val ch[ch[rt][1]][0] #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100010; const int INF=1e9+10; int n,m; int a[maxn]; int L,R,c;char op[5]; int key[maxn],pre[maxn],sz[maxn],ch[maxn][2],rt,tot1; int s[maxn],tot2; int val[maxn]; ll add[maxn],sum[maxn]; void newnode(int &r,int fa,int v) { if(tot2) r=s[tot2--]; else r=++tot1; key[r]=0; add[r]=sum[r]=0; val[r]=v; sz[r]=1; MS0(ch[r]); pre[r]=fa; } void down(int r) { if(add[r]){ val[r]+=add[r]; add[ch[r][0]]+=add[r]; add[ch[r][1]]+=add[r]; sum[ch[r][0]]+=add[r]*sz[ch[r][0]]; sum[ch[r][1]]+=add[r]*sz[ch[r][1]]; add[r]=0; } } void up(int r) { sz[r]=sz[ch[r][0]]+sz[ch[r][1]]+1; sum[r]=sum[ch[r][0]]+sum[ch[r][1]]+val[r]; } void rot(int x,int kind) { int y=pre[x]; down(x);down(y); ch[y][kind^1]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; up(y); } void splay(int x,int goal) { down(x); while(pre[x]!=goal){ if(pre[pre[x]]==goal) rot(x,ch[pre[x]][0]==x); else{ int y=pre[x],z=pre[y]; int kind=ch[y][0]==x,one=0; if(ch[y][0]==x&&ch[z][0]==y) one=1; if(ch[y][1]==x&&ch[z][1]==y) one=1; if(one) rot(y,kind),rot(x,kind); else rot(x,kind),rot(x,kind^1); } } if(goal==0) rt=x; up(x); } void rto(int k,int goal) { int r=rt;k++; down(r); while(sz[ch[r][0]]+1!=k){ if(k<sz[ch[r][0]]+1) r=ch[r][0]; else k-=sz[ch[r][0]]+1,r=ch[r][1]; down(r); } splay(r,goal); } ll query(int l,int r) { rto(l-1,0); rto(r+1,rt); return sum[key_val]; } void update(int l,int r,int c) { rto(l-1,0); rto(r+1,rt); add[key_val]+=c; sum[key_val]+=c*sz[key_val]; } void build(int &x,int l,int r,int fa) { if(l>r) return; int m=(l+r)>>1; newnode(x,fa,a[m]); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); up(x); } void Init() { tot1=rt=0; key[0]=pre[0]=sz[0]=ch[0][0]=ch[0][1]=0; add[0]=sum[0]=0; newnode(rt,0,-INF); newnode(ch[rt][1],rt,INF); sz[rt]=2; build(key_val,1,n,ch[rt][1]); up(ch[rt][1]); up(rt); } int main() { //freopen("in.txt","r",stdin); while(cin>>n>>m){ REP(i,1,n) scanf("%d",&a[i]); Init(); while(m--){ scanf("%s",op); if(op[0]=='Q'){ scanf("%d%d",&L,&R); printf("%I64d ",query(L,R)); } else{ scanf("%d%d%d",&L,&R,&c); update(L,R,c); } } } return 0; }