济南建设厅官方网站,阿里大数据官网,wordpress给外部链接加上跳转,通信管理局网站备案Description Input 输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。任何时刻数列…
Description
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
对于MAX-SUM操作，维护：lsum：从当前区间左端点开始连续一段最大和，rsum：以当前区间右端点结尾连续一段最大和，初始化为0。然后就可以开始瞎搞了√
注意一些小细节，比如说update的时候记得判左右孩子存不存在什么的（或初始化0这个点的mx为-inf。
【splay】
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 using namespace std;
6 const int inf=0x3f3f3f3f;
7 const int N=1000005;
8 queue<int>q;
9 int n,m,root,cnt;
10 int tr[N][2],id[N],a[N],size[N],sum[N],v[N],mx[N],lx[N],rx[N],fa[N];
11 bool tag[N],rev[N];
12 int read()
13 {
14 int x=0,f=1;char c=getchar();
15 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
16 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
17 return x*f;
18 }
19 void update(int x)
20 {
21 int l=tr[x][0],r=tr[x][1];
22 sum[x]=sum[l]+sum[r]+v[x];
23 size[x]=size[l]+size[r]+1;
24 mx[x]=max(mx[l],mx[r]);
25 mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
26 lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
27 rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
28 }
29 void pushdown(int x)
30 {
31 int l=tr[x][0],r=tr[x][1];
32 if(tag[x])
33 {
34 rev[x]=tag[x]=0;
35 if(l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*size[l];
36 if(r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*size[r];
37 if(v[x]>=0)
38 {
39 if(l)mx[l]=lx[l]=rx[l]=sum[l];
40 if(r)mx[r]=lx[r]=rx[r]=sum[r];
41 }
42 else
43 {
44 if(l)lx[l]=rx[l]=0,mx[l]=v[x];
45 if(r)lx[r]=rx[r]=0,mx[r]=v[x];
46 }
47 }
48 if(rev[x])
49 {
50 rev[x]^=1;rev[l]^=1;rev[r]^=1;
51 swap(lx[l],rx[l]);swap(lx[r],rx[r]);
52 swap(tr[l][0],tr[l][1]);swap(tr[r][0],tr[r][1]);
53 }
54 }
55 void rotate(int x,int& k)
56 {
57 int y=fa[x],z=fa[y],l,r;
58 l=(tr[y][1]==x);r=l^1;
59 if(y==k)k=x;
60 else tr[z][tr[z][1]==y]=x;
61 fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
62 tr[y][l]=tr[x][r];tr[x][r]=y;
63 update(y);update(x);
64 }
65 void splay(int x,int& k)
66 {
67 while(x!=k)
68 {
69 int y=fa[x],z=fa[y];
70 if(y!=k)
71 {
72 if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k);
73 else rotate(y,k);
74 }
75 rotate(x,k);
76 }
77 }
78 int find(int x,int rnk)
79 {
80 pushdown(x);
81 int l=tr[x][0],r=tr[x][1];
82 if(size[l]+1==rnk)return x;
83 else if(size[l]>=rnk)return find(l,rnk);
84 else return find(r,rnk-size[l]-1);
85 }
86 int turn(int k,int tot)
87 {
88 int x=find(root,k),y=find(root,k+tot+1);
89 splay(x,root);splay(y,tr[x][1]);
90 return tr[y][0];
91 }
92 void build(int l,int r,int f)
93 {
94 if(l>r)return;
95 int mid=(l+r)>>1,now=id[mid],last=id[f];
96 if(l==r)
97 {
98 sum[now]=a[l];size[now]=1;tag[now]=rev[now]=0;
99 if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];
100 else lx[now]=rx[now]=0,mx[now]=a[l];
101 }
102 else build(l,mid-1,mid),build(mid+1,r,mid);
103 v[now]=a[mid];fa[now]=last;update(now);
104 tr[last][mid>=f]=now;
105 }
106 void insert(int k,int tot)
107 {
108 for(int i=1;i<=tot;i++)a[i]=read();
109 for(int i=1;i<=tot;i++)
110 if(!q.empty())id[i]=q.front(),q.pop();
111 else id[i]=++cnt;
112 build(1,tot,0);int rt=id[(1+tot)>>1];
113 int x=find(root,k+1),y=find(root,k+2);
114 splay(x,root);splay(y,tr[x][1]);
115 tr[y][0]=rt;fa[rt]=y;
116 update(y);update(x);
117 }
118 void rec(int x)
119 {
120 if(!x)return;
121 int l=tr[x][0],r=tr[x][1];
122 rec(l);rec(r);q.push(x);
123 fa[x]=tr[x][0]=tr[x][1]=0;
124 tag[x]=rev[x]=0;
125 }
126 void erase(int k,int tot)
127 {
128 int x=turn(k,tot),y=fa[x];
129 rec(x);tr[y][0]=0;
130 update(y);update(fa[y]);
131 }
132 void makesame(int k,int tot,int val)
133 {
134 int x=turn(k,tot),y=fa[x];
135 tag[x]=1;v[x]=val;sum[x]=val*size[x];
136 if(val>=0)lx[x]=rx[x]=mx[x]=sum[x];
137 else lx[x]=rx[x]=0,mx[x]=val;
138 update(y);update(fa[y]);
139 }
140 void rever(int k,int tot)
141 {
142 int x=turn(k,tot),y=fa[x];
143 if(!tag[x])
144 {
145 rev[x]^=1;
146 swap(tr[x][0],tr[x][1]);
147 swap(lx[x],rx[x]);
148 update(y);update(fa[y]);
149 }
150 }
151 void query(int k,int tot)
152 {
153 int x=turn(k,tot);
154 printf("%d\n",sum[x]);
155 }
156 int main()
157 {
158 n=read();m=read();
159 mx[0]=a[1]=a[n+2]=-inf;
160 for(int i=1;i<=n;i++)a[i+1]=read();
161 for(int i=1;i<=n+2;i++)id[i]=i;
162 root=(n+3)>>1;cnt=n+2;
163 build(1,n+2,0);
164 int k,tot,val;
165 char s[15];
166 while(m--)
167 {
168 scanf("%s",s);
169 if(s[0]!='M'||s[2]!='X')k=read(),tot=read();
170 if(s[0]=='I')insert(k,tot);
171 else if(s[0]=='D')erase(k,tot);
172 else if(s[0]=='M')
173 {
174 if(s[2]=='X')printf("%d\n",mx[root]);
175 else val=read(),makesame(k,tot,val);
176 }
177 else if(s[0]=='R')rever(k,tot);
178 else query(k,tot);
179 }
180 return 0;
181 } View Code
【fhq-treap】
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdlib>
5 using namespace std;
6 const int N=5e5+5;
7 const int inf=0x3f3f3f3f;
8 int n,m,tot,pos,val,cnt,root,rt1,rt2,rt3;
9 int st[N],id[N],a[N],ch[N][11];
10 char op[15];
11 #define lc ch][0
12 #define rc ch][1
13 #define rnd ch][2
14 #define sz ch][3
15 #define v ch][4
16 #define tag ch][5
17 #define rev ch][6
18 #define sum ch][7
19 #define mx ch][8
20 #define lsum ch][9
21 #define rsum ch][10
22 int read()
23 {
24 int x=0,f=1;char c=getchar();
25 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
26 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
27 return x*f;
28 }
29 int max(int a,int b){return a>b?a:b;}
30 void up(int w)
31 {
32 int l=w[lc],r=w[rc];
33 w[sz]=l[sz]+r[sz]+1;
34 w[sum]=l[sum]+r[sum]+w[v];
35 w[mx]=l[rsum]+w[v]+r[lsum];
36 if(l)w[mx]=max(w[mx],l[mx]);
37 if(r)w[mx]=max(w[mx],r[mx]);
38 w[lsum]=max(l[lsum],l[sum]+w[v]+r[lsum]);
39 w[rsum]=max(r[rsum],r[sum]+w[v]+l[rsum]);
40 }
41 void dn(int w)
42 {
43 int l=w[lc],r=w[rc];
44 if(w[tag])
45 {
46 w[rev]=w[tag]=0;
47 if(l)l[tag]=1,l[v]=w[v],l[sum]=w[v]*l[sz];
48 if(r)r[tag]=1,r[v]=w[v],r[sum]=w[v]*r[sz];
49 if(w[v]>=0)
50 {
51 if(l)l[mx]=l[lsum]=l[rsum]=l[sum];
52 if(r)r[mx]=r[lsum]=r[rsum]=r[sum];
53 }
54 else
55 {
56 if(l)l[lsum]=l[rsum]=0,l[mx]=w[v];
57 if(r)r[lsum]=r[rsum]=0,r[mx]=w[v];
58 }
59 }
60 if(w[rev])
61 {
62 w[rev]^=1;l[rev]^=1;r[rev]^=1;
63 swap(l[lsum],l[rsum]);swap(r[lsum],r[rsum]);
64 swap(l[lc],l[rc]);swap(r[lc],r[rc]);
65 }
66 }
67 void dfs(int w){if(!w)return;dfs(w[lc]);dfs(w[rc]);up(w);}
68 int build(int n)
69 {
70 int top=0,w;
71 for(int i=1;i<=n;i++)
72 {
73 w=id[cnt--];
74 w[rnd]=rand();w[v]=a[i];
75 while(top&&st[top][rnd]>w[rnd])
76 {
77 st[top][rc]=w[lc];
78 w[lc]=st[top--];
79 }
80 st[top][rc]=w;
81 st[++top]=w;
82 }
83 ch[0][1]=0;dfs(st[1]);
84 return st[1];
85 }
86 void split(int w,int& l,int& r,int k)
87 {
88 if(!w){l=r=0;return;}
89 dn(w);int lson=w[lc][sz];
90 if(k<=lson){r=w;split(w[lc],l,w[lc],k);}
91 else {l=w;split(w[rc],w[rc],r,k-lson-1);}
92 up(w);
93 }
94 int merge(int a,int b)
95 {
96 if(!a||!b)return a+b;
97 if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);up(a);return a;}
98 else {dn(b);b[lc]=merge(a,b[lc]);up(b);return b;}
99 }
100 void insert(int pos,int tot)
101 {
102 for(int i=1;i<=tot;i++)a[i]=read();
103 rt1=rt2=rt3=0;split(root,rt1,rt3,pos);
104 rt2=build(tot);
105 root=merge(rt1,rt2);root=merge(root,rt3);
106 }
107 void rec(int w)
108 {
109 if(!w)return;
110 int l=w[lc],r=w[rc];
111 rec(l);rec(r);id[++cnt]=w;
112 memset(ch[w],0,sizeof(ch[w]));
113 }
114 void erase(int pos,int tot)
115 {
116 rt1=rt2=rt3=0;split(root,rt2,rt3,pos+tot-1);
117 root=rt2;rt2=0;split(root,rt1,rt2,pos-1);
118 rec(rt2);root=merge(rt1,rt3);
119 }
120 void makesame(int pos,int tot,int val)
121 {
122 rt1=rt2=rt3=0;split(root,rt2,rt3,pos+tot-1);
123 root=rt2;rt2=0;split(root,rt1,rt2,pos-1);
124 int w=rt2;w[tag]=1;w[v]=val;w[sum]=val*w[sz];
125 if(val>=0)w[lsum]=w[rsum]=w[mx]=w[sum];
126 else w[lsum]=w[rsum]=0,w[mx]=val;
127 root=merge(rt1,rt2);root=merge(root,rt3);
128 }
129 void rever(int pos,int tot)
130 {
131 rt1=rt2=rt3=0;split(root,rt2,rt3,pos+tot-1);
132 root=rt2;rt2=0;split(root,rt1,rt2,pos-1);
133 int w=rt2;w[rev]^=1;swap(w[lc],w[rc]);swap(w[lsum],w[rsum]);
134 root=merge(rt1,rt2);root=merge(root,rt3);
135 }
136 void query(int pos,int tot)
137 {
138 rt1=rt2=rt3=0;split(root,rt2,rt3,pos+tot-1);
139 root=rt2;rt2=0;split(root,rt1,rt2,pos-1);
140 printf("%d\n",rt2[sum]);root=merge(rt1,rt2);root=merge(root,rt3);
141 }
142 int main()
143 {
144 n=read();m=read();cnt=N-5;
145 for(int i=1;i<=N-5;i++)id[i]=i;
146 for(int i=1;i<=n;i++)a[i]=read();
147 root=build(n);
148 while(m--)
149 {
150 scanf("%s",op);
151 if(op[0]!='M'||op[2]!='X')pos=read(),tot=read();
152 if(op[0]=='I')insert(pos,tot);
153 else if(op[0]=='D')erase(pos,tot);
154 else if(op[0]=='M')
155 {
156 if(op[2]=='X')printf("%d\n",root[mx]);
157 else val=read(),makesame(pos,tot,val);
158 }
159 else if(op[0]=='R')rever(pos,tot);
160 else query(pos,tot);
161 }
162 return 0;
163 } View Code
转载于:https://www.cnblogs.com/zsnuo/p/7906336.html