This is a big problem

2020-2021 The second annual National Undergraduate algorithm design and programming challenge F topic

Description

Input

Output

For each query operation , The output does not contain xx Total score of movie No .

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

Ideas

The main problem to be solved is , For every point , You need to know how many intervals contain this point , And find the sum of these intervals . But obviously this is not very easy to ask .

So the idea turns to , The interval containing this point , How much contribution has this point made （ That is, the sum of these intervals corresponding to this point ）. So it's easy to know , We need to For each point in the interval , Are given the sum value of this interval . That is, the size of this single point plus inter segment .

Code

• Difference , It should be data points “ false ” 了 .

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;
		}
	}
}

• Line segment tree （ Less than two segment trees , The first code will not be changed , As a board of multi segment trees ）

#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);
        }
    }
}