Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

BZOJ-1012 [JSOI2008]最大数maxnumber

Jacinth posted @ 2015年7月15日 10:46 in BZOJ-LYDSY with tags BZOJ , 581 阅读

水水水,最水的题又来了~~~
纯纯的线段树~~撒花

题目:   http://www.lydsy.com/JudgeOnline/problem.php?id=1012

真的是最最最最撒比的线段树。。。不过要构造一个m大小的。。。不然存起来好麻烦

一开始check里面的判断条件写反了QAQ样例怎么也过不了

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define MM 200020
using namespace std;

char ch[10];
int mx[MM*4],a[MM];
int la,l,n,m,t,d,mm;

void change(int ll,int rr,int st)
{
	if (ll==rr)
	{
		mx[st]=n;
		return;
	}
	int mid=(ll+rr)/2;
	if (l<=mid) change(ll,mid,st<<1);
		else change(mid+1,rr,(st<<1)+1);
	mx[st]=max(mx[st<<1],mx[(st<<1)+1]);
	return;
}

int check(int ll,int rr,int l,int r,int st)
{
	if (ll<=l&&rr>=r) return mx[st];
	int sum=0,mid=(l+r)/2;
	if (ll<=mid) sum=max(sum,check(ll,rr,l,mid,st<<1));
	if (rr>mid) sum=max(sum,check(ll,rr,mid+1,r,(st<<1)+1));
	return sum;
}


int main()
{
	scanf("%d%d",&m,&d);
	t=l=0;
	mm=m;
	memset(mx,0,sizeof(mx));
	while (m--)
	{
		scanf("%s%d",&ch,&n);
		l++;
		if (ch[0]=='A')
		{
			a[++la]=l;
			n=(n%d+t%d)%d;
			change(1,mm,1);
		}
		else
		{
			printf("%d\n",t=check(a[la-n+1],a[la],1,mm,1));
			t%=d;
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter