崇明手机网站建设,深圳服务好的网站建设,农村电商平台,成都建设网站公司简介传送门 debug到死2333. 虽然说是splay维护序列模板#xff0c;作为蒟蒻的我还是GG %%%考场A的dalao Orz Orz. 其实不开long long也行#xff0c;inf开成0x3f3f3f3f也可#xff08;flag,欢迎推翻#xff09; 就当存个板子吧. #includebits/stdc.h
#includecs… 传送门 debug到死2333. 虽然说是splay维护序列模板作为蒟蒻的我还是GG %%%考场A的dalao Orz Orz. 其实不开long long也行inf开成0x3f3f3f3f也可flag,欢迎推翻 就当存个板子吧. #includebits/stdc.h
#includecstdio
#includecmath
#includecstring
#includecstdlib
#includealgorithm
#includequeue
#includedeque
#includelist
#includeset
#includevector
#includeiostream
#define ll long long
#define re register
#define inf 0x7f7f7f7f
#define inl inline
#define sqr(x) (x*x)
#define max(a,b) (ab?a:b)
//#define eps 1e-8
#define debug puts(**************************);
//#pragma comment(linker, /STACK:1024000000,1024000000)
//#pragma GCC optimize (2)
//#pragma G optimize (2)
using namespace std;
//const ll mod;
const ll MAXN1e610;
inl ll read() {re ll x 0; re int f 1;char ch getchar();while(ch0||ch9) { if(ch - ) f -1; ch getchar(); }while(ch0ch9) {x(x1)(x3)(ch^48);chgetchar();}return x * f;
}
inl char readc() {char chgetchar();while((zch||cha)(Zch||chA)) chgetchar();return ch;
}
inl void write(re ll x){if(x10)write(x/10);putchar(x%100);
}
inl void writeln(re ll x){if(x0) {x-x;putchar(-);}write(x); puts();
}
inl ll gcd(re ll x,re ll y){while(y^x^y^x%y);return x;}
inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;}
inl void FR() {freopen(.in,r,stdin);freopen(.out,w,stdout);
}
inl void FC() {fclose(stdin);fclose(stdout);
}
ll root,id[MAXN],cnt;
struct Node {ll fa,son[2],sumx,val,siz,maxx,lx,rx;bool rev,flag;void clear() {fason[0]son[1]sumxvalsizmaxxlxrxrevflag0;}
}Tree[MAXN];
ll dir(ll x) {return Tree[Tree[x].fa].son[1]x;}
inl void pushup(ll x) {re ll lTree[x].son[0],rTree[x].son[1];Tree[x].sizTree[l].sizTree[r].siz1;Tree[x].sumxTree[l].sumxTree[r].sumxTree[x].val;Tree[x].maxxmax(Tree[r].maxx,Tree[l].maxx);Tree[x].maxxmax(Tree[x].maxx,Tree[l].rxTree[r].lxTree[x].val);Tree[x].lxmax(Tree[l].lx,Tree[l].sumxTree[x].valTree[r].lx);Tree[x].rxmax(Tree[r].rx,Tree[r].sumxTree[x].valTree[l].rx);
}
inl void pushdown(ll x) {re ll lTree[x].son[0],rTree[x].son[1];if(Tree[x].flag) {Tree[x].flagTree[x].rev0;if(l) Tree[l].valTree[x].val,Tree[l].sumxTree[l].val*Tree[l].siz,Tree[l].flag1;if(r) Tree[r].valTree[x].val,Tree[r].sumxTree[r].val*Tree[r].siz,Tree[r].flag1;if(Tree[x].val0) {if(l) Tree[l].lxTree[l].rxTree[l].maxxTree[l].sumx;if(r) Tree[r].lxTree[r].rxTree[r].maxxTree[r].sumx;}else {if(l) Tree[l].lxTree[l].rx0,Tree[l].maxxTree[l].val;if(r) Tree[r].lxTree[r].rx0,Tree[r].maxxTree[r].val;}}if(Tree[x].rev) {Tree[x].rev0;Tree[l].rev^1;Tree[r].rev^1;swap(Tree[l].lx,Tree[l].rx);swap(Tree[r].lx,Tree[r].rx);swap(Tree[l].son[0],Tree[l].son[1]);swap(Tree[r].son[0],Tree[r].son[1]);}
}
inl void rotate(ll x) {re ll yTree[x].fa,zTree[y].fa,odir(x);re ll sodir(y);Tree[y].son[o]Tree[x].son[o^1];Tree[Tree[y].son[o]].fay;Tree[x].son[o^1]y;Tree[y].fax;Tree[z].son[so]x;Tree[x].faz;pushup(y);pushup(x);
}
inl void splay(ll x,ll goal) {for(re ll y;(yTree[x].fa)!goal;rotate(x)) {if(Tree[y].fa!goal) rotate(dir(y)dir(x)?y:x);}if(!goal) rootx;
}
inl ll find(ll x,ll rk) {pushdown(x);re ll lTree[x].son[0],rTree[x].son[1];if(Tree[l].siz1rk) return x;else if(Tree[l].sizrk) return find(l,rk);else return find(r,rk-Tree[l].siz-1);
}
ll s[MAXN];
inl ll build(ll l,ll r,ll fro) {re ll mid(lr)1,tid[mid];Tree[t].clear();Tree[t].vals[mid];Tree[t].fafro;if(lr) {Tree[t].lxTree[t].rxmax(0,Tree[t].val);Tree[t].maxxTree[t].sumxTree[t].val;Tree[t].son[0]Tree[t].son[1]0;Tree[t].siz1;return t;}if(lmid) Tree[t].son[0]build(l,mid-1,t);else Tree[t].son[0]0;if(midr) Tree[t].son[1]build(mid1,r,t);else Tree[t].son[1]0;pushup(t);return t;
}
char ss[20];
queuellQ;
inl void insert(ll pos,ll tot) {for(re ll i1;itot;i) s[i]read();for(re ll i1;itot;i) {if(!Q.empty()) id[i]Q.front(),Q.pop();else id[i]cnt;}re ll lfind(root,pos1),rfind(root,pos2);splay(l,0);splay(r,l);Tree[r].son[0]build(1,tot,r);pushup(r);pushup(l);
}
inl void recycle(ll x) {re ll lTree[x].son[0],rTree[x].son[1];if(l) recycle(l);if(r) recycle(r);Q.push(x);Tree[x].clear();lr0;
}
inl ll split(ll pos,ll tot) {re ll xfind(root,pos),yfind(root,postot1);splay(x,0);splay(y,x);return Tree[y].son[0];
}
inl void del(ll pos,ll tot) {re ll xsplit(pos,tot),yTree[x].fa;recycle(x);Tree[y].son[0]0;pushup(y);pushup(Tree[y].fa);
}
inl void modify(ll pos,ll tot,ll val) {re ll xsplit(pos,tot),yTree[x].fa;Tree[x].flag1;Tree[x].valval,Tree[x].sumxTree[x].siz*Tree[x].val;if(Tree[x].val0) Tree[x].lxTree[x].rxTree[x].maxxTree[x].sumx;else Tree[x].lxTree[x].rx0,Tree[x].maxxTree[x].val;pushup(y);pushup(Tree[y].fa);
}
inl void rever(ll pos,ll tot) {re ll xsplit(pos,tot),yTree[x].fa;if(!Tree[x].flag) {Tree[x].rev^1;swap(Tree[x].lx,Tree[x].rx);swap(Tree[x].son[0],Tree[x].son[1]);pushup(y);pushup(Tree[y].fa);}
}
inl ll query(ll pos,ll tot) {re ll xsplit(pos,tot);return Tree[x].sumx;
}
int main() {
// FR();re ll nread(),mread();for(re ll i1;in;i) {s[i1]read();}Tree[0].maxxs[1]s[n2]-inf;cntn2;for(re ll i1;in2;i) id[i]i;rootbuild(1,n2,0);for(re ll i1;im;i) {scanf(%s,ss);if(ss[0]I) {re ll posread(),totread();insert(pos,tot);}else if(ss[0]D) {re ll posread(),totread();del(pos,tot);}else if(ss[0]M) {if(ss[2]X) writeln(Tree[root].maxx);else {re ll posread(),totread(),valread();modify(pos,tot,val);}}else if(ss[0]R) {re ll posread(),totread();rever(pos,tot);}else if(ss[0]G) {re ll posread(),totread();writeln(query(pos,tot));}}
// FC();return 0;
} 转载于:https://www.cnblogs.com/20020723YJX/p/9520947.html
