题解 P1198 【[JSOI2008]最大数】

· · 题解

为啥没有线性做法 那我就补充一下吧

观察到查询等都在末尾进行,所以采用特殊做法

维护一个单调队列q,意义是以最后一个数字结束的一个单调递减的数组极大值

末尾增加一个点:将单调队列小于等于这个数的全部扣除,然后末尾增加一个数

查询[l,size]:从l往后找第一个在单调队列里的数就是结果

总不能一个一个找吧,于是采用二分查找,复杂度O(nlogn),代码贼短~

#include<bits/stdc++.h>
#define M 200005
using namespace std;
int m,p,t,x,sz,r,a[M],q[M];
char ch;
int main() {
    scanf("%d%d",&m,&p);
    for(int i=1; i<=m; i++) {
        scanf("%s%d",&ch,&x);
        if(ch=='A') {
            a[++sz]=(x+t)%p;
            while(r&&a[q[r-1]]<a[sz])r--;
            q[r++]=sz;
        } else if(ch=='Q')printf("%d\n",t=a[*lower_bound(q,q+r,sz-x+1)]);
    }
    return 0;
}

但这个是O(nlogn)的,离线性还差一步

于是再次开脑洞......

将i与从i往后找第一个在单调队列里的数的下标合并在一个集合,并使这个集合的根为后者

于是查询时只需找它所在集合的根就行了

容易发现可以通过并查集来实现

什么时候进行并操作时呢?很简单,只要在出队时合并就行了

这是因为每个数都会进队一次,在出队时它一定是队列的尾部,所以直接向i合并就可以了

这个时间复杂度就是O(nalpha(n))可以视为O(n),因为alpha(n)<=4,只是一个较小常数

代码也就长了一行,而且是线性的

#include<bits/stdc++.h>
#define M 200005
using namespace std;
int m,p,t,x,sz,r,a[M],q[M],id[M];
inline int getr(int i){return i==id[i]?i:id[i]=getr(id[i]);}
inline void unite(int u,int v){id[getr(u)]=getr(v);}
char ch;
int main() {
    scanf("%d%d",&m,&p);
    for(int i=1; i<=m; i++) {
        scanf("%s%d",&ch,&x);
        if(ch=='A') {
            a[++sz]=(x+t)%p;id[sz]=sz;
            while(r&&a[q[r-1]]<a[sz])unite(q[r-1],sz),r--;
            q[r++]=sz;
        } else if(ch=='Q')printf("%d\n",t=a[getr(sz-x+1)]);
    }
    return 0;
}

不过如果是任意区间查询的话,那就不行了,因为答案可能不在单调队列里面,例如a={1,2,3,4,5},则q={5},要查max[1,1],那就挂了

不过如果要求的是和,那怎么办呢?

这就很简单啦,根本不需要用这种方法,直接前缀和就行了,千万别去写线段树哦!