题解：P7968 [COCI 2021/2022 #2] Osumnjičeni

· · 题解

模拟赛 T3，感觉评不了紫。赛时因为忘调用 build没调出来……

题目大意：给你 n 个区间 [l_i,r_i] 和 q 个询问 [p_i,q_i]，对每个询问，求最少将 [p_i,q_i] 内的区间划为多少部分，使得：每部分下标连续并且该部分的区间交集为空。

有一个显然的贪心想法就是对于每个部分，尽可能让其越长越好，因为这样后面剩的的线段越少越不容易有交集，于是我们对于每个位置 i，求 f_i=\max\limits_{j\ge i,\bigcap\limits_{k=i}^j=\text{\o}} j。也就是以 i 为左端点，最右端的右端点。

考虑这个东西怎么求，由于交集运算具有单调性，也就是若 \bigcap\limits_{k=i}^j [l_k,r_k]\ne \text{\o}，则 \bigcap\limits_{k=i}^{j+1} [l_k,r_k]\ne \text{\o}；若 \bigcap\limits_{k=i}^j [l_k,r_k]= \text{\o}，则 \bigcap\limits_{k=i+1}^j [l_k,r_k]= \text{\o}。

于是可以双指针求，那怎么判断加入一个区间会不会产生交集呢？由于我们已经扫了 [i,j-1] 的区间了，也就是这里面的区间两两无交，那么只需要判断区间 j 和这些区间是否有交即可。这个可以离散化一下用线段树维护。

求出 f 之后，每次询问相当一个这样的过程：重复 l=f_l+1，问最少多少次后 l\ge r。于是就可以倍增轻松实现。

代码：

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e5+5;
int n,q,f[N][20],b[N<<1],l[N],r[N],m,ls[N<<2],rs[N<<2],sum[N<<2],cnt,tag[N<<2];
void build(int &u,int l,int r){u=++cnt;if(l==r) return;build(ls[u],l,mid),build(rs[u],mid+1,r);}
void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];}
void pushdown(int u,int l,int r){
    sum[ls[u]]+=(mid-l+1)*tag[u],sum[rs[u]]+=(r-mid)*tag[u];
    tag[ls[u]]+=tag[u],tag[rs[u]]+=tag[u],tag[u]=0;
}
void add(int u,int l,int r,int L,int R,int val){
    if(L<=l&&r<=R){tag[u]+=val,sum[u]+=(r-l+1)*val;return;}
    pushdown(u,l,r);
    if(L<=mid) add(ls[u],l,mid,L,R,val);
    if(mid<R) add(rs[u],mid+1,r,L,R,val);
    pushup(u);
}
int query(int u,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[u];
    pushdown(u,l,r);int res=0;
    if(L<=mid) res+=query(ls[u],l,mid,L,R);
    if(mid<R) res+=query(rs[u],mid+1,r,L,R);
    return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i],b[++m]=l[i],b[++m]=r[i];
    cin>>q;sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;build(b[0],1,m);
    for(int i=1;i<=n;i++) l[i]=lower_bound(b+1,b+1+m,l[i])-b,r[i]=lower_bound(b+1,b+1+m,r[i])-b;
    for(int i=1,j=0;i<=n;i++){
        while(j<n&&!query(1,1,m,l[j+1],r[j+1])) j++,add(1,1,m,l[j],r[j],1);
        f[i][0]=j+1,add(1,1,m,l[i],r[i],-1);
    }
    for(int k=1;k<=17;k++)for(int i=1;i<=n;i++) f[i][k]=f[f[i][k-1]][k-1];
    for(int i=1,u,v;i<=q;i++){
        cin>>u>>v;int ans=0;
        for(int k=17;~k;k--) if(f[u][k]&&f[u][k]<=v) u=f[u][k],ans|=1<<k;
        cout<<ans+1<<'\n';
    }
    return 0; 
}