Luogu P1198 [JSOI2008]最大数单调队列/ST表

布满荆棘的人生 2021-11-17 15:28 201阅读 0赞

开一个单调队列，下标递增，值递减。

然后在上面二分最大数。

如果加上并查集可以做到接近线性。

还有一种是插入一个数然后，从后向前更新ST表。

#include<cstdio>
    #include<iostream>
    #define R register int
    using namespace std;
    inline int g() {
        R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
        do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
    } const int N=200010;
    int n,M,cnt,top,t;
    int a[N],q[N];
    signed main() {
        n=g(),M=g(); for(R i=1,x;i<=n;++i) { register char s[2];
            scanf("%s",s),x=g(); if(s[0]=='A') {
                a[++cnt]=(x+t)%M;
                while(top&&a[q[top]]<a[cnt]) --top;
                q[++top]=cnt;
            } else if(s[0]=='Q') printf("%d\n",t=a[*lower_bound(q+1,q+top+1,cnt-x+1)]);
        }
    }

ST表：

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #define ll long long
    #define R register ll
    using namespace std;
    namespace jack {
        #define db double 
        int n,m; ll t,d,ans,a[200010],f[200010][21]; bool flg;
        inline int max(int a,int b) {
        return a>b?a:b;}
        inline void change(int u) {f[u][0]=a[u]; for(R i=1;u-(1<<i)>=0;i++) f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);}//反向ST表    
        inline ll find(int a,int b) {db t=log2(b-a+1); R k=t; return max(f[b][k],f[a+(1<<k)-1][k]);}
        inline ll g() {
            R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
            do ret=(ret<<3)+(ret<<1)+(ch^48); while(isdigit(ch=getchar())); return fix*ret;
        }
        inline void main() {
            m=g(),d=g();
            for(R i=1;i<=m;i++) {
                register char ch;
                while(!isalpha(ch=getchar())); 
                if(ch=='A') {R x=g();a[++n]=(x+t)%d,change(n);}
                else {
                    R l=g(); if(l==1) {printf("%lld\n",a[n]),t=a[n];continue;}
                    ans=find(n-l+1,n);
                    printf("%lld\n",ans); t=ans;
                }
            }
        }
    }
    signed main() {jack::main();}

--------------------

2019.07.03

转载于:https://www.cnblogs.com/Jackpei/p/11128624.html