首页 > 代码库 > bzoj 1500: [NOI2005]维修数列 splay

bzoj 1500: [NOI2005]维修数列 splay

1500: [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 6556  Solved: 1963
[Submit][Status]

Description

Input

输入文件的第1行包含两个数N和M,N表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。

Output

对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

HINT

 

 

 splay的難點就在於信息的同步與下放。

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 1100000#define MAXV MAXN*2#define MAXE MAXV*2#define MAXT MAXN#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;inline int nextInt(){        char ch;        int x=0;        bool flag=false;        do                ch=(char)getchar(),flag=(ch==-)?true:flag;        while(ch<0||ch>9);        do x=x*10+ch-0;        while (ch=(char)getchar(),ch<=9 && ch>=0);        return x*(flag?-1:1);}int n,m;struct Splay_tree{        int ch[MAXT][2];        int pnt[MAXT];        int val[MAXT];        int siz[MAXT];        int sum[MAXT];        int lx[MAXT],rx[MAXT],mx[MAXT];        int chgf[MAXT],rev[MAXT];        int stack[MAXT],tops;        int root;        queue<int> Q;        Splay_tree()        {                root=0;                for (int i=1;i<=1000000;i++)                        Q.push(i);        }        int nextNode()//支持垃圾回收機制        {                int now=Q.front();                Q.pop();                if (ch[now][0])                        Q.push(ch[now][0]);                if (ch[now][1])                        Q.push(ch[now][1]);                ch[now][0]=ch[now][1]=0;                return now;        }        void Rotate(int now)        {                int p=pnt[now],anc=pnt[p];                int dir=(ch[p][0]==now);                if (anc)                {                        ch[anc][ch[anc][1]==p]=now;                }                pnt[now]=anc;                ch[p][1-dir]=ch[now][dir];                pnt[ch[now][dir]]=p;                pnt[p]=now;                ch[now][dir]=p;                up(p);                up(now);        }        void Reverse(int now)        {                rev[ch[now][0]]^=1;                rev[ch[now][1]]^=1;                swap(ch[now][0],ch[now][1]);                swap(lx[ch[now][0]],rx[ch[now][0]]);                swap(lx[ch[now][1]],rx[ch[now][1]]);                up(now);//容易忽略,由於改變了子節點的lx,rx值,需要更新        }        void Reset(int now,int v)//注意        {                lx[now]=rx[now]=v*siz[now];                mx[now]=sum[now]=siz[now]*v;                val[now]=v;                chgf[now]=v;        }        void down(int now)        {                if (rev[now])                {                        Reverse(now);//                        rev[now]=0;                }                if (chgf[now]!=INF)                {                        Reset(ch[now][0],chgf[now]);                        Reset(ch[now][1],chgf[now]);                        chgf[now]=INF;                }        }        void up(int now)        {                if (!now)                {                        //cout<<"Update error"<<endl;;                        throw "Update 0";                }                sum[now]=sum[ch[now][0]]+sum[ch[now][1]]+val[now];                siz[now]=siz[ch[now][0]]+siz[ch[now][1]]+1;                lx[now]=sum[ch[now][0]]+val[now]+lx[ch[now][1]];                lx[now]=max(lx[now],sum[ch[now][0]]+val[now]);                if (ch[now][0])lx[now]=max(lx[now],lx[ch[now][0]]);                rx[now]=sum[ch[now][1]]+val[now]+rx[ch[now][0]];                rx[now]=max(rx[now],sum[ch[now][1]]+val[now]);                if (ch[now][1])rx[now]=max(rx[now],rx[ch[now][1]]);                mx[now]=max(max(val[now]+rx[ch[now][0]],val[now]+lx[ch[now][1]])                                ,max(val[now],val[now]+rx[ch[now][0]]+lx[ch[now][1]]));                if (ch[now][0])mx[now]=max(mx[now],mx[ch[now][0]]);                if (ch[now][1])mx[now]=max(mx[now],mx[ch[now][1]]);        }        int Splay(int now,int tp=0)        {                int x=now;                tops=-1;                if (now==tp)return now;                while (x!=0)/**/                {                        stack[++tops]=x;                        x=pnt[x];                }                while (tops>=0)                        down(stack[tops--]);                while (pnt[now]!=tp)/**/                {                        int p=pnt[now],anc=pnt[p];                        if (anc==tp)/**/                        {                                Rotate(now);                        }else                        {                                if ((ch[anc][0]==p) == (ch[p][1]==now))                                {                                        Rotate(p);                                        Rotate(now);                                }else                                {                                        Rotate(now);                                        Rotate(now);                                }                        }                }                if (!tp)root=now;                return now;        }        int Get_kth(int now,int rk)        {                down(now);//這裏要先下放標記                if (rk==siz[ch[now][0]]+1)                {                        return now;                }                if (siz[ch[now][0]]<rk)                        return Get_kth(ch[now][1],rk-1-siz[ch[now][0]]);                else                        return Get_kth(ch[now][0],rk);        }        void Insert(int pos,int v)        {                int now;                now=nextNode();                val[now]=v;                chgf[now]=INF;                rev[now]=0;                mx[now]=sum[now]=v;                lx[now]=rx[now]=v;//mx 易忽略                if (!pos)                {                        Splay(Get_kth(root,1));                        pnt[root]=now;                        ch[now][1]=root;                        root=now;//衝定義根節點                        up(now);                        return ;                }else                {                        Splay(Get_kth(root,pos));                        pnt[root]=now;                        pnt[ch[root][1]]=now;                        ch[now][0]=root;                        ch[now][1]=ch[root][1];                        ch[root][1]=0;                        if (root)up(root);                        root=now;                        up(now);                }        }        void Insert(int pos,int *arr,int n)//區間加數        {                int now=0,kroot;                Build_tree(arr,now,0,n-1);                //Scan(now);                if (!root)                {                        root=now;                        return ;                }                if (!pos)                {                        Splay(Get_kth(root,1));                        pnt[now]=root;                        ch[root][0]=now;                        up(root);                }else if (pos==siz[root])                {                        Splay(Get_kth(root,siz[root]));                        pnt[now]=root;                        ch[root][1]=now;                        up(root);                }else                {                        Splay(Get_kth(root,pos));                        Splay(Get_kth(root,pos+1),root);                        ch[ch[root][1]][0]=now;                        pnt[now]=ch[root][1];                        up(ch[root][1]);                        up(root);                }        }        void Delete(int l,int r)        {                if (l==1 && r==siz[root])                {                        Q.push(root);                        root=0;                }else if (l==1)                {                        Splay(Get_kth(root,r+1));                        Q.push(ch[root][0]);                        ch[root][0]=0;                        up(root);                }else if (r==siz[root])                {                        Splay(Get_kth(root,l-1));                        Q.push(ch[root][1]);                        ch[root][1]=0;                        up(root);                }else                {                        Splay(Get_kth(root,l-1));                        Splay(Get_kth(root,r+1),root);                        Q.push(ch[ch[root][1]][0]);                        ch[ch[root][1]][0]=0;                        up(ch[root][1]);                        up(root);                }        }        void Scan(int now)        {                if (!now)return ;                down(now);                if (sum[now]!=sum[ch[now][0]]+sum[ch[now][1]]+val[now])throw "Scan_up";                if (ch[now][0] && pnt[ch[now][0]]!=now)throw "Scan";                Scan(ch[now][0]);                printf("%d ",val[now]);                if (ch[now][1] && pnt[ch[now][1]]!=now)throw "Scan";                Scan(ch[now][1]);        }        qword Get_sum(int l,int r)        {                if (l==1 && r==siz[root])                {                        return sum[root];                }else if (l==1)                {                        Splay(Get_kth(root,r+1));                        return sum[ch[root][0]];                }else if (r==siz[root])                {                        Splay(Get_kth(root,l-1));                        return sum[ch[root][1]];                }else                {                        Splay(Get_kth(root,l-1));                        Splay(Get_kth(root,r+1),root);                        return sum[ch[ch[root][1]][0]];                }        }        qword Max_sum(int l,int r)        {                if (l==1 && r==siz[root])                {                        return mx[root];                }else if (l==1)                {                        Splay(Get_kth(root,r+1));                        return mx[ch[root][0]];                }else if (r==siz[root])                {                        Splay(Get_kth(root,l-1));                        return mx[ch[root][1]];                }else                {                        Splay(Get_kth(root,l-1));                        Splay(Get_kth(root,r+1),root);                        return mx[ch[ch[root][1]][0]];                }        }        void Build_tree(int *arr,int &now,int l,int r)        {                if (r<l)return ;                int mid=(l+r)>>1;                now=nextNode();                val[now]=arr[mid];                chgf[now]=INF;                rev[now]=0;                mx[now]=sum[now]=arr[mid];                lx[now]=rx[now]=arr[mid];                if (l<=mid-1)                        Build_tree(arr,ch[now][0],l,mid-1);                if (mid+1<=r)                        Build_tree(arr,ch[now][1],mid+1,r);                pnt[ch[now][0]]=now;                pnt[ch[now][1]]=now;                up(now);        }        void Make_Reverse(int l,int r)        {                if (l==1 && r==siz[root])                {                        Reverse(root);                        up(root);                }else if (l==1)                {                        Splay(Get_kth(root,r+1));                        Reverse(ch[root][0]);                        up(root);                }else if (r==siz[root])                {                        Splay(Get_kth(root,l-1));                        Reverse(ch[root][1]);                        up(root);                }else                {                        Splay(Get_kth(root,l-1));                        Splay(Get_kth(root,r+1),root);                        Reverse(ch[ch[root][1]][0]);                        up(ch[root][1]);                        up(root);//對子樹的處理都要更新至根節點                }        }        void Make_same(int l,int r,int v)        {                if (l==1 && r==siz[root])                {                        Reset(root,v);                        up(root);                }else if (l==1)                {                        Splay(Get_kth(root,r+1));                        Reset(ch[root][0],v);                        up(root);                }else if (r==siz[root])                {                        Splay(Get_kth(root,l-1));                        Reset(ch[root][1],v);                        up(root);                }else                {                        Splay(Get_kth(root,l-1));                        Splay(Get_kth(root,r+1),root);                        Reset(ch[ch[root][1]][0],v);                        up(ch[root][1]);                        up(root);                }        }}splay;int num[MAXN];int main(){        //freopen("input.txt","r",stdin);        //freopen("output.txt","w",stdout);        //freopen("sequence7.in","r",stdin);        int i,j,k;        int x,y,z;        char opt[MAXN];        try        {                scanf("%d%d",&n,&m);                for (i=0;i<n;i++)                        scanf("%d",num+i);                scanf("\n");                splay.Build_tree(num,splay.root,0,n-1);                for (i=0;i<m;i++)                {                        scanf("%s",opt);                //        cout<<opt<<endl;                        if (opt[2]==T)//GET_SUM                        {                                scanf("%d%d",&x,&y);                                printf(LL "\n",splay.Get_sum(x,x+y-1));                        }else if (opt[2]==X)//MAX_SUM                        {                                printf(LL"\n",splay.Max_sum(1,splay.siz[splay.root]));                        }else if (opt[2]==S)//INSERT                        {                                scanf("%d%d",&x,&y);                                for (j=0;j<y;j++)                                {                                        scanf("%d",&num[j]);                                }                                splay.Insert(x,num,y);                        }else if (opt[2]==L)//DELETE                        {                                scanf("%d%d",&x,&y);                                splay.Delete(x,x+y-1);                        }else if (opt[2]==K)//MAKE_SAME                        {                                scanf("%d%d%d",&x,&y,&z);                                splay.Make_same(x,x+y-1,z);                        }else if (opt[2]==V)//REVERSE                        {                                scanf("%d%d",&x,&y);                                splay.Make_Reverse(x,x+y-1);                        }                        //splay.Scan(splay.root);                        //cout<<endl;                        scanf("\n");                }        }        catch (const char * err)        {                cerr<<err<<endl;                return 0;        }        return 0;}

 

bzoj 1500: [NOI2005]维修数列 splay