Splay POJ3468（老题新做）

68 阅读 0 评论 45 点赞

我是靠谱客的博主合适羽毛，最近开发中收集的这篇文章主要介绍Splay POJ3468（老题新做），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A Simple Problem with Integers

Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u

Submit Status Practice POJ 3468

Appoint description:

Description

You have N integers, A₁, A₂, ... , A_N. 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 A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C abc" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q ab" means querying the sum of A_a, A_a₊₁, ... , A_b.

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

Hint

The sums may exceed the range of 32-bit integers.

这题应该算是线段树区间入目题目，不过还可以用Splay来做，用Splay来维护序列，用到了平衡二叉树的一个重要的性质那就是中序遍历是有序的。人生第一道Splay（感人TAT，QAQ）

代码如下：

/*************************************************************************
> File Name: Spaly.cpp
> Author: acvcla
> QQ:
> Mail: acvcla@gmail.com
> Created Time: 2014年11月16日 星期日 00时14分26秒
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 100;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
LL add[maxn],sum[maxn];
int ch[maxn][2],siz[maxn],key[maxn],pre[maxn],A[maxn];
int root,tot;
void newnode(int &x,int fa,int Key)//新建节点
{
x=++tot;
pre[x]=fa;
siz[x]=1;
key[x]=sum[x]=Key;
ch[x][0]=ch[x][1]=add[x]=0;
}
void Modify(int x,int val){//区间更新
if(!x)return;
add[x]+=val;
key[x]+=val;
sum[x]+=(LL)val*siz[x];
}
void push_down(int x){//下传标记
if(!add[x])return ;
Modify(ch[x][0],add[x]);
Modify(ch[x][1],add[x]);
add[x]=0;
}
void push_up(int x){//更新节点
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
}
void built(int &x,int L,int R,int fa){
if(L>R)return;
int M=(L+R)>>1;
newnode(x,fa,A[M]);
built(ch[x][0],L,M-1,x);
built(ch[x][1],M+1,R,x);
push_up(x);
}
void Init(int n)//初始化Spaly，添加了两个虚拟节点，便于提取区间，避免讨论
{
root=tot=0;
newnode(root,0,0);
newnode(ch[root][1],root,0);
for(int i=1;i<=n;i++)scanf("%d",A+i);
built(ch[ch[root][1]][0],1,n,ch[root][1]);
push_up(ch[root][1]);
push_up(root);
}
void print(int x){
if(!x)return;
print(ch[x][0]);
printf("%d ",key[x]);
print(ch[x][1]);
}
void Rotate(int x,bool kind){//旋转，true右旋，false左旋
int y=pre[x];
push_down(y);//下传标记
push_down(x);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
ch[x][kind]=y;
if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;//若y的父节点存在将其孩子指针指向x
pre[x]=pre[y];
pre[y]=x;
push_up(y);//更新回来，需要注意的是，要先更新孩子
push_up(x);
}
void Spaly(int x,int goal){//伸展操作，将x旋转到goal下面
push_down(x);
while(pre[x]!=goal){
if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
else{
int y=pre[x];
bool kind=(ch[pre[y]][0]==y);
if(ch[y][kind]==x){
Rotate(x,!kind);
Rotate(x,kind);
}else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
push_up(x);
if(goal==0)root=x;//如果goal是0说明已经将x旋转到了根，所以要更新root
}
int Get_kth(int x,int k){//序列中的第k个值
int t=siz[ch[x][0]]+1;
if(t==k)return x;
if(t>k)return Get_kth(ch[x][0],k);
return Get_kth(ch[x][1],k-t);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
siz[0]=sum[0]=0;//不存在的节点初始化为0避免讨论
int n,q,l,r,x;
scanf("%d%d",&n,&q);
Init(n);
char cmd[5];
while(q--){
scanf("%s%d%d",cmd,&l,&r);
Spaly(Get_kth(root,l),0);
Spaly(Get_kth(root,r+2),root);
if(cmd[0]=='Q'){
printf("%lldn",sum[ch[ch[root][1]][0]]);
}else{
int Add;
scanf("%d",&Add);
Modify(ch[ch[root][1]][0],Add);
push_up(ch[root][1]);
push_up(root);
}
}
return 0;
}