bzoj1251 -- splay

splay模板题。

用splay维护序列，令splay的中序遍历为这个序列，则在处理[l,r]时，先将l-1旋转到根，再将r+1旋转到根的右子树，那么根的右子树的左子树就是[l,r]了。

代码：

1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 #define N 50010
  6 #define INF 2147483647
  7 bool b[N];
  8 int i,j,k,m,n,c[N],s[N],a[N],Rt,p[N],ch[N][2],f[N],x,y,z;
  9 inline int Get(int x){return ch[f[x]][1]==x;}
 10 inline int _Max(int x,int y){return x>y?x:y;}
 11 inline void Up(int x){
 12     c[x]=_Max(a[x],_Max(c[ch[x][0]],c[ch[x][1]]));
 13     s[x]=s[ch[x][0]]+s[ch[x][1]]+1;
 14 }
 15 inline void Down(int x){
 16     if(!x)return;
 17     if(p[x]){
 18         if(ch[x][0])p[ch[x][0]]+=p[x],c[ch[x][0]]+=p[x],a[ch[x][0]]+=p[x];
 19         if(ch[x][1])p[ch[x][1]]+=p[x],c[ch[x][1]]+=p[x],a[ch[x][1]]+=p[x];
 20         p[x]=0;
 21     }
 22     if(b[x]){
 23         int t=ch[x][0];ch[x][0]=ch[x][1];ch[x][1]=t;
 24         if(ch[x][0])b[ch[x][0]]^=1;
 25         if(ch[x][1])b[ch[x][1]]^=1;
 26         b[x]=0;
 27     }
 28 }
 29 inline void Rotate(int x){
 30     int y=f[x];bool d=Get(x);
 31     ch[f[y]][Get(y)]=x;
 32     f[x]=f[y];
 33     ch[y][d]=ch[x][d^1];
 34     f[ch[y][d]]=y;
 35     ch[x][d^1]=y;
 36     f[y]=x;Up(y);
 37 }
 38 inline void Splay(int x,int g){
 39     while(f[x]!=g){
 40         Down(f[f[x]]);Down(f[x]);Down(x);
 41         if(f[f[x]]){
 42             if(f[f[x]]==g){Rotate(x);break;}
 43             Rotate(Get(x)==Get(f[x])?f[x]:x);
 44         }
 45         Rotate(x);
 46     }
 47     Up(x);
 48     if(!g)Rt=x;
 49 }
 50 inline int Search(int x){
 51     int u=Rt;
 52     Down(u);
 53     while(s[ch[u][0]]!=x){
 54         if(s[ch[u][0]]>x)u=ch[u][0];else x-=s[ch[u][0]]+1,u=ch[u][1];
 55         Down(u);
 56     }
 57     return u;
 58 }
 59 inline int Build(int l,int r){
 60     if(l>r)return 0;
 61     if(l==r)return l;
 62     int Mid=l+r>>1;
 63     ch[Mid][0]=Build(l,Mid-1);
 64     ch[Mid][1]=Build(Mid+1,r);
 65     s[Mid]=s[ch[Mid][0]]+s[ch[Mid][1]]+1;
 66     f[ch[Mid][0]]=f[ch[Mid][1]]=Mid;
 67     Up(Mid);
 68     return Mid;
 69 }
 70 inline void Update(int l,int r,int x){
 71     int u=Search(l-1),v=Search(r+1);
 72     Splay(u,0);Splay(v,u);
 73     c[ch[v][0]]+=x;
 74     p[ch[v][0]]+=x;
 75     a[ch[v][0]]+=x;
 76 }
 77 inline void Reverse(int l,int r){
 78     int u=Search(l-1),v=Search(r+1);
 79     Splay(u,0);Splay(v,u);
 80     b[ch[v][0]]^=1;
 81 }
 82 inline int Query(int l,int r){
 83     int u=Search(l-1),v=Search(r+1);
 84     Splay(u,0);Splay(v,u);
 85     return c[ch[v][0]];
 86 }
 87 inline void Init(){
 88     for(int i=1;i<=n+2;i++)s[i]=1;
 89     c[0]=a[0]=-INF;c[1]=a[1]=-INF;
 90     c[n+2]=a[n+2]=-INF;
 91     Rt=Build(1,n+2);
 92     ch[0][0]=Rt;
 93 }
 94 int main()
 95 {
 96     scanf("%d%d",&n,&m);
 97     Init();
 98     while(m--){
 99         scanf("%d",&k);
100         if(k==1)scanf("%d%d%d",&x,&y,&z),Update(x,y,z);else{
101             scanf("%d%d",&x,&y);
102             if(k==2)Reverse(x,y);else printf("%d\n",Query(x,y));
103         }
104     }
105     return 0;
106 }

bzoj1251