c/c++语言开发共享P1438 无聊的数列 (差分+线段树)

题目

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("%dn", a[k] + query(1, k, 1, n, 1));         }     }     return 0; }