【BZOJ4864】神秘物质 [Splay]

神秘物质

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

Input

　　

Output

　　

Sample Input

　　

Sample Output

　　1
　　2
　　1
　　5

HINT

　　

Main idea

　　每个点有一个权值，维护一个结构，支持合并相邻两点，删除单点，加入单点，查询区间子集极差的最大值和最小值。

Solution

　　首先我们可以发现，区间子集极差的最大值显然就是整个区间的最大值-区间最小值，然后区间子集极差最小值只有相邻点的才会产生贡献。

　　那么我们用Splay来维护这个结构即可，维护一下子树最大值、子树最小值、子树邻差最小值即可。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n,m;

 int x,y,a[ONE];

 int root,cnt;

 int lc[ONE],rc[ONE],fa[ONE];

 int size[ONE],val[ONE];

 int maxx[ONE],minn[ONE],del[ONE];

 int Ls[ONE],Rs[ONE];

 char ch[];

 inline int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void Up(int i)

 {

         size[i] = size[lc[i]] + size[rc[i]] + ;

         maxx[i] = minn[i] = val[i];

         del[i] = INF;

         Ls[i] = Rs[i] = i;

         if(lc[i])

         {

             Ls[i] = Ls[lc[i]];

             maxx[i] = max(maxx[i], maxx[lc[i]]);

             minn[i] = min(minn[i], minn[lc[i]]);

             del[i] = min(del[i], del[lc[i]]);

             del[i] = min(del[i], abs( val[i]-val[Rs[lc[i]]] ) );

         }

         if(rc[i])

         {

             Rs[i] = Rs[rc[i]];

             maxx[i] = max(maxx[i], maxx[rc[i]]);

             minn[i] = min(minn[i], minn[rc[i]]);

             del[i] = min(del[i], del[rc[i]]);

             del[i] = min(del[i], abs( val[i]-val[Ls[rc[i]]] ) );

         }

 }

 void Turn(int x)

 {

         int y = fa[x], z = fa[y];

         int b = x==lc[y] ? rc[x]:lc[x];

         fa[y] = x;    fa[x] = z;

         if(b) fa[b] = y;

         if(z)

         {

             if(y == lc[z]) lc[z] = x;

             else rc[z] = x;

         }

         if(x==lc[y]) rc[x] = y,lc[y] = b;

         else lc[x] = y, rc[y] = b;

         Up(y);    Up(x);

 }

 void Splay(int x,int pos)

 {

         while(fa[x] != pos)

         {

             if(fa[fa[x]] != pos)

             {

                 if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]);

                 else Turn(x);

             }

             Turn(x);

         }

         if(pos == ) root = x;

 }

 int Build(int i,int l,int r)

 {

         int mid = l+r >> ;

         fa[mid] = i;

         if(l <= mid-) lc[mid] = Build(mid, l,mid-);

         if(mid+ <= r) rc[mid] = Build(mid, mid+,r);

         Up(mid);

         return mid;

 }

 int Getid(int num)

 {

         int i = root;

         while(size[lc[i]] +  != num)

         {

             if(size[lc[i]] +  < num)

                 num -= size[lc[i]] + ,    i = rc[i];

             else i = lc[i];

         }

         return i;

 }

 void Delete(int i)

 {

         int x = Getid(i);

         Splay(x, );

         int L = Rs[lc[x]];    Splay(L,);

         int R = Ls[rc[x]];    Splay(R,L);

         lc[R] = ;

         Splay(R,);

 }

 void Insert(int i,int Val)

 {

         int x = Getid(i);

         Splay(x,);

         int R = Ls[rc[x]];    Splay(R,x);

         val[++cnt] = Val; fa[cnt] = R; lc[R] = cnt;

         Splay(cnt,);

 }

 int main()

 {

         n=get();    m=get();

         for(int i=;i<=n;i++)

             val[i+] = get();

         val[] = val[n+] = INF;

         cnt = n+;

         root = n+ >> ;

         Build(,,n+);

         while(m--)

         {

             scanf("%s",ch+);    x=get();    y=get();

             x++;

             if(ch[] == 'r')

             {

                 Insert(x+,y);

                 Delete(x);    Delete(x);

             }

             if(ch[] == 's')

                 Insert(x,y);

             if(ch[] == 'x')

             {

                 y++;

                 x = Getid(x-);    y = Getid(y+);

                 Splay(x,);    Splay(y,x);

                 printf("%d\n", maxx[lc[y]] - minn[lc[y]]);

             }

             if(ch[] == 'n')

             {

                 y++;

                 x = Getid(x-);    y = Getid(y+);

                 Splay(x,);    Splay(y,x);

                 printf("%d\n", del[lc[y]]);

             }

         }

 }