ftp给网站做备份,公司简介模板免费ppt,建设商城网站视频教学,wordpress淘宝客单页模板下载【BZOJ1500】[NOI2005]维修数列 Description Input 输入的第1 行包含两个数N 和M(M ≤20 000)#xff0c;N 表示初始时数列中数的个数#xff0c;M表示要进行的操作数目。第2行包含N个数字#xff0c;描述初始时的数列。以下M行#xff0c;每行一条命令#xff0c;格式参见…【BZOJ1500】[NOI2005]维修数列 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 题解裸的Splay只不过全是细节我还是不够细啊~ *要开滚动数组记录有哪些空余的位置防止MLE但实测600000的数组就行 *INSERT直接一个一个往里加就行加成一条链也无所谓不会TLE *DELETE因为要释放空间所以必须一个一个删除递归即可 *MAKE_SAME没啥说的*REVERSE最好是先修改再给儿子打标记也就是说标记只对儿子起作用这样比较清晰 *GET_SUM没啥说的*MAX_SUM巨恶心的pushup和pushdown看代码就知道了 #include cstdio
#include cstring
#include iostream
#include queue
using namespace std;
struct point
{int ch[2],fa,siz,tag,v,sv,sm,ls,rs,re;
}s[600010];
int n,m,root;
int num[500010];
char str[20];
queueint q;
void pushdown(int x)
{if(s[x].re){swap(s[s[x].ch[0]].ch[0],s[s[x].ch[0]].ch[1]);swap(s[s[x].ch[1]].ch[0],s[s[x].ch[1]].ch[1]);swap(s[s[x].ch[0]].ls,s[s[x].ch[0]].rs);swap(s[s[x].ch[1]].ls,s[s[x].ch[1]].rs);if(s[x].ch[0]) s[s[x].ch[0]].re^1;if(s[x].ch[1]) s[s[x].ch[1]].re^1;s[x].re0;}if(s[x].tag!130){if(s[x].ch[0]){s[s[x].ch[0]].vs[s[x].ch[0]].tags[x].tag;s[s[x].ch[0]].svs[x].tag*s[s[x].ch[0]].siz;s[s[x].ch[0]].lss[s[x].ch[0]].rsmax(s[s[x].ch[0]].sv,0);s[s[x].ch[0]].smmax(s[s[x].ch[0]].sv,s[x].tag);}if(s[x].ch[1]){s[s[x].ch[1]].vs[s[x].ch[1]].tags[x].tag;s[s[x].ch[1]].svs[x].tag*s[s[x].ch[1]].siz;s[s[x].ch[1]].lss[s[x].ch[1]].rsmax(s[s[x].ch[1]].sv,0);s[s[x].ch[1]].smmax(s[s[x].ch[1]].sv,s[x].tag);}s[x].tag130;}
}
void pushup(int x)
{s[x].sizs[s[x].ch[0]].sizs[s[x].ch[1]].siz1;s[x].lsmax(s[s[x].ch[0]].ls,s[s[x].ch[0]].svs[x].vs[s[x].ch[1]].ls);s[x].rsmax(s[s[x].ch[1]].rs,s[s[x].ch[1]].svs[x].vs[s[x].ch[0]].rs);s[x].smmax(s[s[x].ch[0]].rss[x].vs[s[x].ch[1]].ls,max(s[s[x].ch[0]].sm,s[s[x].ch[1]].sm));s[x].svs[s[x].ch[0]].svs[x].vs[s[x].ch[1]].sv;
}
int readin()
{int ret0,f1; char gcgetchar();while(gc0||gc9){if(gc-)f-f; gcgetchar();}while(gc0gc9) retret*10gc-0,gcgetchar();return ret*f;
}
int rotate(int x,int k)
{int ys[x].fa,zs[y].fa,d(xs[y].ch[1]);if(z) s[z].ch[ys[z].ch[1]]x;if(yk) kx;s[x].faz,s[y].fax,s[y].ch[d]s[x].ch[d^1];if(s[x].ch[d^1]) s[s[x].ch[d^1]].fay;s[x].ch[d^1]y;pushup(y),pushup(x);
}
void splay(int x,int k)
{while(x!k){int ys[x].fa,zs[y].fa;if(y!k){if((xs[y].ch[1])^(ys[z].ch[1])) rotate(x,k);else rotate(y,k);}rotate(x,k);}
}
void build(int l,int r,int last)
{if(lr) return ;int midlr1;s[mid].falast,s[last].ch[midlast]mid;s[mid].vnum[mid];s[mid].tag130;build(l,mid-1,mid),build(mid1,r,mid);pushup(mid);
}
int find(int x,int y)
{pushdown(x);if(s[s[x].ch[0]].siz1y) return x;if(ys[s[x].ch[0]].siz) return find(s[x].ch[0],y);return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);
}
void del(int x)
{if(!x) return;q.push(x);del(s[x].ch[0]),del(s[x].ch[1]);x0;
}
int main()
{nreadin(),mreadin();int i,j,a,b,c,t,u;s[0].smnum[1]num[n2]-130;for(i1;in;i) num[i1]readin();n2,root(n1)/2;build(1,root-1,root),build(root1,n,root);s[root].vnum[root];s[root].tag130;pushup(root);for(in1;i600000;i) q.push(i);for(i1;im;i){scanf(%s,str);switch(str[2]){case S:{areadin()1,breadin();splay(find(root,a1),root),splay(find(root,a),s[root].ch[0]);ts[root].ch[0];for(j1;jb;j){creadin();uq.front(),q.pop();s[u].vc;s[t].ch[1]u,s[u].fat;s[u].re0,s[u].tag130;tu;}while(t!root){pushup(t);ts[t].fa;}break;}case L:{areadin()1,breadin();splay(find(root,a-1),root),splay(find(root,ab),s[root].ch[1]);del(s[s[root].ch[1]].ch[0]);pushup(s[root].ch[1]);break;}case K:{areadin()1,breadin();splay(find(root,a-1),root),splay(find(root,ab),s[root].ch[1]);cs[s[root].ch[1]].ch[0];s[c].vs[c].tagreadin();s[c].re0;s[c].svs[c].siz*s[c].v;s[c].lss[c].rsmax(s[c].sv,0);s[c].smmax(s[c].sv,s[c].v);break;}case V:{areadin()1,breadin();splay(find(root,a-1),root),splay(find(root,ab),s[root].ch[1]);cs[s[root].ch[1]].ch[0];swap(s[c].ch[0],s[c].ch[1]);swap(s[c].ls,s[c].rs);s[c].re1;break;}case T:{areadin()1,breadin();splay(find(root,a-1),root),splay(find(root,ab),s[root].ch[1]);printf(%d\n,s[s[s[root].ch[1]].ch[0]].sv);break;}case X:{printf(%d\n,s[root].sm);break;}}}return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/6440275.html
