P1438 无聊的数列 (差分+线段树)
程序员文章站
2022-10-06 08:38:46
题目 "P1438 无聊的数列" 解析: 先考虑修改,用差分的基本思想,左端点加上首项$k$,修改区间$(l,r]$内每个数的差分数组都加上公差$d$,最后的$r+1$再减去$k+(r l)\times d$。 查询的话就是求出$1 p$的前缀和,也就是区间求和。 不难看出,这实际上就是一个点修改+ ......
题目
解析:
- 先考虑修改,用差分的基本思想,左端点加上首项\(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; }
上一篇: PHP生成静态页面详解
下一篇: redis缓存穿透和缓存失效的预防和解决