「bsoj5408」增添 - 可持久化平衡树 | Bill Yang's Blog

「bsoj5408」增添 - 可持久化平衡树

题目大意

    ZY一口气出了两道大水题,他觉得这样太水了,一定会全场AK。于是他决定第三题继续水下去,他找来了一道ASDFZ的集训题,这道题在那一次考试中是被放在第一题的,可见是真的水。
    有一个长度为$n$的序列,要求支持三种操作。

  1. $1\,\,l\,\,r\,\,x$将$[l,r]$中的数增加$x$,保证$x\le10000$。
  2. $2\,\,l\,\,r\,\,x$用$[l,l+x]$中的数对应替换$[r,r+x]$中的数。
  3. $3\,\,l\,\,r$求$[l,r]$中的数的和。

题目分析

用非旋转treap维护数列,但是要实现区间替换必须要可持久化。
而且标记也要可持久化,因此在下传标记的时候需要拷贝儿子结点。
细节蛮多的,慢慢调吧。

achen用了江XX的生日作为随机数$seed$,每次$seed$变都不变,竟然过了。不敢苟同,不敢苟同


代码

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
139
140
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
#define pii pair<int,int>
#define mp make_pair
mt19937 g(rand());
const int maxn=100005;
struct Treap {
struct Tree {
int l,r,size;
int val,lazy;
LL sum;
Tree() {}
Tree(int s,int v,LL _s):l(0),r(0),size(s),val(v),sum(_s),lazy(0) {}
} tree[maxn*200];
int size;
#define val(x) tree[x].val
#define size(x) tree[x].size
int newnode(int v) {
tree[++size]=Tree(1,v,v);
return size;
}
void push_up(int index) {
int l=tree[index].l,r=tree[index].r;
size(index)=size(l)+size(r)+1;
tree[index].sum=tree[l].sum+tree[r].sum+val(index);
}
void modify(int index,int val) {
tree[index].val+=val;
tree[index].sum+=1ll*tree[index].size*val;
tree[index].lazy+=val;
}
void push_down(int index) {
if(tree[index].lazy==0)return;
int prel=tree[index].l,prer=tree[index].r;
if(prel) {
tree[tree[index].l=++size]=tree[prel];
modify(tree[index].l,tree[index].lazy);
}
if(prer) {
tree[tree[index].r=++size]=tree[prer];
modify(tree[index].r,tree[index].lazy);
}
tree[index].lazy=0;
}
pii split(int index,int num) {
if(!index)return mp(0,0);
push_down(index);
int now=++size;
tree[now]=tree[index];
int l=tree[now].l,r=tree[now].r;
if(num<=size(l)) {
pii lt=split(l,num);
tree[now].l=lt.second;
push_up(now);
return mp(lt.first,now);
} else {
pii rt=split(r,num-size(l)-1);
tree[now].r=rt.first;
push_up(now);
return mp(now,rt.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
int now=++size;
if(g()%(size(a)+size(b))<size(a)) {
push_down(a);
tree[now]=tree[a];
tree[now].r=merge(tree[a].r,b);
} else {
push_down(b);
tree[now]=tree[b];
tree[now].l=merge(a,tree[b].l);
}
push_up(now);
return now;
}
int add(int index,int Left,int Right,int val) {
pii tmp=split(index,Left-1);
pii tmp2=split(tmp.second,Right-Left+1);
modify(tmp2.first,val);
return merge(merge(tmp.first,tmp2.first),tmp2.second);
}
LL query(int index,int Left,int Right) {
pii tmp=split(index,Left-1);
pii tmp2=split(tmp.second,Right-Left+1);
return tree[tmp2.first].sum;
}
} bbt;
int n,m,root;
int main() {
srand(99995999);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)root=bbt.merge(root,bbt.newnode(Get_Int()));
for(int i=1; i<=m; i++) {
int opt=Get_Int(),x=Get_Int(),y=Get_Int();
if(opt==1)root=bbt.add(root,x,y,Get_Int());
else if(opt==2) {
int delta=Get_Int();
if(x==y)continue;
pii t1=bbt.split(root,x-1);
pii t2=bbt.split(t1.second,delta+1);
pii t3=bbt.split(root,y-1);
pii t4=bbt.split(t3.second,delta+1);
root=bbt.merge(bbt.merge(t3.first,t2.first),t4.second);
} else printf("%lld\n",bbt.query(root,x,y));
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%