用奇怪的姿势写区修区查数据结构【CodeVS 1082】
1. 线段树+lazytag，记录lc, rc 【1106ms】
# include <stdio.h>
using namespace std;
int n, seq[200010], m;
typedef long long ll;
int lc[3400010], rc[3400010];
ll w[3400010], lazy[3400010];
inline void pushdown(int x) {
if(!lazy[x]) return;
w[x<<1] += lazy[x] * (rc[x<<1] - lc[x<<1] + 1);
w[x<<1|1] += lazy[x] * (rc[x<<1|1] - lc[x<<1|1] + 1);
lazy[x<<1] += lazy[x];
lazy[x<<1|1] += lazy[x];
lazy[x] = 0;
}
inline void build(int x, int l, int r) {
lc[x] = l, rc[x] = r; w[x] = lazy[x] = 0;
if(l == r) {
w[x] = (ll)seq[l];
return ;
}
int mid = l+r>>1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
w[x] = w[x<<1] + w[x<<1|1];
}
inline void change(int x, int L, int R, ll delta) {
int l = lc[x], r = rc[x];
if(L <= l && r <= R) {
w[x] += delta*(rc[x] - lc[x] + 1);
lazy[x] += delta;
return ;
}
pushdown(x);
int mid = l+r >> 1;
if(L > mid) change(x<<1|1, L, R, delta);
else if(R <= mid) change(x<<1, L, R, delta);
else {
change(x<<1, L, mid, delta);
change(x<<1|1, mid+1, R, delta);
}
w[x] = w[x<<1] + w[x<<1|1];
}
inline ll query(int x, int L, int R) {
int l = lc[x], r = rc[x];
if(L <= l && r <= R) return w[x];
pushdown(x);
int mid = l+r >> 1;
if(L > mid) return query(x<<1|1, L, R);
else if(R <= mid) return query(x<<1, L, R);
else return query(x<<1, L, mid) + query(x<<1|1, mid+1, R);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &seq[i]);
build(1, 1, n);
scanf("%d", &m);
while(m--) {
int opt;
scanf("%d", &opt);
int l, r, del;
if(opt == 1) {
scanf("%d%d%d", &l, &r, &del);
change(1, l, r, (ll)del);
} else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, l, r));
}
}
}
2. 线段树+lazytag，不记录lc, rc 【876ms】，去除build过程【974ms】
# include <stdio.h>
using namespace std;
int n, seq[200010], m;
typedef long long ll;
ll w[3400010], lazy[3400010];
inline void pushdown(int x, int l, int r) {
if(!lazy[x]) return;
int mid = l+r >> 1;
w[x<<1] += lazy[x] * (mid - l + 1);
w[x<<1|1] += lazy[x] * (r - (mid+1) + 1);
lazy[x<<1] += lazy[x];
lazy[x<<1|1] += lazy[x];
lazy[x] = 0;
}
inline void build(int x, int l, int r) {
w[x] = lazy[x] = 0;
if(l == r) {
w[x] = (ll)seq[l];
return ;
}
int mid = l+r>>1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
w[x] = w[x<<1] + w[x<<1|1];
}
inline void change(int x, int l, int r, int L, int R, ll delta) {
if(L <= l && r <= R) {
w[x] += delta*(r - l + 1);
lazy[x] += delta;
return ;
}
pushdown(x, l, r);
int mid = l+r >> 1;
if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
else if(R <= mid) change(x<<1, l, mid, L, R, delta);
else {
change(x<<1, l, mid, L, mid, delta);
change(x<<1|1, mid+1, r, mid+1, R, delta);
}
w[x] = w[x<<1] + w[x<<1|1];
}
inline ll query(int x, int l, int r, int L, int R) {
if(L <= l && r <= R) return w[x];
pushdown(x, l, r);
int mid = l+r >> 1;
if(L > mid) return query(x<<1|1, mid+1, r, L, R);
else if(R <= mid) return query(x<<1, l, mid, L, R);
else return query(x<<1, l, mid, L, mid) + query(x<<1|1, mid+1, r, mid+1, R);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &seq[i]);
build(1, 1, n);
scanf("%d", &m);
while(m--) {
int opt;
scanf("%d", &opt);
int l, r, del;
if(opt == 1) {
scanf("%d%d%d", &l, &r, &del);
change(1, 1, n, l, r, (ll)del);
} else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
}
3. 线段树+tag永久化，不记录lc, rc 【779ms】加build过程【779ms】
# include <stdio.h>
using namespace std;
int n, seq[200010], m;
typedef long long ll;
ll w[3400010], tag[3400010];
inline void change(int x, int l, int r, int L, int R, ll delta) {
if(L == l && r == R) {
tag[x] += delta;
return ;
}
w[x] = w[x] + (R-L+1) * delta;
int mid = l+r >> 1;
if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
else if(R <= mid) change(x<<1, l, mid, L, R, delta);
else {
change(x<<1, l, mid, L, mid, delta);
change(x<<1|1, mid+1, r, mid+1, R, delta);
}
}
inline ll query(int x, int l, int r, int L, int R) {
if(L == l && r == R) return w[x] + tag[x] * (R-L+1);
int mid = l+r >> 1;
if(L > mid) return query(x<<1|1, mid+1, r, L, R) + tag[x] * (R-L+1);
else if(R <= mid) return query(x<<1, l, mid, L, R) + tag[x] * (R-L+1);
else return query(x<<1, l, mid, L, mid) + query(x<<1|1, mid+1, r, mid+1, R) + tag[x] * (R-L+1);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &seq[i]);
change(1, 1, n, i, i, seq[i]);
}
scanf("%d", &m);
while(m--) {
int opt;
scanf("%d", &opt);
int l, r, del;
if(opt == 1) {
scanf("%d%d%d", &l, &r, &del);
change(1, 1, n, l, r, (ll)del);
} else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
}
4. 树状数组 【540ms】
# include <stdio.h>
using namespace std;
int n, seq[200010], m;
typedef long long ll;
ll bit1[2400010], bit2[2400010];
inline int lowbit(int x) {
return x&(-x);
}
inline void change(int pos, ll del) {
ll del2 = pos*del;
while(pos <= n) {
bit1[pos] += del;
bit2[pos] += del2;
pos += lowbit(pos);
}
}
inline void change(int l, int r, ll del) {
change(l, del); change(r+1, -del);
}
inline ll ask(int pos) {
ll ret1 = 0, ret2 = 0; int ppos = pos;
while(pos > 0) {
ret1 = ret1 + bit1[pos];
ret2 = ret2 + bit2[pos];
pos -= lowbit(pos);
}
return (ppos + 1) * ret1 - ret2;
}
inline ll query(int l, int r) {
return ask(r) - ask(l-1);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &seq[i]);
change(i, i, (ll)seq[i]);
}
scanf("%d", &m);
while(m--) {
int opt;
scanf("%d", &opt);
int l, r, del;
if(opt == 1) {
scanf("%d%d%d", &l, &r, &del);
change(l, r, (ll)del);
} else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r));
}
}
}
5. 优秀的splay技术【2297ms】
# include <stdio.h>
# define RRL ch[ch[root][1]][0]
using namespace std;
int n, seq[2400010], m;
typedef long long ll;
int ch[2400010][2], fa[2400010], root, sz[2400010], siz=0;
ll w[2400010], tag[2400010], sum[2400010];
inline void pushdown(int x) {
if (!x || !tag[x]) return;
w[x] += tag[x];
if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x] * sz[ch[x][0]];
if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x] * sz[ch[x][1]];
tag[x] = 0;
}
inline void update(int x) {
if(!x) return;
sz[x] = 1+sz[ch[x][0]]+sz[ch[x][1]];
sum[x] = w[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
inline void rotate(int x) {
if(!fa[x]) return;
pushdown(fa[x]), pushdown(x);
int y = fa[x], c = ch[y][0] == x, &f = fa[y], &s = ch[x][c];
fa[x] = f; if(f) ch[f][ch[f][1] == y]=x; f=x;
ch[y][!c]=s; if(s) fa[s] = y; s=y;
update(y);
if(y == root) root = x;
}
inline void splay(int x, int to) {
pushdown(x);
while(fa[x] != to) {
if(fa[fa[x]] != to) {
int y = fa[x];
if((ch[y][0] == x) ^ (ch[fa[y]][0] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
update(x);
if(!to) root = x;
}
inline void splayk(int k, int to) {
int x = root; pushdown(x);
while(sz[ch[x][0]] != k-1) {
if(sz[ch[x][0]] < k) {
k-=sz[ch[x][0]]+1;
x=ch[x][1];
} else x=ch[x][0];
pushdown(x);
}
splay(x, to);
}
inline void add(int &x, int fat, ll tw) {
x = ++siz; sz[x] = 1; fa[x] = fat;
w[x] = sum[x] = tw;
}
inline void buildsplay(int &x, int fa, int l, int r) {
if(l>r) {x=0; return;}
int mid=l+r>>1;
add(x, fa, seq[mid]);
buildsplay(ch[x][0], x, l, mid-1);
buildsplay(ch[x][1], x, mid+1, r);
update(x);
}
inline void build() {
siz = 0, root = 0;
add(root, 0, 0);
add(ch[root][1], root, 0);
update(root);
buildsplay(RRL, ch[root][1], 1, n);
update(ch[root][1]);
update(root);
}
inline void getlr(int l, int r) {
splayk(l, 0);
splayk(r+2, root);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i)
scanf("%d", &seq[i]);
build();
scanf("%d", &m);
while(m--) {
int opt;
scanf("%d", &opt);
int l, r, del;
if(opt == 1) {
scanf("%d%d%d", &l, &r, &del);
getlr(l, r);
tag[RRL] += del;
sum[RRL] += (ll)sz[RRL] * del;
} else {
scanf("%d%d", &l, &r);
getlr(l, r);
printf("%lld\n", sum[RRL]);
}
}
}
待继续更新填坑（剩余treap, SBT, toptree ......）
2024年1月10日 13:51
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.