出题人题解 | #little w and Discretization#

原题解链接：https://ac.nowcoder.com/discuss/150260

问你区间做离散化后有多少个数字的值发生了变化。然后离散化的时候如果区间里面是 $1$ 到某个连续的数字都已经存在的,这些数字的值就不需要变化。

然后这个题就是一步区间 $m e x$ ,求出来以后再来一步求区间内值域在某一个范围的数字的个数。

然后想卡掉 $l o g^{2}$ 的做法,可能时限给的有点紧。标程是两次离线 $n l o g$ 的复杂度。

但是跑的太快也就400ms的速度。

标程: 链接https://ac.nowcoder.com/acm/contest/view-submission?submissionId= 38180525

跟求区间元素种类数类似。我们从左到右遍历整个数组,过程中维护每个数字最后一次出现的位置。记为 $l a s t$ 数组,这个数组用一个权值线段树维护。

树上每个节点维护值域内 $l a s t$ 最靠左的位置。对于每个查询 $l, r$ ,在遍历到位置 $r$ 的时候,在权值线段树中二分,如果值域内所有的数字全部在 $l$ 内出现过。

那么就走线段树的右子树,否则走线段树的左子树。然后将第一次离线的结果作为第二次离线的查询。这次只要求区间内值域在某个范围内的数字个数即可。

当然验题的时候,验题人使用的解法更多,可以先整体二分求出所有区间的 $m e x$ ,再离线或者主席树,或者两步都是主席树(可能会炸内存) ,然后也能莫队+离线再用读入挂怼过去。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+1000;
//int a[maxn];
set<pair<int,int> > heap[maxn];
struct Seg_Tree{
    pair<int,int> Min[maxn*4];
    Seg_Tree(){
        for (int i=0;i<maxn*4;i++){
            Min[i] = {0x3f3f3f3f,-1};
        }
    }
    void up(int x){
        Min[x] = min(Min[x<<1],Min[x<<1|1]);
    }
    void update(int x,int l,int r,int pos,pair<int,int> Val){
        if (l == r){
            Min[x] = Val;
            return;
        }
        int mid = l+r >>1;
        if (pos <= mid)update(x<<1,l,mid,pos,Val);
        else update(x<<1|1,mid+1,r,pos,Val);
        up(x);
    }
    pair<int,int> query(int x,int l,int r,int L,int R){
        if (l>R || L>r)return {0x3f3f3f3f,-1};
        if (L<=l && r<=R)return Min[x];
        int mid = l+r >>1;
        return min(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
    }
}tree;
int n,m;
int ans [maxn];
pair<int,int> query[maxn];
vector<int> pos[maxn];
vector<int> rans[maxn];
struct BIT{
    int sum[maxn];
    int lowbit(int x){
        return x & -x;
    }
    void add(int x){
        while (x<maxn){
            sum[x] ++;
            x += lowbit(x);
        }
    }
    int query(int x){
        int res = 0;
        while (x){
            res += sum[x];
            x -= lowbit(x);
        }
        return res;
    }
    int query(int l,int r){
        return query(r) - query(l-1);
    }
}bit,bit2;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        int temp;
        scanf("%d", &temp);
        temp = min(temp, n + 1);
        pos[temp].push_back(i);
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        query[i] = {l,r};
        heap[l].insert({r,i});
    }
    for (int i=1;i<=n;i++){
        if (!heap[i].empty())tree.update(1,1,n,i,*heap[i].begin());
    }
    for (int i=1;i<=n;i++){
        if (pos[i].empty())continue;
        pos[i].push_back(n+1);
        int L = 1;
        for (int x:pos[i]){
            int R = x;
            while (1){
                if (R<=L)break;
                pair<int,int> pr = tree.query(1,1,n,L,R-1);
                if (pr.first >=R)break;
                ans[pr.second] = i;
                pair<int,int> q = query[pr.second];
                heap[q.first].erase({q.second,pr.second});
                pair<int,int> newVal = {0x3f3f3f3f,-1};
                if (!heap[q.first].empty()){
                    newVal = *heap[q.first].begin();
                }
                tree.update(1,1,n,q.first,newVal);
            }
            L = x+1;
        }
    }
    for (int i=1;i<=m;i++){
        rans[ans[i]].push_back(i);
    }
    memset(ans,-1,sizeof ans);
    for (int i=1;i<=n;i++){
        for (int idx : rans[i]){
            ans[idx] = bit.query(query[idx].first,query[idx].second);
        }
        for (int x : pos[i]){
            if (x == n+1)continue;
            bit.add(x);
        }
    }
    for (int x : pos[n+1]){
        bit2.add(x);
    }
    for (int i=1;i<=m;i++){
        int out = query[i].second - query[i].first +1;
        if (ans[i]!=-1){
            out -= ans[i];
        }else{
            out =bit2.query(query[i].first,query[i].second);
        }
        printf("%d\n",out);
    }
}
/*
 5
1 6 2 1 1
5
1 3
3 5
1 5
2 2
 3 3
 */