万恶的标题党啊~

这个题明显扫描线辣……但是怎么扫呢？

我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值，然后用线段树维护。

从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时，需要将[tex][l,next[l]-1][/tex]（[tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置）中的所有大于[tex]A[l][/tex]（[tex]l[/tex]的值）的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats？

答案是否定的。注意到我们真正需要的只是叶子结点，所以其他非叶子结点的最小值全部弄成无限大，然后这样做就可以把最小值当做标记来弄了……非常精巧。

代码：

/**************************************************************
    Problem: 3339
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1988 ms
    Memory:10396 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=A[L];
    }else{
        int M=L+(R-L)/2;
        minv[o]=INF;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
    }
}
inline void paint(int o,int v){
    minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
    paint(o<<1,minv[o]);
    paint(o<<1|1,minv[o]);
    minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
    if(L==R)
        return minv[o];
    if(minv[o]<INF)
        pushdown(o);
    int M=L+(R-L)/2;
    if(pos<=M)
        return query(o<<1,L,M);
    else
        return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
    if(ql<=L && R<=qr){
        paint(o,v);
    }else{
        if(minv[o]<INF)
            pushdown(o);
        int M=L+(R-L)/2;
        if(ql<=M)
            update(o<<1,L,M);
        if(qr>M)
            update(o<<1|1,M+1,R);
    }
}
 
inline int readint(){
    register int x=0;
    register char c;
    fread(&c,1,1,stdin);
    while(!isdigit(c))
        fread(&c,1,1,stdin);
    while(isdigit(c)){
        x=x*10+c-'0';
        fread(&c,1,1,stdin);
    }
    return x;
}
int buf[21];
inline void putint(int x){
    register int i,p=0;
    if(!x){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
 
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
    int id;
    int l,r;
    int ans;
};
bool cmp1(const Query& x,const Query& y){
    if(x.l==y.l)
        return x.r<y.r;
    else
        return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
    return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
    int n,q;
    register int i,l=1,k=0;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++){
        V[i]=readint();
        vis[V[i]]=true;
        if(k==V[i])
            while(vis[k])
                k++;
        A[i]=k;
    }
    build_tree(1,1,n);
    for(i=n;i>=1;i--){
        if(!last[V[i]])
            next[i]=n+1;
        else
            next[i]=last[V[i]];
        last[V[i]]=i;
    }
    for(i=1;i<=q;i++){
        QS[i].id=i;
        QS[i].l=readint();
        QS[i].r=readint();
    }
    sort(QS+1,QS+1+q,cmp1);
    for(i=1;i<=q;i++){
        while(l<QS[i].l){
            ql=l;
            qr=next[l]-1;
            v=V[l];
            update(1,1,n);
            l++;
        }
        pos=QS[i].r;
        QS[i].ans=query(1,1,n);
    }
    sort(QS+1,QS+1+q,cmp2);
    for(i=1;i<=q;i++){
        putint(QS[i].ans);
    }
    return 0;
}

• 相关文章
• 全局相关文章