poj 3468 A Simple Problem with Integers (Splay树)

发布时间:2017-1-17 16:48:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3468 A Simple Problem with Integers (Splay树)",主要涉及到poj 3468 A Simple Problem with Integers (Splay树)方面的内容,对于poj 3468 A Simple Problem with Integers (Splay树)感兴趣的同学可以参考一下。

A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 48548   Accepted: 14366 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval. Input The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab. Output You need to answer all Q commands in order. One answer in a line. Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15 Hint The sums may exceed the range of 32-bit integers. Source POJ Monthly--2007.11.25, Yang Yi 题意:自己看~ 思路:简单的水题,仅当Splay树练练手。。。PS:注意Splay树是怎么建立的 感受:Splay树的系数还是挺大的,线段树跑这题2000+MS,而Splay跑了4000+MS #include<iostream> #include<cstdio> #include<cstring> //Lint #if defined (_WIN32) || defined (__WIN32) || defined (WIN32) || defined (__WIN32__) #define LL __int64 #define LLS "%" "I" "6" "4" "d" #else #define LL long long #define LLS "%" "l" "l" "d" #endif #define N 100005 #define KeyNode ch[ch[rt][1]][0] using namespace std; int c,id,rt; int pre[N],ch[N][2],size[N],val[N],add[N]; LL sum[N]; void Treaval(int x){ if(x){ Treaval(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d , sum = %2lld \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x],sum[x]); Treaval(ch[x][1]); } } void debug(){ printf("%d\n",rt); Treaval(rt); } //以上Debug void Pushup(int x){ size[x]=1+size[ch[x][0]]+size[ch[x][1]]; sum[x]=add[x]+val[x]+sum[ch[x][0]]+sum[ch[x][1]]; } void Pushdown(int x){ if(add[x]){ val[x]+=add[x]; add[ch[x][0]]+=add[x]; add[ch[x][1]]+=add[x]; sum[ch[x][0]]+=(LL)add[x]*size[ch[x][0]]; sum[ch[x][1]]+=(LL)add[x]*size[ch[x][1]]; add[x]=0; } } void Rotate(int x,int f){ int y=pre[x]; Pushdown(y); Pushdown(x); ch[y][!f]=ch[x][f]; pre[ch[x][f]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; pre[y]=x; ch[x][f]=y; Pushup(y); } void Splay(int x,int goal){ while(pre[x]!=goal){ if(pre[pre[x]]==goal){ Rotate(x,ch[pre[x]][0]==x); } else{ int y=pre[x]; int z=pre[y]; int f=(ch[z][0]==y); if(ch[y][f]==x){ Rotate(x,!f); Rotate(x,f); } else{ Rotate(y,f); Rotate(x,f); } } } if(goal==0)rt=x; Pushup(x); } void RotateTo(int k,int goal){ int x=rt; Pushdown(x); while(size[ch[x][0]]!=k){ if(size[ch[x][0]]>k)x=ch[x][0]; else{ k=k-size[ch[x][0]]-1; x=ch[x][1]; } Pushdown(x); } Splay(x,goal); } void NewNode(int x,int c,int fa){ pre[x]=fa; val[x]=c; sum[x]=c; add[x]=0; size[x]=1; } void Build(int &x,int l,int r,int fa){ if(l>r) return; int m=(l+r)>>1; x=++id; Build(ch[x][0],l,m-1,x); scanf("%d",&c); NewNode(x,c,fa); Build(ch[x][1],m+1,r,x); Pushup(x); } void init(int n){ rt=id=0; memset(ch,0,sizeof(ch)); rt=++id; NewNode(rt,0,0); ch[rt][1]=++id; NewNode(ch[rt][1],0,rt); size[rt]=2; Build(KeyNode,1,n,ch[rt][1]); Pushup(ch[rt][1]); Pushup(rt); } int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ init(n); //debug(); while(m--){ char opt[1]; int l,r; scanf("%s%d%d",opt,&l,&r); if(opt[0]=='Q'){ RotateTo(l-1,0); RotateTo(r+1,rt); printf(LLS"\n",sum[KeyNode]); } else { RotateTo(l-1,0); RotateTo(r+1,rt); scanf("%d",&c); add[KeyNode]+=c; sum[KeyNode]+=(LL)size[KeyNode]*c; } } } }

上一篇:Android JNI开发入门之二