# P1438 boring sequence (difference + line tree)

## subject

P1438 boring sequence

## Analysis:

• First, consider the modification. Using the basic idea of difference, add the first item \ (k \) to the left endpoint, add the tolerance \ (D \) to the difference array of each number in the modification interval \ ((l,r] \), and then subtract \ (k + (R-L) times d \) from the last \ (r+1 \).
• The query is to find the prefix sum of \ (1-p \), that is, the interval sum.

It's not hard to see that this is actually a problem of point modification + interval modification + interval summation, so directly go up the line segment tree and use the line segment tree to maintain the difference array.

There is also a hole in this topic, which is to determine the size relationship of \ (l,r \) and whether \ (r+1 \) is out of bounds.

## Code

```#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() {
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) {
if (opt == 1) {
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 {