AHSOFNU NOIP模拟题-3 T4/BZOJ 3339(离线+线段树)

发表于 | 分类于 | | + s

此题在线做很麻烦，而且这题也不强制在线，不会修改$A$的值，那就离线吧。
先求出$[1, i]$的$mex$值，然后求出$nxt$值，即下一个为该数值的下标，没有就是$0$，可以很容易$O(n)$推出来
然后考虑从$A[1]$开始删数，即考虑$A[i]$对后面的$mex$值的影响
可以发现，删去$A[i]$后，$i$到$nxt[i]-1$都会受影响，并且这个范围内$mex$大于$A[i]$的都要等于$A[i]$，这里的修改可以线段树完成，有点麻烦。那么对查询区间按左端点排序，然后依次删数，发现一个区间的$mex$值就是线段树上单点查询右端点的值。(实际上线段树上单点查询$i$表示为删了几个数$+1$到$i$之间的$mex$值)

注意此题卡输入，一定要输入优化，以后做题要测一测极限数据，看看大概时间，如果输入数据很大的话，也要考虑输入优化。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "mex"
using namespace std;
const int MAXN = 200000 + 5, INF = 1000000000;
struct inv {
    int no, l, r;
    bool operator < (const inv &b) const {
        return l < b.l;
    }
}qj[MAXN];
int n, q, A[MAXN], mex[MAXN], mk[MAXN], nxt[MAXN], ans[MAXN];
#define M ((l+r)>>1)
#define lc (o<<1)
#define rc (o<<1|1)
int lazy[MAXN*4];
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
void pushdown(int o, int l, int r) {
    if (lazy[o]!=INF) {
        if (l!=r) lazy[lc] = min(lazy[lc], lazy[o]);
        if (l!=r) lazy[rc] = min(lazy[rc], lazy[o]);
    }
}
void build(int o, int l, int r) {
    if (l==r) lazy[o] = mex[l]; else lazy[o] = INF, build(lc, l, M), build(rc, M+1, r);
}
void update(int o, int l, int r, int x, int y, int w) {
    pushdown(o, l, r);
    if (x<=l&&r<=y) {
        lazy[o] = min(lazy[o], w);
        return ;
    }
    if (x<=M) update(lc, l, M, x, y, w);
    if (M<y) update(rc, M+1, r, x, y, w);
}
int query(int o, int l, int r, int p) {
    pushdown(o, l, r);
    if (l==r) {
        return lazy[o];
    }
    if (p<=M) return query(lc, l, M, p);
        else if (M<p) return query(rc, M+1, r, p);
}
void clean() {
    ms(mk, false), ms(nxt, 0);
}
void solve() {
    clean();
    int k = 0;
    for (int i=1;i<=n;i++) {
        A[i] = read();
        mk[A[i]] = true;
        if (mk[k]) {
            while (mk[k]) k++;
        }
        mex[i] = k;
    }
    ms(mk, false);
    for (int i=n;i>0;i--) {
        nxt[i] = mk[A[i]];
        mk[A[i]] = i;
    }
    build(1,1,n);
    for (int i=1;i<=q;i++) qj[i].l = read(), qj[i].r = read(), qj[i].no = i;
    sort(qj+1, qj+1+q), k = 1;
    for (int i=1;i<=q;i++) {
        while (k!=qj[i].l) {
            if (nxt[k]==0) update(1,1,n,k,n,A[k]); else update(1,1,n,k,nxt[k]-1,A[k]);
            k++;
        }
        ans[qj[i].no] = query(1,1,n,qj[i].r);
    }
    for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}
int main() {
    freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
    scanf("%d%d", &n, &q), solve();
    fclose(stdin); fclose(stdout);
    return 0;
}
------ 本文结束 ------