牛课练习赛34 Flittle w and Discretization 主席树维护Mex

主席树维护Mex。

每个右端点 r 维护出一棵在[1, r ] 区间中其他所有的值离这个 r 最近的的位置是多少。

然后询问区间[L,R]的时候，从rt[R] 出发，然后如果左儿子的中所有出线位置的最小值 >= L, 则说明他们所有的点都出线在这个区间内了，然后往右走。

否则就说明左边有点没有出线过，需要往左走。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N =3e5+ ;

struct Node{

    int ls, rs, mn, num;

    Node(){ls = rs = mn = num = ;}

}tr[N<<];

int rt[N];

int tot;

int build(int l, int r){

    int x = ++tot;

    if(l == r) return x;

    int m = l+r >> ;

    tr[x].ls = build(l,m);

    tr[x].rs = build(m+,r);

    return x;

}

int Update(int L, int p, int lst, int l, int r){

    int x = ++tot;

    tr[x] = tr[lst];

    if(l == r){

        tr[x].mn = p;

        ++tr[x].num;

        return x;

    }

    int m = l+r >> ;

    if(L <= m) tr[x].ls = Update(L, p, tr[lst].ls, l, m);

    else tr[x].rs = Update(L, p, tr[lst].rs, m+, r);

    tr[x].mn = min(tr[tr[x].ls].mn, tr[tr[x].rs].mn);

    tr[x].num = tr[tr[x].ls].num + tr[tr[x].rs].num;

    return x;

}

int Query(int L, int x, int x2){

//    cout << L << ' ' << tr[x].mn << ' ' << tr[x].num - tr[x2].num << endl;

    if(tr[x].mn >= L) return tr[x].num - tr[x2].num;

    if(!tr[x].ls) return ;

    int ret = ;

    if(tr[tr[x].ls].mn >= L) ret = tr[tr[x].ls].num-tr[tr[x2].ls].num + Query(L,tr[x].rs,tr[x2].rs);

    else ret = Query(L,tr[x].ls,tr[x2].ls);

    return ret;

}

void Q(int p, int l, int r){

    cout << l << " " << r <<  " " << tr[p].mn << ' ' << tr[p].num << endl;

    if(l == r) return ;

    int m = l+r >> ;

    Q(tr[p].ls, l, m);

    Q(tr[p].rs, m+, r);

}

int a[N];

int main(){

    int n, m;

    scanf("%d", &n);

    rt[] = build(,n);

    for(int i = ; i <= n; ++i){

        scanf("%d", &a[i]);

        if(a[i] <= n) rt[i] = Update(a[i], i, rt[i-], , n);

        else rt[i] = rt[i-];

    }

//    Q(rt[4],1,n);

    scanf("%d", &m);

    int L, R;

    for(int i = ; i <= m; ++i){

        scanf("%d%d", &L, &R);

        printf("%d\n", (R-L+)-Query(L, rt[R], rt[L-]));

    }

    return ;

}