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上面数据有' '所以要特殊判断。然后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 ",&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 ",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; }