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

좋은 웹페이지 즐겨찾기