[JSOI2008]最大数maxnumber

标签： 线段树 单独队列

---

题目链接

题解

线段树裸题。

如果一直RE可能是你用的cin/cout。

Code

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)

inline int read()

{

	int sum=0,p=1;char ch=getchar();

	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();

	if(ch=='-')p=-1,ch=getchar();

	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();

	return sum*p;

}

const int maxn=2e5+20;

int n;

int mod;

struct node {

	int mx;

	inline void Merge(node a,node b)

		{

			mx=max(a.mx,b.mx);

		}

};

node c[maxn*4];

void init()

{

	n=read();mod=read();

}

#define lc (o<<1)

#define rc (o<<1 | 1)

#define left lc,l,mid

#define right rc,mid+1,r

inline void update(int x,int d,int o,int l,int r)

{

	if(l==r)

	{

		c[o].mx=d;

		return;

	}

	register int mid=(l+r)>>1;

	if(x<=mid)update(x,d,left);

	else update(x,d,right);

	c[o].Merge(c[lc],c[rc]);

}

inline int query(int ql,int qr,int o,int l,int r)

{

	if(ql<=l && r<=qr)

	{

		return c[o].mx;

	}

	register int mid=(l+r)>>1;register int ans=0;

	if(ql<=mid)ans=max(ans,query(ql,qr,left));

	if(qr>mid)ans=max(ans,query(ql,qr,right));

	return ans;

}

inline void doing()

{

	register int t=0;

	int cnt=0;

	REP(i,1,n)

	{

		char ch[5];int x;

		scanf("%s",ch);

		if(ch[0]=='A')

		{

			cnt++;

			x=read();x=(x+t)%mod;

			update(cnt,x,1,1,n);

		}else

		{

			x=read();

			t=query(cnt-x+1,cnt,1,1,n);

			printf("%d\n",t);

		}

	}

}

int main()

{

	init();

	doing();

	return 0;

}