题解 P1198 【[JSOI2008]最大数】
teafrogsf
2017-11-03 11:36:38
## 我真的没想到,分块居然过了这题而且跑得比线段树快得多233333
由于本题询问有m个,则我们假定会增加m/2个数,那么就可以块的长度就可以假定为sqrt(m/2)(但我的代码好像分的是sqrt(m)/2,不过跑的也挺快我就没改了,大家可自行比对效率,本人数学不好不会证明ORZ)
更新的时候直接建块和Max值就可以了,而查询则是裸的分块,按块查询即可。注意处理边角块与负数问题。
还有,需要注意cin,洛谷输入格式依然坑爹。
在块大小sqrt(m)/2的情况下,复杂度应该是O(x\*sqrt(m)),其中x为加入的数的个数。~~说不定比mlogx快呢~~
```cpp
#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>
void read(T &x)
{
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;
}
```