phpstudy建设网站视频教程,惠州网络推广,网站建设广告图,建网站免费空间[Submit][Status][Discuss]Description 请写一个程序#xff0c;要求维护一个数列#xff0c;支持以下 6 种操作#xff1a;请注意#xff0c;格式栏 中的下划线‘ _ ’表示实际输入文件中的空格Input 输入的第1 行包含两个数N 和M(M ≤20 000)#xff0c;N 表示初始时数列… [Submit][Status][Discuss] 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 题解Splay tree模板题 自己的板子 1 #includebits/stdc.h2 #define RI register int3 #define For(i,a,b) for (RI ia;ib;i)4 using namespace std;5 const int inf0x3f3f3f3f;6 const int N1e617;7 int n,m,rt,cnt;8 int a[N],id[N],fa[N],c[N][2];9 int sum[N],sz[N],v[N],mx[N],lx[N],rx[N];10 bool tag[N],rev[N];11 //tag表示是否有统一修改的标记rev表示是否有统一翻转的标记12 //sum表示这个点的子树中的权值和v表示这个点的权值13 //lx[]是一个子树以最左端为起点向右延伸的最大子串和,rx类似 14 //mx[]是当前子树的最大子串和15 queueint q;16 inline int read()17 {18 RI x0,f1;char chgetchar();19 while(ch0||ch9){if(ch-) f-1; chgetchar();}20 while(0chch9){x(x1)(x3)ch-0;chgetchar();}21 return x*f;22 }23 inline void pushup(RI x)24 {25 RI lc[x][0],rc[x][1];26 sum[x]sum[l]sum[r]v[x];27 sz[x]sz[l]sz[r]1;28 mx[x]max(mx[l],max(mx[r],rx[l]v[x]lx[r]));29 lx[x]max(lx[l],sum[l]v[x]lx[r]);30 rx[x]max(rx[r],sum[r]v[x]rx[l]);31 }32 //上传记录标记33 inline void pushdown(RI x)34 {35 RI lc[x][0],rc[x][1];36 if(tag[x])37 {38 rev[x]tag[x]0;//我们有了一个统一修改的标记再翻转就没有什么意义了39 if(l) tag[l]1,v[l]v[x],sum[l]v[x]*sz[l];40 if(r) tag[r]1,v[r]v[x],sum[r]v[x]*sz[r];41 if(v[x]0) 42 {43 if(l) lx[l]rx[l]mx[l]sum[l];44 if(r) lx[r]rx[r]mx[r]sum[r];45 }46 else47 {48 if(l) lx[l]rx[l]0,mx[l]v[x];49 if(r) lx[r]rx[r]0,mx[r]v[x];50 }51 }52 if(rev[x])53 {54 rev[x]0;rev[l]^1;rev[r]^1;55 swap(lx[l],rx[l]);swap(lx[r],rx[r]);56 //注意,在翻转操作中,前后缀的最大和子序列都反过来了 57 swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);58 }59 }60 inline void rotate(RI x,RI k)61 {62 RI yfa[x],zfa[y],l(c[y][1]x),rl^1;63 if (yk)kx;else c[z][c[z][1]y]x;64 fa[c[x][r]]y;fa[y]x;fa[x]z;65 c[y][l]c[x][r];c[x][r]y;66 pushup(y);pushup(x);67 //旋转操作,一定要上传标记且顺序不能变 68 }69 inline void splay(RI x,RI k)70 {71 while(x!k)72 {73 int yfa[x],zfa[y];74 if(y!k)75 {76 if((c[z][0]y)^(c[y][0]x)) rotate(x,k);77 else rotate(y,k);78 }79 rotate(x,k);80 }81 }82 //这是整个程序的核心之一毕竟是伸展操作嘛83 inline int find(RI x,RI rk)84 {//返回当前序列第rk个数的标号 85 pushdown(x);86 RI lc[x][0],rc[x][1];87 if(sz[l]1rk) return x;88 if(sz[l]rk) return find(l,rk);89 else return find(r,rk-sz[l]-1);90 }91 inline void recycle(RI x)92 {//这就是用时间换空间的回收冗余编号机制很好理解93 RI lc[x][0],rc[x][1];94 if(l) recycle(l);95 if(r) recycle(r);96 q.push(x);97 fa[x]lrtag[x]rev[x]0;98 }99 inline int split(RI k,RI tot)//找到[k1,ktot]
100 {
101 RI xfind(rt,k),yfind(rt,ktot1);
102 splay(x,rt);splay(y,c[x][1]);
103 return c[y][0];
104 }
105 //这个split操作是整个程序的核心之三
106 //我们通过这个split操作找到[k1,ktot]并把k,和ktot1移到根和右儿子的位置
107 //然后我们返回了这个右儿子的左儿子这就是我们需要操作的区间
108 inline void query(RI k,RI tot)
109 {
110 RI xsplit(k,tot);
111 printf(%d\n,sum[x]);
112 }
113 inline void modify(RI k,RI tot,RI val)//MAKE-SAME
114 {
115 RI xsplit(k,tot),yfa[x];
116 v[x]val;tag[x]1;sum[x]sz[x]*val;
117 if(val0) lx[x]rx[x]mx[x]sum[x];
118 else lx[x]rx[x]0,mx[x]val;
119 pushup(y);pushup(fa[y]);
120 //每一步的修改操作由于父子关系发生改变
121 //及记录标记发生改变我们需要及时上传记录标记
122 }
123 inline void rever(RI k,RI tot)//翻转
124 {
125 RI xsplit(k,tot),yfa[x];
126 if(!tag[x])
127 {
128 rev[x]^1;
129 swap(c[x][0],c[x][1]);
130 swap(lx[x],rx[x]);
131 pushup(y);pushup(fa[y]);
132 }
133 //同上
134 }
135 inline void erase(RI k,RI tot)//DELETE
136 {
137 RI xsplit(k,tot),yfa[x];
138 recycle(x);c[y][0]0;
139 pushup(y);pushup(fa[y]);
140 //同上
141 }
142 inline void build(RI l,RI r,RI f)
143 {
144 RI mid(lr)1,nowid[mid],preid[f];
145 if(lr)
146 {
147 mx[now]sum[now]a[l];
148 tag[now]rev[now]0;
149 //这里这个tag和rev的清0是必要因为这个编号可能是之前冗余了
150 lx[now]rx[now]max(a[l],0);
151 sz[now]1;
152 }
153 if(lmid) build(l,mid-1,mid);
154 if(midr) build(mid1,r,mid);
155 v[now]a[mid]; fa[now]pre;
156 pushup(now); //上传记录标记
157 c[pre][midf]now;
158 //当midf时now是插入到又区间取了所以c[pre][1]now当midf时同理
159 }
160 inline void insert(RI k,RI tot)
161 {
162 for(int i1;itot;i) a[i]read();
163 for(int i1;itot;i)
164 {
165 if(!q.empty()) id[i]q.front(),q.pop();
166 else id[i]cnt;//利用队列中记录的冗余节点编号
167 }
168 build(1,tot,0);
169 RI zid[(1tot)1];
170 RI xfind(rt,k1),yfind(rt,k2);
171 //首先依据中序遍历找到我们需要操作的区间的实际编号
172 splay(x,rt);splay(y,c[x][1]);
173 //把k1(注意我们已经右移了一个单位和(k1)1移到根和右儿子
174 fa[z]y;c[y][0]z;
175 //直接把需要插入的这个平衡树挂到右儿子的左儿子上去就好了
176 pushup(y);pushup(x);
177 //上传记录标记
178 }
179 //可以这么记只要用了split就要重新上传标记
180 //只有find中需要下传标记
181 int main()
182 {
183 nread(),mread();
184 mx[0]a[1]a[n2]-inf;
185 For(i,1,n) a[i1]read();
186 For(i,1,n2) id[i]i;//虚拟了两个节点1和n2然后把需要操作区间整体右移一个单位
187 build(1,n2,0);//建树
188 rt(n3)1;cntn2;//取最中间的为根
189 RI k,tot,val;char ch[10];
190 while(m--)
191 {
192 scanf(%s,ch);
193 if(ch[0]!M || ch[2]!X) kread(),totread();
194 if(ch[0]I) insert(k,tot);
195 if(ch[0]D) erase(k,tot);//DELETE
196 if(ch[0]M)
197 {
198 if(ch[2]X) printf(%d\n,mx[rt]);//MAX-SUM
199 else valread(),modify(k,tot,val);//MAKE-SAME
200 }
201 if(ch[0]R) rever(k,tot);//翻转
202 if(ch[0]G) query(k,tot);//GET-SUM
203 }
204 return 0;
205 } View Code 斌神的板子 1 /**************************************************************2 Problem: 15003 User: SongHL4 Language: C5 Result: Accepted6 Time:6152 ms7 Memory:26684 kb8 ****************************************************************/9 10 #includebits/stdc.h11 using namespace std;12 13 #define Key_value ch[ch[root][1]][0]14 const int MAXN 500010;15 const int INF 0x3f3f3f3f;16 int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN];17 int root,tot1;18 int sum[MAXN],rev[MAXN],same[MAXN];19 int lx[MAXN],rx[MAXN],mx[MAXN];20 int s[MAXN],tot2;//内存池和容量21 int a[MAXN];22 int n,q;23 24 void NewNode(int r,int father,int k)25 {26 if(tot2) r s[tot2--];//取的时候是tot2--,存的时候就是tot227 else r tot1;28 pre[r] father;29 ch[r][0] ch[r][1] 0;30 key[r] k;31 sum[r] k;32 rev[r] same[r] 0;33 lx[r] rx[r] mx[r] k;34 size[r] 1;35 }36 void Update_Rev(int r)37 {38 if(!r)return;39 swap(ch[r][0],ch[r][1]);40 swap(lx[r],rx[r]);41 rev[r] ^ 1;42 }43 void Update_Same(int r,int v)44 {45 if(!r)return;46 key[r] v;47 sum[r] v*size[r];48 lx[r] rx[r] mx[r] max(v,v*size[r]);49 same[r] 1;50 }51 void push_up(int r)52 {53 int lson ch[r][0], rson ch[r][1];54 size[r] size[lson] size[rson] 1;55 sum[r] sum[lson] sum[rson] key[r];56 lx[r] max(lx[lson],sum[lson] key[r] max(0,lx[rson]));57 rx[r] max(rx[rson],sum[rson] key[r] max(0,rx[lson]));58 mx[r] max(0,rx[lson]) key[r] max(0,lx[rson]);59 mx[r] max(mx[r],max(mx[lson],mx[rson]));60 }61 void push_down(int r)62 {63 if(same[r])64 {65 Update_Same(ch[r][0],key[r]);66 Update_Same(ch[r][1],key[r]);67 same[r] 0;68 }69 if(rev[r])70 {71 Update_Rev(ch[r][0]);72 Update_Rev(ch[r][1]);73 rev[r] 0;74 }75 }76 void Build(int x,int l,int r,int father)77 {78 if(l r)return;79 int mid (lr)/2;80 NewNode(x,father,a[mid]);81 Build(ch[x][0],l,mid-1,x);82 Build(ch[x][1],mid1,r,x);83 push_up(x);84 }85 void Init()86 {87 root tot1 tot2 0;88 ch[root][0] ch[root][1] size[root] pre[root] 0;89 same[root] rev[root] sum[root] key[root] 0;90 lx[root] rx[root] mx[root] -INF;91 NewNode(root,0,-1);92 NewNode(ch[root][1],root,-1);93 for(int i 0;i n;i)94 scanf(%d,a[i]);95 Build(Key_value,0,n-1,ch[root][1]);96 push_up(ch[root][1]);97 push_up(root);98 }99 //旋转,0为左旋1为右旋
100 void Rotate(int x,int kind)
101 {
102 int y pre[x];
103 push_down(y);
104 push_down(x);
105 ch[y][!kind] ch[x][kind];
106 pre[ch[x][kind]] y;
107 if(pre[y])
108 ch[pre[y]][ch[pre[y]][1]y] x;
109 pre[x] pre[y];
110 ch[x][kind] y;
111 pre[y] x;
112 push_up(y);
113 }
114 //Splay调整将r结点调整到goal下面
115 void Splay(int r,int goal)
116 {
117 push_down(r);
118 while(pre[r] ! goal)
119 {
120 if(pre[pre[r]] goal)
121 {
122 push_down(pre[r]);
123 push_down(r);
124 Rotate(r,ch[pre[r]][0] r);
125 }
126 else
127 {
128 push_down(pre[pre[r]]);
129 push_down(pre[r]);
130 push_down(r);
131 int y pre[r];
132 int kind ch[pre[y]][0]y;
133 if(ch[y][kind] r)
134 {
135 Rotate(r,!kind);
136 Rotate(r,kind);
137 }
138 else
139 {
140 Rotate(y,kind);
141 Rotate(r,kind);
142 }
143 }
144 }
145 push_up(r);
146 if(goal 0) root r;
147 }
148 int Get_kth(int r,int k)
149 {
150 push_down(r);
151 int t size[ch[r][0]] 1;
152 if(t k)return r;
153 if(t k)return Get_kth(ch[r][0],k);
154 else return Get_kth(ch[r][1],k-t);
155 }
156
157 //在第pos个数后面插入tot个数
158 void Insert(int pos,int tot)
159 {
160 for(int i 0;i tot;i)scanf(%d,a[i]);
161 Splay(Get_kth(root,pos1),0);
162 Splay(Get_kth(root,pos2),root);
163 Build(Key_value,0,tot-1,ch[root][1]);
164 push_up(ch[root][1]);
165 push_up(root);
166 }
167
168 //删除子树
169 void erase(int r)
170 {
171 if(!r)return;
172 s[tot2] r;
173 erase(ch[r][0]);
174 erase(ch[r][1]);
175 }
176 //从第pos个数开始连续删除tot个数
177 void Delete(int pos,int tot)
178 {
179 Splay(Get_kth(root,pos),0);
180 Splay(Get_kth(root,postot1),root);
181 erase(Key_value);
182 pre[Key_value] 0;
183 Key_value 0;
184 push_up(ch[root][1]);
185 push_up(root);
186 }
187 //将从第pos个数开始的连续的tot个数修改为c
188 void Make_Same(int pos,int tot,int c)
189 {
190 Splay(Get_kth(root,pos),0);
191 Splay(Get_kth(root,postot1),root);
192 Update_Same(Key_value,c);
193 push_up(ch[root][1]);
194 push_up(root);
195 }
196
197 //将第pos个数开始的连续tot个数进行反转
198 void Reverse(int pos,int tot)
199 {
200 Splay(Get_kth(root,pos),0);
201 Splay(Get_kth(root,postot1),root);
202 Update_Rev(Key_value);
203 push_up(ch[root][1]);
204 push_up(root);
205 }
206 //得到第pos个数开始的tot个数的和
207 int Get_Sum(int pos,int tot)
208 {
209 Splay(Get_kth(root,pos),0);
210 Splay(Get_kth(root,postot1),root);
211 return sum[Key_value];
212 }
213 //得到第pos个数开始的tot个数中最大的子段和
214 int Get_MaxSum(int pos,int tot)
215 {
216 Splay(Get_kth(root,pos),0);
217 Splay(Get_kth(root,postot1),root);
218 return mx[Key_value];
219 }
220
221 void InOrder(int r)
222 {
223 if(!r)return;
224 push_down(r);
225 InOrder(ch[r][0]);
226 printf(%d ,key[r]);
227 InOrder(ch[r][1]);
228 }
229
230
231
232 int main()
233 {
234 while(scanf(%d%d,n,q) 2)
235 {
236 Init();
237 char op[20];
238 int x,y,z;
239 while(q--)
240 {
241 scanf(%s,op);
242 if(strcmp(op,INSERT) 0)
243 {
244 scanf(%d%d,x,y);
245 Insert(x,y);
246 }
247 else if(strcmp(op,DELETE) 0)
248 {
249 scanf(%d%d,x,y);
250 Delete(x,y);
251 }
252 else if(strcmp(op,MAKE-SAME) 0)
253 {
254 scanf(%d%d%d,x,y,z);
255 Make_Same(x,y,z);
256 }
257 else if(strcmp(op,REVERSE) 0)
258 {
259 scanf(%d%d,x,y);
260 Reverse(x,y);
261 }
262 else if(strcmp(op,GET-SUM) 0)
263 {
264 scanf(%d%d,x,y);
265 printf(%d\n,Get_Sum(x,y));
266 }
267 else if(strcmp(op,MAX-SUM) 0)
268 printf(%d\n,Get_MaxSum(1,size[root]-2));
269 }
270 }
271 return 0;
272 } View Code 转载于:https://www.cnblogs.com/songorz/p/9808010.html
