题解 P1198 【[JSOI2008]最大数】

teafrogsf

2017-11-03 11:36:38

Solution

## 我真的没想到,分块居然过了这题而且跑得比线段树快得多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; } ```