题解：CF1774G Segment Covering

潘德理2010 · 2026-07-21 21:26:34 · 题解

发现题目让我们求的东西是偶数减去奇数，比较特殊，肯定需要从其中挖掘性质。

发现，如果一个线段被另一个完全包含，那么在选择长线段的时候，短线段选不选都一样，那么选和不选就抵消了。所以我们可以直接扔掉长线段，得到若干个互不包含的线段。

考虑如何求解答案。令 f_i 为，第 i 条线段及以前的线段，覆盖 r_i 及以前的位置的答案。不难列出式子 f_i=-\sum\limits_{j<i}f_j[r_j\ge l_i]。这个式子没有办法直接求解，继续挖掘其性质。我们手玩一下，得到结论如下：

令 u=1,v=2，此时有 f_u=1,f_v=-1。然后执行 u\gets to_u,v\gets to_v，仍有 f_u=1,f_v=-1。重复上述过程。若 u=v 则无解。

使用倍增模拟上述过程即可。注意边界条件以及无解的判断。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int p=998244353;
struct seg{
    int l,r;
    bool operator<(const seg &a)const{
        if(l!=a.l) return l<a.l;
        return r<a.r;
    }
}a[N];
int n,q;
int f[N][20];
void trans(){
    int m=0;
    sort(a+1,a+n+1,[&](const seg &a,const seg &b){
        if(a.r!=b.r) return a.r<b.r;
        return a.l>b.l;
    });
    for(int i=1;i<=n;i++){
        if(m==0||a[i].l>a[m].l){
            a[++m]=a[i];
        }
    }
    n=m;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].r--;
    }
    trans();
    for(int i=1;i<=n;i++){
        f[i][0]=lower_bound(a+1,a+n+1,seg{a[i].r+2,0})-a;
    }
    f[n+1][0]=n+1;
    for(int j=1;j<=17;j++){
        for(int i=1;i<=n+1;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    while(q--){
        int l,r,x,y;
        cin>>l>>r;
        r--;
        x=lower_bound(a+1,a+n+1,seg{l,0})-a;
        int le=1,ri=n;
        while(le<=ri){
            int mid=(le+ri)>>1;
            if(a[mid].r<=r){
                le=mid+1;
                y=mid;
            }
            else{
                ri=mid-1;
            }
        }
        if(a[x].l!=l||a[y].r!=r){
            cout<<"0\n";
            continue;
        }
        int u=x,v=x+1;
        for(int j=17;j>=0;j--){
            int tu=f[u][j],tv=f[v][j];
            if(tu<=y){
                u=tu;
            }
            if(tv<=y){
                v=tv;
            }
        }
        if(u==v){
            cout<<"0\n";
        }
        else if(u==y){
            cout<<p-1<<"\n";
        }
        else if(v==y){
            cout<<"1\n";
        }
        else{
            cout<<"0\n";
        }
    }
}