Splay POJ3468（老题新做）

100 阅读 0 评论 66 点赞

我是靠谱客的博主合适羽毛，这篇文章主要介绍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

复制代码

1
2
3
4
5
6
7
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/*************************************************************************
> 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;
}