BZOJ 1012 JSOI 2008 최대 치 max number 선분 트 리 물 문제

제목: 데이터 구 조 를 유지 하고 두 가지 기능 을 지원 합 니 다. 조회 구간 이 가장 크 고 수열 의 마지막 에 삽 입 됩 니 다.
사고방식: 한눈 에 선분 나무 가 보 여서 할 말 이 없어 요.한 가지 만 주의해 야 합 니 다. 삽입 할 때 라인 트 리 의 범 위 는 시퀀스 의 총 수 를 따라 가지 마 십시오. 그러면 노드 를 만 든 후에 아버지 노드 의 정 보 를 업데이트 할 수 없습니다.
CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 200010
#define MO d
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)
using namespace std;

int cnt,asks,d;
int tree[MAX << 2];
int last;

char c[10];

void Modify(int l,int r,int aim,int pos,int c);
int Ask(int l,int r,int x,int y,int pos);

int main()
{
	cin >> asks >> d;
	for(int x,i = 1;i <= asks; ++i) {
		scanf("%s",c);
		switch(c[0]) {
			case 'Q':
				scanf("%d",&x);
 				last = Ask(1,MAX - 1,cnt - x + 1,cnt,1);
				printf("%d
",last);
				break;
			case 'A':
				cnt++;
				scanf("%d",&x);
				Modify(1,MAX - 1,cnt,1,(x + last) % MO);
				break;
		}
	}
	return 0;
}

void Modify(int l,int r,int aim,int pos,int c)
{
	if(l == r) {
		tree[pos] = c;
		return ;
	}
	int mid = (l + r) >> 1;
	if(aim <= mid)	Modify(l,mid,aim,LEFT,c);
	else	Modify(mid + 1,r,aim,RIGHT,c);
	tree[pos] = max(tree[LEFT],tree[RIGHT]);
}

int Ask(int l,int r,int x,int y,int pos)
{
	if(l == x && r == y)	return tree[pos];
	int mid = (l + r) >> 1;
	if(y <= mid)	return Ask(l,mid,x,y,LEFT);
	if(x > mid)		return Ask(mid + 1,r,x,y,RIGHT);
	int left = Ask(l,mid,x,mid,LEFT);
	int right = Ask(mid + 1,r,mid + 1,y,RIGHT);
	return max(left,right); 
}