Description
Input
Output
对于每一个询问操作，输出不包含xx号电影的评分时的总评分。
Sample Input 1
10 5
0 4 6 3
0 1 2 2
0 4 5 2
1 4
1 1
Sample Output 1
4
13
Hint
思路
这题主要要解决的问题就在，对于每一点，需要知道多少个区间包含了该点，并求出这些区间的和。但显然这不是很好求。
所以思路转为，包含该点的区间，该点对应的做出了多少贡献（即这个点对应的这些区间的和）。那么很容易知道，我们需要对区间中的每点，都赋予其这段区间的和值。也就是这个单点加区间段的大小。
代码
差分，能过应该是数据点“假”了。
int a[N]; void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int op; cin >> op; int l, r, x; if(op == 0) { cin >> l >> r >> x; a[1] += (r - l + 1) * x; a[l] -= (r - l + 1) * x; a[r + 1] += (r - l + 1) * x; a[N - 1] -= (r - l + 1) * x; } else { cin >> x; int ans = 0; for (int i = 1; i <= x; i++) ans += a[i]; cout << ans << endl; } } }
- 线段树（用不到两颗线段树，第一份代码就不改了，作为多颗线段树的板子）
#include <bits/stdc++.h> using namespace std; const int N = 200100; #define int long long #define ls u<<1 #define rs u<<1|1 struct node { int l, r; int v, add; } tr[2][N << 2]; int n, m; void pushup(int _, int u) { tr[_][u].v = tr[_][ls].v + tr[_][rs].v; } void pushdown(int _, int u) { if(tr[_][u].add) { tr[_][ls].add += tr[_][u].add, tr[_][ls].v += (tr[_][ls].r - tr[_][ls].l + 1) * tr[_][u].add; tr[_][rs].add += tr[_][u].add, tr[_][rs].v += (tr[_][rs].r - tr[_][rs].l + 1) * tr[_][u].add; tr[_][u].add = 0; } } void build(int _, int u, int l, int r) { tr[_][u] = {l, r}; if(l == r) { return ; } int mid = (l + r) >> 1; build(_, ls, l, mid), build(_, rs, mid + 1, r); pushup(_, u); } void modify(int _, int u, int l, int r, int v) { if(tr[_][u].l >= l && tr[_][u].r <= r) { tr[_][u].v += (tr[_][u].r - tr[_][u].l + 1) * v; tr[_][u].add += v; return ; } int mid = (tr[_][u].l + tr[_][u].r) >> 1; pushdown(_, u); if(l <= mid) modify(_, ls, l, r, v); if(r > mid) modify(_, rs, l, r, v); pushup(_, u); return ; } int query(int _, int u, int l, int r){ if(tr[_][u].l >= l && tr[_][u].r <= r) { return tr[_][u].v; } int mid = (tr[_][u].l + tr[_][u].r) >> 1; pushdown(_, u); int res = 0; if(l <= mid) res = query(_, ls, l, r); if(r > mid) res += query(_, rs, l, r); return res; } signed main() { cin >> n >> m; build(0, 1, 1, n), build(1, 1, 1, n); for (int i = 1; i <= m; i++) { int op, l, r, x; cin >> op; if(op == 0) { cin >> l >> r >> x; modify(0, 1, l, r, x); modify(1, 1, l, r, (r - l + 1) * x); } else { cin >> x; cout << query(0, 1, 1, n) - query(1, 1, x, x) << endl; } } return 0; }
const int N = 2e6 + 10; const int mod = 1e9 + 7; //*/ 998244353; const int inf = 1e9; int n, m; struct node { int l, r; int val; int lz; }tr[N * 2]; void pushup(int u) { tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val; return; } void pushdown(int u) { if (tr[u].lz) { tr[u << 1].val += tr[u].lz * (tr[u << 1].r - tr[u << 1].l + 1); tr[u << 1 | 1].val += tr[u].lz * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1); tr[u << 1].lz += tr[u].lz; tr[u << 1 | 1].lz += tr[u].lz; tr[u].lz = 0; } else return; } void build(int u, int l, int r) { tr[u].l = l, tr[u].r = r; if (l == r) return; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int x) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].val += (tr[u].r - tr[u].l + 1) * x; tr[u].lz += x; return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, x); if (r > mid) modify(u << 1 | 1, l, r, x); pushup(u); } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return tr[u].val; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; int ans = 0; if (l <= mid) ans += query(u << 1, l, r); if (r > mid) ans += query(u << 1 | 1, l, r); return ans; } void solve() { rd(n), rd(m); build(1, 1, n); int ans = 0; for (int i = 1; i <= m; i++) { int op; rd(op); if (op == 0) { int l, r; rd(l), rd(r); int x; rd(x); ans += (r - l + 1) * x; modify(1, l, r, (r - l + 1) * x); } else { int x; rd(x); pf(ans - query(1, x, x), 1); } } }
