UVA 12436 - Rip Van Winkle's Code（线段树)

时间：2024-10-23 13:34:14

UVA 12436 - Rip Van Winkle's Code

option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=3867&mosmsg=Submission+received+with+ID+14331401" target="_blank" style="">题目链接

题意：区间改动一个加入等差数列，一个把区间设为某个值，然后询问区间和

思路：关键在于等差数列的地方，线段树的每一个结点加入一个首项和公差，因为等差数列加上一个等差数列还是一个等差数列。利用这个性质就能够进行维护了，注意set操作会覆盖掉等差数列的操作

代码：

#include <cstdio>

#include <cstring>

#define lson(x) ((x<<1)+1)

#define rson(x) ((x<<1)+2)

typedef long long ll;

const int N = 250005;

int n;

struct Node {

	ll l, r, a1, d, c, val;

	int setc;

} node[N * 4];

void build(ll l, ll r, int x = 0) {

	node[x].l = l; node[x].r = r;

	node[x].a1 = node[x].d = node[x].val = node[x].setc = 0;

	if (l == r) return;

	ll mid = (l + r) / 2;

	build(l, mid, lson(x));

	build(mid + 1, r, rson(x));

}

void pushup(int x) {

	node[x].val = node[lson(x)].val + node[rson(x)].val;

}

void pushdown(int x) {

	if (node[x].setc) {

		node[lson(x)].c = node[rson(x)].c = node[x].c;

		node[lson(x)].val = (node[lson(x)].r - node[lson(x)].l + 1) * node[x].c;

		node[rson(x)].val = (node[rson(x)].r - node[rson(x)].l + 1) * node[x].c;

		node[lson(x)].setc = node[rson(x)].setc = 1;

		node[lson(x)].a1 = node[lson(x)].d = node[rson(x)].a1 = node[rson(x)].d = 0;

		node[x].setc = 0;

	}

	node[lson(x)].a1 += node[x].a1;

	node[lson(x)].d += node[x].d;

	ll l = node[x].l, r = node[x].r;

	ll mid = (l + r) / 2;

	ll amid = node[x].a1 + node[x].d * (mid - l + 1);

	ll len1 = (mid - l + 1), len2 = (r - mid);

	node[lson(x)].val += node[x].a1 * len1 + len1 * (len1 - 1) / 2 * node[x].d;

	node[rson(x)].a1 += amid;

	node[rson(x)].d += node[x].d;

	node[rson(x)].val += amid * len2 + len2 * (len2 - 1) / 2 * node[x].d;

	node[x].a1 = node[x].d = 0;

}

void A(ll l, ll r, ll d, int x = 0) {

	if (node[x].l >= l && node[x].r <= r) {

		ll st = node[x].l - l + 1;

		if (d == -1) st = r - node[x].l + 1;

		node[x].a1 += st;

		node[x].d += d;

		ll len = node[x].r - node[x].l + 1;

		node[x].val += st * len + len * (len - 1) / 2 * d;

		return;

	}

	pushdown(x);

	ll mid = (node[x].l + node[x].r) / 2;

	if (l <= mid) A(l, r, d, lson(x));

	if (r > mid) A(l, r, d, rson(x));

	pushup(x);

}

void C(ll l, ll r, ll c, int x = 0) {

	if (node[x].l >= l && node[x].r <= r) {

		node[x].setc = 1;

		node[x].c = c;

		node[x].val = (node[x].r - node[x].l + 1) * c;

		node[x].a1 = node[x].d = 0;

		return;

	}

	pushdown(x);

	ll mid = (node[x].l + node[x].r) / 2;

	if (l <= mid) C(l, r, c, lson(x));

	if (r > mid) C(l, r, c, rson(x));

	pushup(x);

}

ll S(ll l, ll r, int x = 0) {

	if (node[x].l >= l && node[x].r <= r)

		return node[x].val;

	pushdown(x);

	ll mid = (node[x].l + node[x].r) / 2;

	ll ans = 0;

	if (l <= mid) ans += S(l, r, lson(x));

	if (r > mid) ans += S(l, r, rson(x));

	pushup(x);

	return ans;

}

int main() {

	while (~scanf("%d", &n)) {

		build(1, 250000);

		ll a, b, c;

		char Q[2];

		while (n--) {

			scanf("%s%lld%lld", Q, &a, &b);

			if (Q[0] == 'C') scanf("%lld", &c);

			if (Q[0] == 'A') A(a, b, 1);

			if (Q[0] == 'B') A(a, b, -1);

			if (Q[0] == 'C') C(a, b, c);

			if (Q[0] == 'S') printf("%lld\n", S(a, b));

		}

	}

	return 0;

}

相关文章