首页 > 代码库 > POJ 3468 伸展树建树
POJ 3468 伸展树建树
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 59628 | Accepted: 18180 | |
| 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
这题用线段树做得更快，代码也更少，不过为了学伸展树，所以搞了好久。
每个节点存储的信息：
int pre[maxn]; 当前节点的前驱
int ch[maxn][2];当前节点的左右子树
int val[maxn];当前节点的值
int size[maxn];当前节点的子树的节点个数
int lazy[maxn];当前节点的子树被增加的值
LL sum[maxn];当前节点的子树的总值
当Q X Y的时候，就把x-1节点设置成根节点。y+1节点设置成根节点的右子树。
那么sum[ch[ch[root][1]][0]]即为结果。
当C X Y k的时候，就把x-1节点设置成根节点。y+1节点设置成根节点的右子树。
然后lazy[ch[ch[root][1]][0]]+=k;
因为把x-1设置成根节点，y+1设成根节点的右子树后，右子树的左子树就包含x到y区间的数了。#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 1000000
#define maxn 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct splaytree //伸展树
{
int pre[maxn];//前驱
int key[maxn];//键值
int ch[maxn][2];//左右孩子
int a[maxn];//数列
int size[maxn];//这颗树下面有多少个结点
int lazy[maxn];
ll sum[maxn];
int root,tot,n;//根节点，节点数量
void create()
{
tot=root=0;
mem(ch,0); mem(size,0);
mem(pre,0); mem(lazy,0);
mem(key,0); mem(sum,0);
}
void dfs(int x)
{
if(x)
{
dfs(ch[x][0]);
printf("结点：%2d 左儿子：%2d 右儿子：%2d 父结点：%2d 值为：%2d 节点数：%2d\n",x,ch[x][0],ch[x][1],pre[x],key[x],size[x]);
dfs(ch[x][1]);
}
}
void debug()
{
printf("根结点为：%d\n",root);
dfs(root);
}
void newnode(int &r,int father,int k)
{//在r位置，父亲为father，新建一个值点。
r=++tot;
pre[r]=father;
key[r]=k;
sum[r]=k;
lazy[r]=0;
size[r]=1;
ch[r][0]=ch[r][1]=0;
}
void push_down(int x)
{
key[x]+=lazy[x];
lazy[ch[x][1]]+=lazy[x];
lazy[ch[x][0]]+=lazy[x];
sum[ch[x][1]]+=(ll)lazy[x]*size[ch[x][1]];
sum[ch[x][0]]+=(ll)lazy[x]*size[ch[x][0]];
lazy[x]=0;
}
void push_up(int x)
{
size[x]=size[ch[x][1]]+size[ch[x][0]]+1;
sum[x]=sum[ch[x][1]]+sum[ch[x][0]]+lazy[x]+key[x];
}
void rotate(int x,int kind)//kind=1表示右旋，kind=0表示左旋
{
int y=pre[x];
push_down(x);push_down(y);
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;
pre[x]=pre[y];
pre[y]=x;
push_up(y);
}
void splay(int x,int goal) //goal=0则把x伸展到根,否则伸展到根的右子树
{
push_down(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);
}
}
push_up(x);
if(!goal) root=x;//把root更新成x
}
int find(int rank)//查找对应排名的结点编号
{
int r=root;
push_down(r);
while(size[ch[r][0]]!=rank)
{
if(rank<size[ch[r][0]]) r=ch[r][0];
else
{
rank-=size[ch[r][0]]+1;
r=ch[r][1];
}
push_down(r);
}
return r;
}
int insert(int x)//插入值x
{
int r=root;
while(ch[r][key[r]<x])
{
if(key[r]==x) {splay(r,0);return 0;}
r=ch[r][key[r]<x];
}
newnode(ch[r][x>key[r]],r,x);
splay(ch[r][x>key[r]],0);
return 1;
}
int get_pre(int x)//寻找节点x的前驱的值，未找到则返回INF
{
int r=ch[x][0];
if(!r) return -INF;
while(ch[r][1]) r=ch[r][1];
return key[r];
}
int get_next(int x)
{
int r=ch[x][1];
if(!r) return INF;
while(ch[r][0]) r=ch[r][0];
return key[r];
}
void update(int l,int r,int k)
{
splay(find(l-1),0);
splay(find(r+1),root);
lazy[ch[ch[root][1]][0]]+=k;
sum[ch[ch[root][1]][0]]+=(ll)size[ch[ch[root][1]][0]]*k;
}
ll query(int l,int r)
{
splay(find(l-1),0);
splay(find(r+1),root);
return sum[ch[ch[root][1]][0]];
}
void build(int &x,int l,int r,int father)
{
if(l>r) return ;
int mid=(l+r)/2;
newnode(x,father,a[mid]);
if(l<mid) build(ch[x][0],l,mid-1,x);
if(r>mid) build(ch[x][1],mid+1,r,x);
push_up(x);
}
void start()
{
newnode(root,0,-INF);
newnode(ch[root][1],root,-INF);
size[root]=2;
build(ch[ch[root][1]][0],1,n,ch[root][1]);
//在父结点值为-1的左子树建树不符合排序二叉树，这个有点不理解
push_up(ch[root][1]);
push_up(root);
}
}tree;
int main()
{
int n,q,i;
while(~scanf("%d%d",&n,&q))
{
tree.create();
tree.n=n;
for(i=1;i<=n;i++)
scanf("%d",&tree.a[i]);
tree.start();
//tree.debug();
while(q--)
{
char str[4];
int x,y,k;
scanf("%s%d%d",str,&x,&y);
if(str[0]=='Q')
printf("%lld\n",tree.query(x,y));
else
{
scanf("%d",&k);
tree.update(x,y,k);
}
}
}
return 0;
}