首页 > 代码库 > SPOJ GSS6 4487. Can you answer these queries VI (SPLAY)
SPOJ GSS6 4487. Can you answer these queries VI (SPLAY)
题目大意:
四个操作:
I X Y 在x位置插入y
D x 删除x位置的数
R x y 用y替换x位置上的数字
Q x y 求出[x,y]上的最大子序列的和。
思路分析:
对于动态维护序列肯定是splay了。
现在就考虑以下几个问题。
之前我们知道线段树处理连续的子序列的和是用区间合并的。那splay上怎么做。
考虑边界,如儿子为 0 或者是冗余节点怎么办?
初始化的时候将值赋成什么。
仔细考虑这些就能减少代码量。
注意replace的时候,要去找到然后直接修改,如果先旋转的话就会造成超时。
#include <cstdio> #include <iostream> #define maxn 222222 #define keyTree (ch[ch[root][1]][0]) using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; char CHAR() { char res; while (res = getchar(), !isalpha(res)); return res; } inline void scanf_(int &num) { char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-') { neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; } inline void printf_(int num) { bool flag=false; if(num<0) { putchar('-'); num=-num; } int ans[10],top=0; while(num!=0) { ans[top++]=num%10; num/=10; } if(top==0) putchar('0'); for(int i=top-1; i>=0; i--) { char ch=ans[i]+'0'; putchar(ch); } } int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn]; int root,top1,top2; /*以上变量为Splay固有的*/ int sum[maxn],lmax[maxn],rmax[maxn],res[maxn],val[maxn],a[maxn]; void New(int &x,int PRE,int v) { if(top2)x=S[--top2]; else x=++top1; ch[x][0]=ch[x][1]=0; siz[x]=1; pre[x]=PRE; /*special*/ sum[x]=lmax[x]=rmax[x]=val[x]=res[x]=v; } void pushup(int x)/*special*/ { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; int ls=ch[x][0],rs=ch[x][1]; lmax[x]=lmax[ls],rmax[x]=rmax[rs],sum[x]=val[x]+sum[ls]+sum[rs]; lmax[x]=max(lmax[x],max(sum[ls]+val[x],sum[ls]+val[x]+lmax[rs])); rmax[x]=max(rmax[x],max(sum[rs]+val[x],sum[rs]+val[x]+rmax[ls])); res[x]=max(max(0,rmax[ls])+val[x]+max(0,lmax[rs]),max(res[ls],res[rs])); } void pushdown(int x)/*special*/ { } void build(int &x,int s,int e,int f) { if(s>e)return; int mid=(s+e)>>1; New(x,f,a[mid]); if(s<mid)build(ch[x][0],s,mid-1,x); if(e>mid)build(ch[x][1],mid+1,e,x); pushup(x); } void Rotate(int x,int kind) { int y=pre[x]; pushdown(x); pushdown(y); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; pushup(y); } void Splay(int x,int goal) { pushdown(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x) { Rotate(x,!kind); Rotate(x,kind); } else { Rotate(y,kind); Rotate(x,kind); } } } pushup(x); if(goal==0)root=x; } void RotateTo(int k,int goal) { int r=root; pushdown(r); while(siz[ch[r][0]]!=k) { if(k<siz[ch[r][0]]) { r=ch[r][0]; } else { k-=siz[ch[r][0]]+1; r=ch[r][1]; } pushdown(r); } Splay(r,goal); } void erase(int x) { int y=pre[x]; int head=0,tail=0; for(que[tail++]=x; head<tail; head++) { S[top2++]=que[head]; if(ch[que[head]][0])que[tail++]=ch[que[head]][0]; if(ch[que[head]][1])que[tail++]=ch[que[head]][1]; } ch[y][ch[y][1]==x]=0; pushup(y); } void init(int n)/*special*/ { root=top1=top2=0; ch[0][0]=ch[0][1]=siz[0]=pre[0]=sum[0]=0; lmax[0]=rmax[0]=val[0]=res[0]=-inf; New(root,0,-inf); New(ch[root][1],root,-inf); siz[root]=2; for(int i=0; i<n; i++)scanf_(a[i]); build(keyTree,0,n-1,ch[root][1]); pushup(ch[root][1]); pushup(root); } void insert(int pos,int val) { RotateTo(pos-1,0); RotateTo(pos,root); New(keyTree,ch[root][1],val); pushup(ch[root][1]); pushup(root); } void Delete(int pos) { RotateTo(pos-1,0); RotateTo(pos+1,root); erase(keyTree); pushup(ch[root][1]); pushup(root); } int get(int k,int x) { while(k!=siz[ch[x][0]]) { if(k<siz[ch[x][0]])x=ch[x][0]; else { k-=siz[ch[x][0]]+1; x=ch[x][1]; } } return x; } void replace(int pos,int v) { int x=get(pos,root); val[x]=v; Splay(x,0); } int query(int l,int r) { RotateTo(l-1,0); RotateTo(r+1,root); return res[keyTree]; } int main() { int n; scanf("%d",&n); init(n); int m; scanf("%d",&m); while(m--) { char str; str=CHAR(); int l,r; if(str=='I')scanf_(l),scanf_(r),insert(l,r); else if(str=='D')scanf_(l),Delete(l); else if(str=='R')scanf_(l),scanf_(r),replace(l,r); else scanf_(l),scanf_(r),printf_(query(l,r)),puts(""); } return 0; }
SPOJ GSS6 4487. Can you answer these queries VI (SPLAY)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。