题解 P1198 【[JSOI2008]最大数】

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快呢

#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;
}