题目

P2801 教主的魔法

解析

成天做水题

线段树，第一问区间加很简单

第二问可以维护一个区间最大值和一个区间最小值，若C小于等于区间最小值，就加上区间长度，若C大于区间最大值，就加0

ps:求教指针线段树，我的空间怎么那么大

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int n, m, num;

int a[N];

class tree {

	public :

		int mx, mn, sum;

		int lazy, len;

		tree *ls, *rs;

		tree() {

			sum = mx = mn = lazy = len = 0;

			ls = rs = NULL;

		}

} t[N];

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;

}

inline void pushup(tree *rt) {

	rt->mn = min(rt->ls->mn, rt->rs->mn);

	rt->mx = max(rt->ls->mx, rt->rs->mx);

}

void build(int l, int r, tree *rt) {

	rt->len = r - l + 1;

	if (l == r) {

		rt->mn = rt->mx = a[l];

		return;

	}

	rt->ls = &t[++num], rt->rs = &t[++num];

	int m = (l + r) >> 1;

	build(l, m, rt->ls), build(m + 1, r, rt->rs);

	pushup(rt);

}

inline void pushdown(tree *rt) {

	if (rt->lazy) {

		rt->ls->mx += rt->lazy;

		rt->rs->mx += rt->lazy;

		rt->ls->mn += rt->lazy;

		rt->rs->mn += rt->lazy;

		rt->ls->lazy += rt->lazy;

		rt->rs->lazy += rt->lazy;

		rt->lazy = 0;

	}

}

void update(int L, int R, int c, int l, int r, tree *rt) {

	if (L <= l && r <= R) {

		rt->mn += c;

		rt->mx += c;

		rt->lazy += c;

		return;

	}

	pushdown(rt);

	int m = (l + r) >> 1;

	if (L <= m) update(L, R, c, l, m, rt->ls);

	if (R > m) update(L, R, c, m + 1, r, rt->rs);

	pushup(rt);

}

int query(int L, int R, int c, int l, int r, tree *rt) {

	if (L <= l && r <= R && rt->mn >= c) return rt->len;

	if (L <= l && r <= R && rt->mx < c) return 0;

	pushdown(rt);

	int m = (l + r) >> 1, ans = 0;

	if (L <= m) ans += query(L, R, c, l, m, rt->ls);

	if (R > m) ans += query(L, R, c, m + 1, r, rt->rs);

	return ans;

}

int main() {

	read(n), read(m);

	for (int i = 1; i <= n; ++i) read(a[i]);

	tree *rt = new tree;

	build(1, n, rt);

	for (int i = 1, x, y, z; i <= m; ++i) {

		char c;

		cin >> c;

		read(x), read(y), read(z);

		if (c == 'M')

			update(x, y, z, 1, n, rt);

		else

			printf("%d\n", query(x, y, z, 1, n, rt));

	}

	delete rt;

	return 0;

}