/*http://poj.org/problem?id=3468*/
/*区间更新,区间求和*/
/*注意各种编码细节,特别是splay buildTree和 rotateTo*/
/*仔细体会与线段树解决区间问题的不同点,如结点记录的信息是不同的*/
/*lazy思想*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 111111;
class SplayTree{
#define l(x) (ch[x][0])
#define r(x) (ch[x][1])
#define mid(x,y) (x+y)>>1
public:
int ch[MAXN][2],pre[MAXN],sz[MAXN];
long long sum[MAXN],add[MAXN],val[MAXN];
int a[MAXN];
int tot,root;
void init(){
memset(ch,0,sizeof(int)*MAXN*2);
memset(pre,0,sizeof(int)*MAXN);
memset(sz,0,sizeof(int)*MAXN);
memset(sum,0,sizeof(long long)*MAXN);
memset(add,0,sizeof(long long)*MAXN);
memset(val,0,sizeof(long long)*MAXN);
tot = root = 0;
}
void read(int n){
a[1] = a[n+2] = 0;
for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
}
void push_up(int rt){
sum[rt] = sum[l(rt)]+sum[r(rt)]+val[rt];
sz[rt] = sz[l(rt)]+sz[r(rt)]+1;
}
void push_down(int rt){
if(add[rt]){
if(l(rt)){
val[l(rt)] += add[rt];
add[l(rt)] += add[rt];
sum[l(rt)] += add[rt]*sz[l(rt)];
}
if(r(rt)){
val[r(rt)] += add[rt];
add[r(rt)] += add[rt];
sum[r(rt)] += add[rt]*sz[r(rt)];
}
add[rt] = 0;
}
}
void rotate(int x,int f){
int y = pre[x];
push_down(x);
push_down(y);
ch[y][!f] = ch[x][f];
if(ch[y][!f]) pre[ch[y][!f]] = y;
push_up(y);
if(pre[y]) ch[pre[y]][r(pre[y])==y] = x;
pre[x] = pre[y];
ch[x][f] = y;
pre[y] = x;
}
void splay(int x,int goal){
while(pre[x]!=goal){
int y = pre[x],z = pre[pre[x]];
if(z==goal){
rotate(x,l(y)==x);
}else{
int f = l(z)==y;
if(ch[y][!f]==x){
rotate(y,f); rotate(x,f);
}else{
rotate(x,!f); rotate(x,f);
}
}
}
push_up(x);
if(goal==0) root = x;
}
void rotateTo(int k,int goal){
int x = root;
while(1){
push_down(x);
if(k==(sz[l(x)]+1)) break;
else if(k<(sz[l(x)]+1)) x = l(x);
else{
k -= sz[l(x)]+1;
x = r(x);
}
}
splay(x,goal);
}
void buildTree(int l,int r,int &rt,int f){
if(l>r)return;
int m = mid(l,r);
rt = ++tot;
pre[rt] = f;
val[rt] = a[m];
buildTree(l,m-1,l(rt),rt);
buildTree(m+1,r,r(rt),rt);
push_up(rt);
}
long long query(int l,int r){
rotateTo(l-1,0);
rotateTo(r+1,root);
return sum[l(r(root))];
}
void update(int l,int r,int c){
rotateTo(l-1,0);
rotateTo(r+1,root);
val[l(r(root))] += c;
sum[l(r(root))] += c*sz[l(r(root))];
add[l(r(root))] += c;
}
}spt;
int main(){
int n,q;
while(scanf("%d%d",&n,&q)!=EOF){
spt.init();
spt.read(n);
spt.buildTree(1,n+2,spt.root,0);
char op[2]; int a,b,c;
while(q--){
scanf("%s%d%d",op,&a,&b);
if(op[0]=='Q'){
printf("%I64d\n",spt.query(a+1,b+1));
}else{
scanf("%d",&c);
spt.update(a+1,b+1,c);
}
}
}
return 0;
}
分享到:
相关推荐
给定一个长度为N的序列,每个序列的长度是一个整数。... 将[L,R]这个区间所有数加上V. 将[L,R]这个区间翻转,例如 1234变成 4321 求[L,R]区间的最大值 能力有限,实现可能有纰漏,也没有用到lazy_tag
Splay,平衡树的一种,支持部分区间操作。
SplayTree详细解释
Splay教学课件
splay经典代码,hdu1890,经典入门题,可作为模板
Splay基础教程 By Sqybi.自底向上型的
讲解Splay的经典论文 -------- Randomized Splay Trees: Theoretical and Experimental Results Susanne Albers Marek Karpinski
展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
Splay结构体的模板,含有各种旋转、插入、翻转等操作,注释清晰
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...
SplayTree优化版C源代码,带有完整的解释,其实就是置顶向下的Splay tree
splay 伸展树.ppt
splay和动态树的经典,是ACM选手了解动态树和Splay的重要资源。欢迎大家下载,并能熟练利用动态树和splay解题。
splay程序,希望大家可以看一下,适合新手
splay tree C# code 伸展树的C#代码实现 我看到没有C#实现版本,所以就把java代码转化成C#实现了一把
伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 ...
1、对于区间加的操作,只需要加上一个加标记,并且修改这个节点维护的区间 2、对于区间翻转操作,只需要加上一个翻转标记 3、对于区间插入操作,如果插入到 pos,
Splay模板包括旋转,主函数Splay,插入,删除,最大值,最小值,查询k大,查询排名
一个简单的 AVL树、splay树、以及二叉搜索树的代码实现 也可在我的github仓库中下载: https://github.com/yunwei37/myClassNotes
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...