P4137 Rmq Problem / mex 题解

· · 题解

前言

好久没用整体二分发电了。

正文

注意到实际上 mex 是可以二分的。

对于全局 mex 我们可以二分 mex 是哪个值。

check 为是否区间内比 x（假设当前二分答案为 x）小的个数是否等于 x+1 是则记录答案为 x+1 并 l=mid+1；不是则 r=mid-1。

这是显然正确的吧。

那么对于区间查询 mex，只需要更改 check，改为满足该条件下的 dp 的 f_x 数值是否等于 x+1。

条件：

  1. a_i < a_j
  2. L \leqslant i \leqslant R
  3. L \leqslant j \leqslant R
  4. a_j \leqslant x

其中 L、R 为查询区间。

注意到可以使用类似于扫描线的方法，询问和插入均按照右端点或下标从小到大排序，之后用整体二分二分 x 每个能做贡献的数值只保留与其相同数值中下表最大的那一个放进树状数组，之后查询是否满足要求，就完了。

可能会有一些细节但不多。

代码

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define N 1000005
using namespace std ;
int n , q , tr[N] , last[N] , ans[N] , cnt=0 , num=0 ;
void change(int x,int k) {
    while(x<=n+1) {
        tr[x] += k ;
        x += lowbit(x) ;
    }
}
int ask(int x) {
    int ans=0 ;
    while(x) {
        ans += tr[x] ;
        x -= lowbit(x) ;
    }
    return ans ;
}
struct node {
    int x , i , l , r , opt , k , tm ;
    bool operator <(const node &a)const {
        return this->tm>a.tm ;
    }
} a[N],q1[N],q2[N];
void solve(int l,int r,int L,int R) {
    if(l>r||L>R) return ;
    int mid=(l+r)>>1 , tot1=0 , tot2=0 ;
    for(int i=L; i<=R; i++) {
        if(a[i].opt==1) {
            if(a[i].x<=mid){
                if(last[a[i].x]) change(last[a[i].x],-1) ;
                last[a[i].x] = a[i].i ;
                change(a[i].i,1) ;
                q1[++tot1] = a[i] ;
            } else q2[++tot2] = a[i] ;
        } else {
            int x=ask(a[i].r)-ask(a[i].l-1) ;
            if(a[i].k+x<=mid) q1[++tot1] = a[i] ;
            else if(x+a[i].k==mid+1) {
                ans[a[i].i] = mid+1 ;
                a[i].k += x ;
                q2[++tot2] = a[i] ;
            } else exit(114514) ;
        }
    }
    for(int i=1; i<=tot1; i++) {
        a[i+L-1] = q1[i] ;
        if(q1[i].opt==1) {
            if(last[q1[i].x]) {
                change(last[q1[i].x],-1) ;
                last[q1[i].x] = 0 ;
            }
        }
    }
    for(int i=1; i<=tot2; i++) a[i+L-1+tot1] = q2[i] ;
    if(l!=r) solve(l,mid,L,L+tot1-1) ;
    solve(mid+1,r,L+tot1,R) ;
}
int read() {
    int x=0 ;
    char a=getchar() ;
    while(!(a>='0'&&a<='9')) a = getchar() ;
    while(a>='0'&&a<='9') {
        x *= 10 ;
        x += a-'0' ;
        a = getchar() ;
    }
    return x ;
}
bool cmp(node a,node b) {
    return a.r==b.r?a.tm<b.tm:a.r<b.r ;
}
int t[N] ;
signed main(){
    n = read() , q = read() ;
    for(int i=1; i<=n; i++) {
        int temp=read() ;
        cnt++ ;
        a[cnt].opt = 1 , a[cnt].k = 1 , a[cnt].x = temp , a[cnt].r = a[cnt].i = i , a[cnt].tm = cnt ;
    }
    for(int i=1; i<=q; i++) {
        int x , y ;
        x = read() , y = read() ;
        cnt++ ;
        a[cnt].i = ++num , a[cnt].opt = 2 , a[cnt].l = x , a[cnt].r = y , a[cnt].tm=cnt ;
    }
    sort(a+1,a+1+cnt,cmp) ;
    solve(0,n+1,1,cnt) ;
    for(int i=1; i<=num; i++) printf("%d\n",ans[i]) ;
    return 0 ;
}

废话

本人模拟赛做该题的待修版（单点），把 check 推成了等于 x 就行，实际上这道题的样例已经否定了这种写法，希望大家不要像我一样犯这种高级错误（实际上还有 multiset 用 end 查最大值这种发电操作）。