Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

1251 序列终结者

大意:
维护一个数列 支持翻转[l,r],给[l,r]加上一个delta,求[l,r]的最大值

做法:
splay乱搞搞..
只需要知道3点:
1.整棵树的中序遍历序列便是当前序列。
2.翻转一个区间等价于交换子树中所有节点的左子树和右子树。
3.传懒标记要注意在正确的时候下传,以及要将新改变的节点splay到根。

  1 #include <cstdio>
  2 #include <cstring>
  3 struct Tsplay
  4 {
  5     #define Lch(t)    T[t].l
  6     #define Rch(t)    T[t].r
  7     #define Par(t)    T[t].p
  8     #define Max(t)    T[t].max
  9     #define Delt(t)    T[t].delt
 10     #define Val(t)    T[t].val
 11     #define Rev(t)    T[t].rev
 12     #define Size(t)    T[t].size
 13     int l,r,p,size;
 14     int delt,max,val;
 15     bool rev; 
 16 }    T[50005];
 17 int Stk[50005],root,Root;
 18 int N,M,cmd,x,y,delt;
 19 inline void Down(int t)
 20 {
 21     if (Delt(t))
 22     {
 23         if (Lch(t)) Delt(Lch(t))+=Delt(t),Val(Lch(t))+=Delt(t),Max(Lch(t))+=Delt(t);
 24         if (Rch(t))    Delt(Rch(t))+=Delt(t),Val(Rch(t))+=Delt(t),Max(Rch(t))+=Delt(t);
 25         Delt(t)=0;
 26     }
 27     if (Rev(t))
 28     {
 29         int tmp=Lch(t);Lch(t)=Rch(t);Rch(t)=tmp;
 30         Rev(Lch(t))^=1,Rev(Rch(t))^=1,Rev(t)=0;
 31     }
 32 }
 33 inline void Tupdate(int t)
 34 {
 35     Size(t)=1,Max(t)=Val(t);
 36     if (Lch(t))
 37     {
 38         if (Max(Lch(t))>Max(t))    Max(t)=Max(Lch(t));
 39         Size(t)+=Size(Lch(t));
 40     }
 41     if (Rch(t))
 42     {
 43         if (Max(Rch(t))>Max(t))    Max(t)=Max(Rch(t));
 44         Size(t)+=Size(Rch(t));
 45     }
 46 }
 47 inline void zig(int x)
 48 {
 49     int y=Par(x),z=Par(y);
 50     Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
 51     if (Lch(z)==y)    Lch(z)=x;
 52     else    Rch(z)=x;
 53     Par(x)=z,Par(y)=x;
 54     Tupdate(y);
 55 }
 56 inline void zag(int x)
 57 {
 58     int y=Par(x),z=Par(y);
 59     Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
 60     if (Lch(z)==y)    Lch(z)=x;
 61     else    Rch(z)=x;
 62     Par(x)=z,Par(y)=x;
 63     Tupdate(y);
 64 }
 65 inline void splay(int &root,int x)
 66 {
 67     Stk[++Stk[0]]=x;
 68     for (int u=x;Par(u);u=Par(u))
 69         Stk[++Stk[0]]=Par(u);
 70     for (;Stk[0];--Stk[0])
 71         Down(Stk[Stk[0]]);
 72     for (int y,z;Par(x);)
 73     {
 74         y=Par(x),z=Par(y);
 75         if (!z)
 76             if (Lch(y)==x)    zig(x);
 77             else    zag(x);
 78         else
 79         if (Lch(z)==y)
 80             if (Lch(y)==x)    zig(y),zig(x);
 81             else    zag(x),zig(x);
 82         else
 83             if (Rch(y)==x)    zag(y),zag(x);
 84             else    zig(x),zag(x);
 85     }
 86     Tupdate(root=x);
 87 }
 88 inline int Findkth(int k)
 89 {
 90     if (k==0)    return 0;
 91     if (k>N)    return N+1;
 92     for (int p=root;;)
 93     {
 94         Down(p);
 95         if (k<=Size(Lch(p)))    p=Lch(p);
 96         else
 97         if (k<=Size(Lch(p))+1)    return p;
 98         else    k-=Size(Lch(p))+1,p=Rch(p);
 99     }
100 }
101 inline int Findintv(int l,int r)
102 {
103     int u=Findkth(l-1),v=Findkth(r+1),tmp;
104     if (l==1&&r==N)    return root;
105     if (u<1)    return splay(root,v),Lch(v);
106     if (v>N)    return splay(root,u),Rch(u);
107     splay(root,v);
108     Par(Lch(v))=0;
109     splay(Lch(v),u);
110     Par(u)=v;
111     return Rch(u);
112 }
113 int main()
114 {
115     scanf("%d%d",&N,&M);
116     root=1;
117     for (int i=1;i<=N;++i)
118         Par(i)=i-1,Rch(i-1)=i,Size(i)=N-i+1;
119     for (int i=1;i<=M;++i)
120     {
121         scanf("%d%d%d",&cmd,&x,&y);
122         Root=Findintv(x,y);
123         if (cmd==1)
124         {
125             scanf("%d",&delt);
126             Delt(Root)+=delt,Max(Root)+=delt,Val(Root)+=delt;
127             splay(root,Root);
128         }
129         else
130         if (cmd==2)    Rev(Root)^=1;
131         else    printf("%d\n",Max(Root));
132     }
133     return 0;
134 }
135 

posted on 2010-04-12 09:07 jsn1993 阅读(511) 评论(0)  编辑 收藏 引用 所属分类: Data Structures


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理