선분 트 리 - 구간 수정 + 조회 구간 최대 값

제목.
설명 설명 은 하나의 수열 을 지정 하고 초기 값 은 모두 0 입 니 다. 현재 이 서열 에 대해 두 가지 조작 이 있 습 니 다. 조작 1: 첫 번 째 k1 개 를 두 번 째 k2 개 수 에 1 을 추가 합 니 다.조작 2: 조회 가 k1 개 에서 k2 개 까지 최대 치 입 니 다.모든 수 < = 100000 입력 형식 Input Format 첫 줄 에 정수 n 을 지정 하여 n 개의 동작 이 있 음 을 표시 합 니 다.다음은 n 줄 을 이 어 줄 마다 세 개의 정 수 를 나타 내 고 하나의 조작 을 나타 낸다.출력 형식 Output Format 몇 줄, 조회 한 번, 출력 한 번.샘플 입력 Sample Input 3 1 2 1 3 2 3 3 3 샘플 출력 Sample Output 1
템 플 릿

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define l(x) t[x].l
#define r(x) t[x].r
#define dat(x) t[x].dat
#define sum(x) t[x].sum
#define add(x) t[x].add 
#define clean(x, y) memset(x, y, sizeof(x))
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;
typedef long long LL;
using namespace std;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

template<typename T>
inline void write(T s) {
	if (s < 0) putchar('-'), s = -s;
	if (s > 9) write(s / 10);
	putchar(s % 10 + '0');
}

int n;
int a[maxn];
struct tree {
	int l, r;
	LL dat, sum, add;
} t[maxn << 2];

void build(int p, int l, int r) {
	l(p) = l, r(p) = r;
	if (l == r) { sum(p) = a[l]; return ; }
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	dat(p) = dat(p << 1) + dat(p << 1 | 1);
//	sum(p) = sum(p << 1) + sum(p << 1 | 1); 
}

void spread(int p) {
	if (add(p)) {
//		sum(p << 1) = add(p) * (r(p << 1) - l(p << 1) + 1);
//		sum(p << 1 | 1) = add(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
		add(p << 1) += add(p);
		add(p << 1 | 1) += add(p);
		dat(p << 1) += add(p);
		dat(p << 1 | 1) += add(p);
		add(p) = 0;
	}
}

void change(int p, int l, int r, int d) {
	if (l <= l(p) && r >= r(p)) {
		sum(p) += (LL) d * (r(p) - l(p) + 1);
		add(p) += d;
		dat(p) += d;
		return ;
	}
	spread(p);
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) change(p << 1, l, r, d);
	if (r > mid) change(p << 1 | 1, l, r, d);
	sum(p) = sum(p << 1) + sum(p << 1 | 1);
	dat(p) = max(dat(p << 1), dat(p << 1 | 1));
}

LL ask(int p, int l, int r) {
	if (l <= l(p) && r >= r(p)) return dat(p);
	spread(p);
	int mid = (l(p) + r(p)) >> 1;
	LL val = 0;
	if (l <= mid) val = max(val, ask(p << 1, l, r));
	if (r > mid)  val = max(val, ask(p << 1 | 1, l, r));
	return val;
}

int main() {
	read(n);
	build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		int opt, x, y;
		read(opt), read(x), read(y);
		if (opt == 1)
			change(1, x, y, 1);
		else
			write(ask(1, x, y)), putchar('
');
	}
	return 0;
}