首页 > 代码库 > Splay练习题 [POJ 3468] A Simple Problem with Integers
Splay练习题 [POJ 3468] A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 64372 | Accepted: 19813 | |
| 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 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4
Sample Output
455915
Hint
/* 注意用64位整形、其他没什么的 */#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 101000#define ll __int64ll num[N];struct SplayTree{ ll ch[N][2],pre[N],val[N],add[N],sz[N],sum[N]; ll root,top; inline void AddNode(ll x,ll c) { if(x==0) return; val[x]+=c; add[x]+=c; sum[x]+=c*sz[x]; } inline void PushUp(ll x) { if(x==0) return; sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]]; } inline void PushDown(ll x) { if(x==0) return; if(add[x]) { AddNode(ch[x][0],add[x]); AddNode(ch[x][1],add[x]); add[x]=0; } } inline void Rotate(ll x,ll c) { ll y=pre[x]; PushDown(y); PushDown(x); ch[y][!c]=ch[x][c]; if(ch[x][c]) pre[ch[x][c]]=y; pre[x]=pre[y]; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; ch[x][c]=y; pre[y]=x; PushUp(y); if(y==root) root=x; } inline void Splay(ll x,ll f) { PushDown(x); while(pre[x]!=f) { PushDown(pre[pre[x]]); PushDown(pre[x]); PushDown(x); if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][0]==x); else { ll y=pre[x],z=pre[y]; ll c=(ch[z][0]==y); if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c); else Rotate(y,c),Rotate(x,c); } } PushUp(x); if(f==0) root=x; } inline void SplayKth(ll k,ll f) { ll x=root; k+=1; while(1) { PushDown(x); if(k==sz[ch[x][0]]+1) break; else if(k<=sz[ch[x][0]]) x=ch[x][0]; else k-=sz[ch[x][0]]+1,x=ch[x][1]; } Splay(x,f); } inline void NewNode(ll &x,ll c) { x=++top; ch[x][0]=ch[x][1]=pre[x]=0; sz[x]=1; add[x]=0; sum[x]=val[x]=c; } inline void Build(ll &x,ll l,ll r,ll f) { if(l>r) return; ll m=(l+r)>>1; NewNode(x,num[m]); Build(ch[x][0],l,m-1,x); Build(ch[x][1],m+1,r,x); pre[x]=f; PushUp(x); } inline void Init(ll n) { ch[0][0]=ch[0][1]=pre[0]=val[0]=add[0]=sz[0]=sum[0]=0; root=top=0; for(ll i=1;i<=n;i++) scanf("%I64d",&num[i]); Build(root,0,n+1,0); } inline void Add(ll a,ll b,ll c) { SplayKth(a-1,0); SplayKth(b+1,root); AddNode(ch[ch[root][1]][0],c); } inline void GetSum(ll a,ll b) { SplayKth(a-1,0); SplayKth(b+1,root); printf("%I64d\n",sum[ch[ch[root][1]][0]]); }}t;int main(){ ll n,m; while(scanf("%I64d%I64d",&n,&m)!=EOF) { t.Init(n); while(m--) { char op; ll a,b,c; scanf(" %c",&op); if(op==‘Q‘) { scanf("%I64d%I64d",&a,&b); t.GetSum(a,b); } else { scanf("%I64d%I64d%I64d",&a,&b,&c); t.Add(a,b,c); } } } return 0;}
Splay练习题 [POJ 3468] A Simple Problem with Integers