用奇怪的姿势写区修区查数据结构【CodeVS 1082】

tonyfang posted @ 2016年9月05日 19:40 in 随笔 with tags c++ OI , 378 阅读

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 ......)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter