2017-11-03 11:36:38

## 我真的没想到，分块居然过了这题而且跑得比线段树快得多233333

#include<cstdio>
#include<iostream>
#include<cmath>
#define neko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
using std::cin;
typedef long long ll;
int p,blk,m,bl[neko];
ll mod,t,a[neko],Max[neko];
template<typename T>
{
char c=getchar();x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
}
void update(ll x)
{
if(x>=mod)x%=mod;
if(x<0)x+=mod;
bl[++p]=(p-1)/blk+1,a[p]=x;
Max[bl[p]]=chkmax(Max[bl[p]],x);
}
ll query(int l,int r)
{
ll tmp=-3e9;
f(i,l,chkmin(bl[l]*blk,r))tmp=chkmax(tmp,a[i]);
f(i,bl[l]+1,bl[r]-1)tmp=chkmax(tmp,Max[i]);
f(i,chkmax((bl[r]-1)*blk+1,l),r)tmp=chkmax(tmp,a[i]);
return t=tmp;
}
int main()
{
std::ios::sync_with_stdio(false);
char c;
int x;
ll y;
cin>>m>>mod;blk=sqrt(m)/2;
f(i,1,m)
{
cin>>c;
if(c=='A')cin>>x,update(x+t);
if(c=='Q')cin>>y,printf("%lld\n",query(p-y+1,p));
}return 0;
}
• star
首页