首页 > 代码库 > spoj 4487. Can you answer these queries VI splay 常数优化
spoj 4487. Can you answer these queries VI splay 常数优化
4487. Can you answer these queries VIProblem code: GSS6 |
Given a sequence A of N (N <= 100000) integers, you have to apply Q (Q <= 100000) operations:
Insert, delete, replace an element, find the maximum contiguous(non empty) sum in a given interval.
Input
The first line of the input contains an integer N.
The following line contains N integers, representing the starting
sequence A1..AN, (|Ai| <= 10000).
The third line contains an integer Q. The next Q lines contains the operations in following form:
I x y: insert element y at position x (between x - 1 and x).
D x : delete the element at position x.
R x y: replace element at position x with y.
Q x y: print max{Ai + Ai+1 + .. + Aj | x <= i <= j <= y}.
All given positions are valid, and given values are between -10000 and +10000.
The sequence will never be empty.
Output
For each "Q" operation, print an integer(one per line) as described above.
Example
Input:
5
3 -4 3 -1 6
10
I 6 2
Q 3 5
R 5 -4
Q 3 5
D 2
Q 1 5
I 2 -10
Q 1 6
R 2 -1
Q 1 6
Output:
8
3
6
3
5
第二次写splay居然遇上了考splay的常数优化。弄了很久。首先是读入优化，貌似SPOJ上面数据有‘\r‘所以要特殊判断。然后inline所有函数，最后把splay移到一个struct里面会加速很多。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 110000#define MAXV MAXN*2#define MAXE MAXV*2#define MAXT MAXN*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLL#define lch splay[now].ch[0]#define rch splay[now].ch[1]typedef long long qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=(char)getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=(char)getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}int n,m;int root=0,topt=0;;struct sss{ int lx,rx,mx,val,sum,siz,pnt; int ch[2];}splay[MAXT];inline void up(int now){ splay[now].lx=splay[now].rx=splay[now].mx=-INF; if (lch)splay[now].lx=max(splay[now].lx,splay[lch].lx); splay[now].lx=max(splay[now].lx,max(splay[lch].sum+splay[now].val,splay[lch].sum+splay[now].val+splay[rch].lx)); if (rch)splay[now].rx=max(splay[now].rx,splay[rch].rx); splay[now].rx=max(splay[now].rx,max(splay[rch].sum+splay[now].val,splay[rch].sum+splay[now].val+splay[lch].rx)); splay[now].mx=splay[now].val; if (lch)splay[now].mx=max(splay[now].mx,splay[lch].mx); if (rch)splay[now].mx=max(splay[now].mx,splay[rch].mx); splay[now].mx=max(splay[now].mx,splay[lch].rx+splay[rch].lx+splay[now].val); splay[now].mx=max(splay[now].mx,splay[rch].lx+splay[now].val); splay[now].mx=max(splay[now].mx,splay[lch].rx+splay[now].val); splay[now].siz=splay[lch].siz+splay[rch].siz+1; splay[now].sum=splay[lch].sum+splay[rch].sum+splay[now].val;}inline void Rotate(int now){ int p=splay[now].pnt,anc=splay[p].pnt; int dir=splay[p].ch[0]==now; if (anc) splay[anc].ch[splay[anc].ch[1]==p]=now; splay[now].pnt=anc; splay[splay[now].ch[dir]].pnt=p; splay[p].ch[1-dir]=splay[now].ch[dir]; splay[p].pnt=now; splay[now].ch[dir]=p; up(p); up(now);}/*inline int Get_kth(int now,int rk){ if (rk==siz[splay[now].ch[0]]+1) return now; if (rk<siz[splay[now].ch[0]]+1) return Get_kth(splay[now].ch[0],rk); else return Get_kth(splay[now].ch[1],rk-siz[splay[now].ch[0]]-1);}*/inline int Get_kth(int rk){ int now=root; while (rk!=splay[splay[now].ch[0]].siz+1) { if (rk>splay[splay[now].ch[0]].siz+1) { rk-=splay[splay[now].ch[0]].siz+1; now=splay[now].ch[1]; }else { now=splay[now].ch[0]; } } return now;}inline void Splay(int now,int tp=0){ if (now==tp)return ; while (splay[now].pnt!=tp) { int p=splay[now].pnt,anc=splay[p].pnt; if (anc==tp) Rotate(now); else if( (splay[anc].ch[0]==p) == (splay[p].ch[0]==now)) { Rotate(p); Rotate(now); }else { Rotate(now); Rotate(now); } } if (tp==0)root=now;}inline void Insert(int pos,int v){ int now=++topt; splay[now].ch[0]=splay[now].ch[1]=0; splay[now].pnt=0; splay[now].val=v; splay[now].siz=1; splay[now].lx=splay[now].rx=splay[now].mx=splay[now].sum=v; if (!pos) { Splay(Get_kth(1)); splay[now].ch[1]=root; splay[root].pnt=now; root=now; up(now); return ; } Splay(Get_kth(pos)); splay[now].pnt=root; splay[now].ch[1]=splay[root].ch[1]; splay[splay[root].ch[1]].pnt=now; splay[root].ch[1]=now; up(now); up(root); return ;}inline void Delete(int pos){ Splay(Get_kth(pos)); if (pos!=splay[root].siz) { Splay(Get_kth(pos+1),root);/**/ splay[splay[root].ch[1]].ch[0]=splay[root].ch[0]; splay[splay[root].ch[0]].pnt=splay[root].ch[1];; splay[splay[root].ch[1]].pnt=splay[root].pnt; root=splay[root].ch[1]; }else { root=splay[root].ch[0]; splay[root].pnt=0; } up(root);}inline int Qry_mxs(int l,int r){ if (l==1 && r==splay[root].siz) { return splay[root].mx; }else if (l==1) { Splay(Get_kth(r+1)); return splay[splay[root].ch[0]].mx; }else if (r==splay[root].siz) { Splay(Get_kth(l-1)); return splay[splay[root].ch[1]].mx; }else { Splay(Get_kth(l-1)); Splay(Get_kth(r+1),root); return splay[splay[splay[root].ch[1]].ch[0]].mx; }}inline void Chg_val(int pos,int v){ Splay(Get_kth(pos)); splay[root].val=v; up(root);}void Scan(int now){ if (!now)return ; if (splay[now].siz!=splay[lch].siz+splay[rch].siz+1)throw 2; if (splay[now].ch[0]) { if (splay[splay[now].ch[0]].pnt!=now)throw 1; Scan(splay[now].ch[0]); } printf("%d ",splay[now].val); if (splay[now].ch[1]) { if (splay[splay[now].ch[1]].pnt!=now)throw 1; Scan(splay[now].ch[1]); }}void Build_tree(int &now,int *num,int l,int r){ now=++topt; int mid=(l+r)>>1; splay[now].siz=1; splay[now].sum=splay[now].val=splay[now].mx=splay[now].lx=splay[now].rx=num[mid]; if (l<=mid-1)Build_tree(lch,num,l,mid-1); if (mid+1<=r)Build_tree(rch,num,mid+1,r); splay[lch].pnt=now; splay[rch].pnt=now; up(now);}int num[MAXN];int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i,j,k; int x,y,z; scanf("%d",&n); for (i=0;i<n;i++) { x=nextInt(); num[i]=x; } Build_tree(root,num,0,n-1); scanf("%d\n",&m); char opt; for (i=0;i<m;i++) { opt=getchar(); //scanf("%c",&opt); if (opt==‘I‘) { // scanf("%d%d",&x,&y); x=nextInt();y=nextInt(); x--; Insert(x,y); }else if (opt==‘Q‘) { // scanf("%d%d",&x,&y); x=nextInt();y=nextInt(); printf("%d\n",Qry_mxs(x,y)); }else if (opt==‘R‘) { // scanf("%d%d",&x,&y); x=nextInt();y=nextInt(); Chg_val(x,y); }else if (opt==‘D‘) { // scanf("%d",&x); x=nextInt(); Delete(x); } getchar(); } return 0;}
spoj 4487. Can you answer these queries VI splay 常数优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。