P1438 无聊的数列 (差分+线段树)

题目

解析：

了解差分的话就很好做了

先考虑修改，用差分的基本思想，左端点加上首项\(k\)，因为是等差数列，所以修改的区间内都应该加一个增量，即修改区间\((l,r]\)内每个数的差分数组都加上公差\(d\)，显然最后的\(r+1\)再减去\(k+(r-l)\times d\)。
查询的话就是求出\(1-p\)的前缀和，也就是区间求和。

不难看出，这实际上就是一个点修改+区间修改+区间求和的题，所以直接上线段树，用线段树维护差分数组。

这个题目还有坑点就是要判断\(l,r\)的大小关系和\(r+1\)是否出界。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int n, m, rt;

int a[N];

class tree {

	public :

		int sum, lazy;

		int len;

} t[N << 2];

#define lson rt << 1

#define rson rt << 1 | 1

template<class T>inline void read(T &x) {

	x = 0; int f = 0; char ch = getchar();

	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

	x = f ? -x : x;

	return;

}

void pushup(int rt) {

	t[rt].sum = t[lson].sum + t[rson].sum;

}

void build(int l, int r, int rt) {

	t[rt].len = r - l + 1;

	if (l == r) return;

	int m = (l + r) >> 1;

	build(l, m, lson);

	build(m + 1, r, rson);

}

inline void pushdown(int rt) {

	if (t[rt].lazy) {

		t[lson].lazy += t[rt].lazy;

		t[rson].lazy += t[rt].lazy;

		t[lson].sum += t[lson].len * t[rt].lazy;

		t[rson].sum += t[rson].len * t[rt].lazy;

		t[rt].lazy = 0;

	}

}

void update(int L, int R, int c, int l, int r, int rt) {

	if (L <= l && r <= R) {

		t[rt].sum += c * t[rt].len;

		t[rt].lazy += c;

		return;

	}

	pushdown(rt);

	int m = (l + r) >> 1;

	if (L <= m) update(L, R, c, l, m, lson);

	if (R > m) update(L, R, c, m + 1, r, rson);

	pushup(rt);

}

int query(int L, int R, int l, int r, int rt) {

	if(L <= l && r <= R) return t[rt].sum;

	pushdown(rt);

	int m = (l + r) >> 1, ans = 0;

	if (L <= m) ans += query(L, R, l, m, lson);

	if (R > m) ans += query(L, R, m + 1, r, rson);

	return ans;

}

main() {

	read(n), read(m);

	for (int i = 1; i <= n; ++i) read(a[i]);

	build(1, n, 1);

	for (int i = 1, opt, l ,r, k, d; i <= m; ++i) {

		read(opt);

		if (opt == 1) {

			read(l), read(r), read(k), read(d);

			update(l, l, k, 1, n, 1);

			if (r > l) update(l + 1, r, d, 1, n, 1);

			if (r != n) update(r + 1, r + 1, -(k + (r - l) * d), 1, n, 1);

		} else {

			read(k);

			printf("%d\n", a[k] + query(1, k, 1, n, 1));

		}

	}

	return 0;

}

巴特西

P1438 无聊的数列 (差分+线段树)

题目

解析：

代码

最新文章

热门文章