Description

　　請寫一個程序，要求維護一個數列，支持以下6種操作：（請注意，格式欄中的下劃線‘ _ ’表示實際輸入文件中的空格）
　　1. 插入 INSERT_posi_tot_c1_c2_…_ctot 在當前數列的第posi個數字后插入tot個數字：c1, c2, …, ctot；若在數列首插入，則posi為0
　　2. 刪除 DELETE_posi_tot 從當前數列的第posi個數字開始連續刪除tot個數字
　　3. 修改 MAKE-SAME_posi_tot_c 將當前數列的第posi個數字開始的連續tot個數字統一修改為c
　　4. 翻轉 REVERSE_posi_tot 取出從當前數列的第posi個數字開始的tot個數字，翻轉后放入原來的位置
　　5. 求和 GET-SUM_posi_tot 計算從當前數列開始的第posi個數字開始的tot個數字的和并輸出
　　6. 求和最大的子列 MAX-SUM 求出當前數列中和最大的一段子列，并輸出最大和

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

Data Constraint

Hint

樣例說明請點這里
【數據規模和約定】
　　你可以認為在任何時刻，數列中至少有1個數。
　　輸入數據一定是正確的，即指定位置的數在數列中一定存在。
　　50%的數據中，任何時刻數列中最多含有30 000個數；
　　100%的數據中，任何時刻數列中最多含有500 000個數。
　　100%的數據中，任何時刻數列中任何一個數字均在[-1 000, 1 000]內。
　　100%的數據中，M ≤20 000，插入的數字總數不超過4 000 000個，輸入文件大小不超過20MBytes。

Solution

• 這題真的調試了一萬年……

• 經典的Splay操作，維護子序列的話就維護一下子樹前后綴的最大值，在合并到父親上即可。

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=5e5+3,inf=1e9; int root,tot; int a[N],fa[N],key[N],size[N],s[N][2]; int sum[N],c[N],mx[N],pre[N],suf[N],back[N]; bool rev[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline void newnode(int &v,int val,int p) {if(back[0]) v=back[back[0]--]; else v=++tot;sum[v]=mx[v]=key[v]=val;pre[v]=suf[v]=max(0,val);size[v]=1,fa[v]=p,c[v]=inf;s[v][0]=s[v][1]=rev[v]=0; } inline void reverse(int v) {if(!v) return;swap(s[v][0],s[v][1]);swap(pre[v],suf[v]);rev[v]^=1; } inline void modify(int v,int val) {if(!v) return;sum[v]=size[v]*val,c[v]=key[v]=val;if(val>0) mx[v]=pre[v]=suf[v]=sum[v]; elsepre[v]=suf[v]=0,mx[v]=val; } inline void update(int v) {sum[v]=sum[s[v][0]]+sum[s[v][1]]+key[v];size[v]=size[s[v][0]]+size[s[v][1]]+1;pre[v]=max(pre[s[v][0]],sum[s[v][0]]+key[v]+pre[s[v][1]]);suf[v]=max(suf[s[v][1]],sum[s[v][1]]+key[v]+suf[s[v][0]]);mx[v]=max(0,suf[s[v][0]])+key[v]+max(0,pre[s[v][1]]);if(s[v][0]) mx[v]=max(mx[v],mx[s[v][0]]);if(s[v][1]) mx[v]=max(mx[v],mx[s[v][1]]); } inline void down(int v) {if(rev[v]){reverse(s[v][0]),reverse(s[v][1]);rev[v]=false;}if(c[v]<inf){modify(s[v][0],c[v]),modify(s[v][1],c[v]);c[v]=inf;} } inline void build(int &v,int l,int r,int p) {if(l>r) return;int mid=(l+r)>>1;newnode(v,a[mid],p);build(s[v][0],l,mid-1,v);build(s[v][1],mid+1,r,v);update(v); } inline void rotate(int x) {down(x);int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[x][w^1]]=y;if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x,int k) {for(int y;(y=fa[x])^k;rotate(x))if(fa[y]^k) rotate(pd(x)==pd(y)?y:x);update(x);if(!k) root=x; } inline int kth(int v,int k) {down(v);if(size[s[v][0]]+1==k) return v;if(k<=size[s[v][0]]) return kth(s[v][0],k);return kth(s[v][1],k-size[s[v][0]]-1); } inline void change(int l,int r,int val) {splay(kth(root,l-1),0);splay(kth(root,r+1),root);modify(s[s[root][1]][0],val); } inline int get_sum(int l,int r) {splay(kth(root,l-1),0);splay(kth(root,r+1),root);return sum[s[s[root][1]][0]]; } inline void insert(int x,int y) {splay(kth(root,x),0);splay(kth(root,x+1),root);build(s[s[root][1]][0],1,y,s[root][1]);update(s[root][1]),update(root); } inline void travel(int v) {down(v);if(s[v][0]) travel(s[v][0]);back[++back[0]]=v;if(s[v][1]) travel(s[v][1]); } inline void delete_num(int x,int y) {splay(kth(root,x-1),0);splay(kth(root,y+1),root);travel(s[s[root][1]][0]);s[s[root][1]][0]=0;update(s[root][1]),update(root); } inline void flip(int l,int r) {splay(kth(root,l-1),0);splay(kth(root,r+1),root);reverse(s[s[root][1]][0]); } inline int get_max(int l,int r) {splay(kth(root,l-1),0);splay(kth(root,r+1),root);return mx[s[s[root][1]][0]]; } inline void print(int v) {down(v);if(s[v][0]) print(s[v][0]);if(key[v]<inf) write(key[v]),putchar(' ');if(s[v][1]) print(s[v][1]); } int main() {int n=read(),m=read();a[1]=a[n+2]=-inf,c[0]=inf;for(int i=2;i<=n+1;i++) a[i]=read();build(root,1,n+2,0);while(m--){char ch=getchar();while(ch!='X' && ch!='G' && ch!='V' && ch!='I' && ch!='D' && ch!='K') ch=getchar();if(ch=='K')//MAKE-SAME{getchar(),getchar();int x=read()+1,y=x+read()-1;change(x,y,read());}elseif(ch=='G')//GET-SUM{getchar(),getchar(),getchar();int x=read()+1,y=x+read()-1;write(get_sum(x,y)),putchar('\n');}elseif(ch=='I')//INSERT{int x=read()+1,y=read();for(int i=1;i<=y;i++) a[i]=read();insert(x,y);}elseif(ch=='D')//DELETE{int x=read()+1,y=x+read()-1;delete_num(x,y); }elseif(ch=='V')//REVERSE{int x=read()+1,y=x+read()-1;flip(x,y);}elseif(ch=='X')//MAX-SUM{write(get_max(2,size[root]-1)),putchar('\n');scanf("\n");}}return 0; }

Code

//新打的，更快的，更短的

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=5e5+5,inf=1e9; int root,tot; int fa[N],s[N][2],key[N],size[N]; int pre[N],suf[N],sum[N],mx[N],c[N]; int a[N],back[N]; bool rev[N]; char st[10]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline void update(int x) {sum[x]=sum[s[x][0]]+sum[s[x][1]]+key[x];size[x]=size[s[x][0]]+size[s[x][1]]+1;pre[x]=max(pre[s[x][0]],sum[s[x][0]]+key[x]+pre[s[x][1]]);suf[x]=max(suf[s[x][1]],sum[s[x][1]]+key[x]+suf[s[x][0]]);mx[x]=max(0,suf[s[x][0]])+key[x]+max(0,pre[s[x][1]]);if(s[x][0]) mx[x]=max(mx[x],mx[s[x][0]]);if(s[x][1]) mx[x]=max(mx[x],mx[s[x][1]]); } inline void newnode(int &v,int val,int p) {if(back[0]) v=back[back[0]--]; else v=++tot;key[v]=sum[v]=mx[v]=val;fa[v]=p,size[v]=1,c[v]=inf;pre[v]=suf[v]=max(0,val);s[v][0]=s[v][1]=rev[v]=0; } void build(int &v,int l,int r,int p) {if(l>r) return;int mid=l+r>>1;newnode(v,a[mid],p);build(s[v][0],l,mid-1,v);build(s[v][1],mid+1,r,v);update(v); } inline void reverse(int x) {if(!x) return;swap(s[x][0],s[x][1]);swap(pre[x],suf[x]);rev[x]^=1; } inline void modify(int x,int val) {if(!x) return;sum[x]=size[x]*val,key[x]=c[x]=val;if(val>0) pre[x]=suf[x]=mx[x]=sum[x]; elsepre[x]=suf[x]=0,mx[x]=val; } inline void down(int x) {if(rev[x]){reverse(s[x][0]),reverse(s[x][1]);rev[x]=false;}if(c[x]<inf){modify(s[x][0],c[x]),modify(s[x][1],c[x]);c[x]=inf;} } inline void rotate(int x) {down(x);int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x,int k) {for(int y;(y=fa[x])^k;rotate(x))if(fa[y]^k) rotate(pd(x)==pd(y)?y:x);update(x);if(!k) root=x; } int kth(int x,int k) {down(x);if(size[s[x][0]]+1==k) return x;if(size[s[x][0]]>=k) return kth(s[x][0],k);return kth(s[x][1],k-size[s[x][0]]-1); } inline void get(int x,int y) {splay(kth(root,x-1),0);splay(kth(root,y+1),root); } void travel(int x) {if(s[x][0]) travel(s[x][0]);back[++back[0]]=x;if(s[x][1]) travel(s[x][1]); } int main() {int n=read(),m=read();a[1]=a[n+2]=inf;for(int i=2;i<=n+1;i++) a[i]=read();build(root,1,n+2,0);while(m--){scanf("%s",&st);if(st[0]=='I'){int x=read()+1,y=read();for(int i=1;i<=y;i++) a[i]=read();splay(kth(root,x),0);splay(kth(root,x+1),root);build(s[s[root][1]][0],1,y,s[root][1]);update(s[root][1]),update(root);}elseif(st[0]=='D'){int x=read()+1,y=x+read()-1;get(x,y);travel(s[s[root][1]][0]);s[s[root][1]][0]=0;update(s[root][1]),update(root);}elseif(st[0]=='R'){int x=read()+1,y=x+read()-1;get(x,y);reverse(s[s[root][1]][0]);}elseif(st[0]=='G'){int x=read()+1,y=x+read()-1;get(x,y);write(sum[s[s[root][1]][0]]),putchar('\n');}elseif(st[2]=='K'){int x=read()+1,y=x+read()-1,z=read();get(x,y);modify(s[s[root][1]][0],z);}else{get(2,size[root]-1);write(mx[s[s[root][1]][0]]),putchar('\n');}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 2413. 【NOI2005】维护数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。