2022年江西省大学生程序设计竞赛 K.Peach Conference 线段树 懒标记清空

传送门

大致题意：

  给定一个n和m，表示有区间大小为n，进行m次操作。
  输入m行，每行3个数字v, l, r。如果v等于0则表示查询[l, r]内桃子的数量，如果v不为0则表示给[l, r]区间修改全部加v，如果有某个点数量+v小于0，则修改为0即可。

大致思路：

  这个题和势能也还是有些关系的。如果要对一个区间加上v，那么这个区间的最大值+v<=0，就需要区间清空，如果一个区间的最小值+v>0，则直接区间修改并且懒标记修改，如果上述两个条件都不满足，则继续递归左右儿子即可。所以考虑线段树上维护最大最小值，区间和，懒标记和区间清空标记。代码中的clear是区间清空标记，lazy是懒标记，mx是区间最大值，mn是区间最小值。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>

typedef long long ll;
typedef std::pair<int, int> PII;
#define ls u << 1
#define rs u << 1 |1

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;

struct node {
	int l, r;
	bool clear;
	ll lazy, mx, mn, sum;
}tr[N << 2];

inline void build(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);
}

inline void pushup(int u) {
	tr[u].mx = std::max(tr[ls].mx, tr[rs].mx);
	tr[u].mn = std::min(tr[ls].mn, tr[rs].mn);
	tr[u].sum = tr[ls].sum + tr[rs].sum;
}

inline void pushdown(int u) { 
	if (tr[u].clear) {
		tr[ls].lazy = 0, tr[ls].mx = tr[ls].mn = tr[ls].sum = 0;
		tr[rs].lazy = 0, tr[rs].mx = tr[rs].mn = tr[rs].sum = 0;
		tr[ls].clear = tr[rs].clear = true;	
		tr[u].clear = false;
	}
	
	if (tr[u].lazy) {
		ll &v = tr[u].lazy;
		tr[ls].lazy += v;
		tr[rs].lazy += v;
		tr[ls].sum += v * (tr[ls].r - tr[ls].l + 1);
		tr[rs].sum += v * (tr[rs].r - tr[rs].l + 1);
		tr[ls].mn += v;
		tr[rs].mn += v;
		tr[ls].mx += v;
		tr[rs].mx += v;
		v = 0; 
	}
}

inline void modify(int u, int l, int r, int v) {

	if (tr[u].l >= l && tr[u].r <= r) {
		if (tr[u].mx + v <= 0) {
			tr[u].clear = true;
			tr[u].sum = tr[u].lazy = tr[u].mx = tr[u].mn = 0;	
		} else if(tr[u].mn + v > 0) {
			tr[u].lazy += v;
			tr[u].sum += v * (tr[u].r - tr[u].l + 1);
			tr[u].mn += v;
			tr[u].mx += v;
		} else {
			pushdown(u);
			modify(ls, l, r, v);
			modify(rs, l, r, v);
			pushup(u);
		}
		return ;
	}
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(l <= mid)	modify(ls, l, r, v);
	if(r > mid)	modify(rs, l, r, v);
	
	pushup(u);
}

inline ll query(int u, int l, int r) {
	if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
	
	ll res = 0;
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid)	res += query(ls, l, r);
	if(r > mid)	res += query(rs, l, r);
	
	return res;
}

inline void solve() {
	std::cin >> n >> m;
	
	build(1, 1, n);
	
	while (m --) {
		int v, l, r;
		std::cin >> v >> l >> r;
		
		if(v)	modify(1, l, r, v);	
		else std::cout << query(1, l, r) << '\n';
	}	
}

int main(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    
    int _ = 1;
    //std::cin >> _;
    while(_ --)
    	solve();

    return 0;
}