Description

请写一个程序，要求维护一个数列，支持以下 6 种操作：

请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。

第2行包含N个数字，描述初始时的数列。

以下M行，每行一条命令，格式参见问题描述中的表格。

任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。

插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

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

Solution

平衡树模板(呵

qtmd

注意插入后更新不能用splay函数……

因为可能插入的是0之类的然后splay就RE了

只能用两个update或者splay+特判

题目卡空间记得回收节点编号

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (500000+100)  5 using namespace std;  6   7 int Lmax[N],Rmax[N],Mmax[N],Sum[N],Cov[N],Rev[N];  8 int n,m,pos,tot,Root,a[N];  9 int stack[N],top,sz,k; 10 int Val[N],Size[N],Son[N][2],Father[N]; 11 char opt[21]; 12  13 int Get(int x) {
   return Son[Father[x]][1]==x;} 14 void Clear(int x) {stack[++top]=x; Cov[x]=Rev[x]=Sum[x]=Mmax[x]=Lmax[x]=Rmax[x]=Father[x]=Son[x][0]=Son[x][1]=Size[x]=Val[x]=0;} 15 int Getid() {
   if (!top) return ++sz; return stack[top--];} 16  17 void Update(int x) 18 { 19     Sum[x]=Sum[Son[x][0]]+Sum[Son[x][1]]+Val[x]; 20     Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1; 21     Mmax[x]=max(max(Mmax[Son[x][0]],Mmax[Son[x][1]]),Rmax[Son[x][0]]+Lmax[Son[x][1]]+Val[x]); 22     Lmax[x]=max(Lmax[Son[x][0]],Sum[Son[x][0]]+Lmax[Son[x][1]]+Val[x]); 23     Rmax[x]=max(Rmax[Son[x][1]],Sum[Son[x][1]]+Val[x]+Rmax[Son[x][0]]); 24 } 25  26 int Build(int l,int r,int fa) 27 { 28     if (l>r) return 0; 29     if (l==r) 30     { 31         int id=Getid(); 32         Val[id]=Sum[id]=Mmax[id]=a[l]; 33         Size[id]=1; 34         Father[id]=fa; 35         Lmax[id]=Rmax[id]=max(a[l],0); 36         return id; 37     } 38     int mid=(l+r)>>1; 39     int id=Getid(); 40     Son[id][0]=Build(l,mid-1,id); 41     Son[id][1]=Build(mid+1,r,id); 42     Father[id]=fa; 43     Val[id]=a[mid]; 44     Update(id); 45     return id; 46 } 47  48 void Pushdown(int x) 49 { 50     int l=Son[x][0],r=Son[x][1]; 51     if(Cov[x]) 52     { 53         Rev[x]=Cov[x]=0; 54         if(l)Cov[l]=1,Val[l]=Val[x],Sum[l]=Val[x]*Size[l]; 55         if(r)Cov[r]=1,Val[r]=Val[x],Sum[r]=Val[x]*Size[r]; 56         if(Val[x]>=0) 57         { 58             if(l)Lmax[l]=Rmax[l]=Mmax[l]=Sum[l]; 59             if(r)Lmax[r]=Rmax[r]=Mmax[r]=Sum[r]; 60         } 61         else  62         { 63             if(l)Lmax[l]=Rmax[l]=0,Mmax[l]=Val[x]; 64             if(r)Lmax[r]=Rmax[r]=0,Mmax[r]=Val[x]; 65         } 66     } 67     if(Rev[x]) 68     { 69         Rev[x]^=1;Rev[l]^=1;Rev[r]^=1; 70         swap(Lmax[l],Rmax[l]);swap(Lmax[r],Rmax[r]); 71         swap(Son[l][0],Son[l][1]);swap(Son[r][0],Son[r][1]); 72     } 73 } 74  75 void Rotate(int x) 76 { 77     int wh=Get(x); 78     int fa=Father[x],fafa=Father[fa]; 79     Father[fa]=x; Son[fa][wh]=Son[x][wh^1]; 80     if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 81     Father[x]=fafa; Son[x][wh^1]=fa; 82     if (fafa) Son[fafa][Son[fafa][1]==fa]=x; 83     Update(fa); 84     Update(x); 85 } 86  87 void Push(int x){
   if (x!=Root) Push(Father[x]); Pushdown(x);} 88 void Splay(int x,int tar) 89 { 90     Push(x); 91     for (int fa;(fa=Father[x])!=tar;Rotate(x)) 92         if (Father[fa]!=tar) 93             Rotate(Get(fa)==Get(x)?fa:x); 94     if (!tar) Root=x; 95 } 96  97 int Findx(int x) 98 { 99     int now=Root;100     while (1)101     {102         Pushdown(now);103         if (Size[Son[now][0]]>=x)104             now=Son[now][0];105         else106         {107             x-=Size[Son[now][0]];108             if (x==1)109             {110                 Splay(now,0);111                 return now;112             }113             x--;114             now=Son[now][1];115         }116     }117 }118 119 int Split(int x,int y)120 {121     int xx=Findx(x);122     int yy=Findx(y);123     Splay(xx,0); Splay(yy,xx);124     return Son[yy][0];125 }126 127 void Clear_up(int x)128 {129     if (Son[x][0]) Clear_up(Son[x][0]);130     if (Son[x][1]) Clear_up(Son[x][1]);131     Clear(x);132 }133 134 void INSERT(int pos,int tot)135 {136     Split(pos+1,pos+2);137     for (int i=1;i<=tot;++i)138         scanf("%d",&a[i]);139     int x=Build(1,tot,Son[Root][1]);140     Son[Son[Root][1]][0]=x;141     Update(Son[Root][1]); Update(Root);142 }143 144 void DELETE(int pos,int tot)145 {146     int x=Split(pos,pos+tot+1);147     Son[Father[x]][Get(x)]=0;148     Clear_up(x);149     Update(Son[Root][1]); Update(Root);150 }151 152 void MAKE_SAME(int pos,int tot,int k)153 {154     int x=Split(pos,pos+tot+1);155     Cov[x]=k;156     Val[x]=k; Cov[x]=1; Sum[x]=Size[x]*k;157     if(k>=0)Lmax[x]=Rmax[x]=Mmax[x]=Sum[x];158     else Lmax[x]=Rmax[x]=0,Mmax[x]=k;159     Update(Son[Root][1]); Update(Root);160 }161 162 void REVERSE(int pos,int tot)163 {164     int x=Split(pos,pos+tot+1);165     Rev[x]^=1;166     swap(Son[x][0],Son[x][1]);167     swap(Lmax[x],Rmax[x]);168     Update(Son[Root][1]); Update(Root);169 }170 171 void GET_SUM(int pos,int tot)172 {173     int x=Split(pos,pos+tot+1);174     printf("%d\n",Sum[x]);175     Update(Son[Root][1]); Update(Root);176 }177 178 int main()179 {180     scanf("%d%d",&n,&m);181     for (int i=1;i<=n;++i)182         scanf("%d",&a[i+1]);183     Mmax[0]=a[1]=a[n+2]=-0x3fffffff;184     Build(1,n+2,0);185     Root=1;186     while (m--)187     {188         scanf("%s",opt);189         if (opt[0]!='M' || opt[2]!='X') scanf("%d%d",&pos,&tot);190         if (opt[0]=='I') INSERT(pos,tot);191         if (opt[0]=='D') DELETE(pos,tot);192         if (opt[0]=='M')193         {194             if (opt[2]=='X') printf("%d\n",Mmax[Root]);195             else scanf("%d",&k),MAKE_SAME(pos,tot,k);196         }197         if (opt[0]=='R')REVERSE(pos,tot);198         if (opt[0]=='G')GET_SUM(pos,tot);199     }200 }