2019/5/30 day10 解题日志

2019-05-30

字数统计: 891字 | 阅读时长: 4分

题目链接

day10

给定一个序列A，求区间内最小未出现的自然数。

主席树O(nlogn)

思路

（话说这个$mex$计算不是在博弈求$sg$的吗……）

不妨用权值线段树维护区间内的数字出现位置的最小值，并且每次插入都维护当前数字出现位置。
那么由于查询的范围是$[l,r]$，可以知道如果左儿子的区间内，有数字最近出现的位置小于$l$，说明查询的区间$[l,r]$内不存在该值。
那么这道题就变成了一道喜闻乐见的模板题。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,q,m,tot;
int a[maxn],t[maxn];
int T[maxn],lson[maxn*22],rson[maxn*22],c[maxn*22];
bool vis[maxn+5];
int build(int l,int r){
    int root=tot++;
    c[root]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[root]=build(l,mid);
        rson[root]=build(mid+1,r);
    }
    return root;
}
int update(int root,int pos,int val,int l,int r){
    int newroot=tot++,tmp=newroot;
    c[newroot]=c[root];
    if(l==r){
        c[newroot]=val;
    } else {
        int mid=l+r>>1;
        lson[newroot]=lson[root];
        rson[newroot]=rson[root];
        if(pos<=mid)lson[newroot] = update(lson[root],pos,val,l,mid);
        else        rson[newroot] = update(rson[root],pos,val,mid+1,r);
        c[newroot] = min(c[lson[newroot]],c[rson[newroot]]);
    }
    return tmp;
}
int query(int root,int lim){
    int l=1,r=maxn;
    while(l<r){
        int mid=l+r>>1;
        if(c[lson[root]] < lim){
            r=mid;
            root=lson[root];
        }
        else{
            l=mid+1;
            root=rson[root];
        }
    }
    return l-1;
}
int main(){
    read(n,q);
    for(int i=1;i<=n;i++){
        read(a[i]);a[i]++;if(a[i]>maxn)a[i]=maxn;
    }
    T[0]=build(1,maxn);
    for(int i=1;i<=n;i++){
        T[i]=update(T[i-1],a[i],i,1,maxn);
    }
    int l,r;
    while(q--){
        read(l,r);
        print(query(T[r],l),"\n");
    }
    return 0;
}

离线 + 权值线段树

思路

这个做法其实就是主席树的离线版本，而且由于离线处理，就不需要将权值线段树可持久化了。

首先对询问进行排序，然后剩下的部分就跟“主席树”思路一模一样了。
用权值线段树维护区间内的数字出现位置的最小值，并且每次插入都维护当前数字出现位置。
那么由于查询的范围是$[l,r]$，可以知道如果左儿子的区间内，有数字最近出现的位置小于$l$，说明查询的区间$[l,r]$内不存在该值。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,q;
int a[maxn];
vector<pair<int,int> >vec[maxn];
int ans[maxn];

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid = l+r>>1

int minv[maxn<<2];
void update(int p,int v,int l,int r,int rt){
    if(l==r){minv[rt]=v;return;}
    intmid;
    if(p<=mid)update(p,v,lson);
    else      update(p,v,rson);
    minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
}
int query(int lim){
    int l=1,r=maxn,rt=1;
    while(l<r){
        intmid;
        if(minv[rt<<1]<lim){
            r=mid;
            rt=rt<<1;
        } else {
            l=mid+1;
            rt=rt<<1|1;
        }
    }return l-1;
}
int main(){
    read(n,q);
    for(int i=1;i<=n;i++){
        read(a[i]);a[i]++;if(a[i]>maxn)a[i]=maxn;
    }int l,r;
    for(int i=1;i<=q;i++){
        read(l,r);
        vec[r].push_back(make_pair(l,i));
    }
    for(int i=1;i<=n;i++){
        update(a[i],i,1,maxn,1);
        for(auto p:vec[i]){
            ans[p.second]=query(p.first);
        }
    }for(int i=1;i<=q;i++)print(ans[i],"\n");
    return 0;
}

分块

留坑。