[CF369E] Valera and Queries

Description

给定 (n) 条线段 ([l_i,r_i])，有 (m) 个询问，每次给定若干个点，问多少线段能至少覆盖这些点中的一个。

Solution

补集转化，求多少线段一个点也不能覆盖。

点将数轴分割成了一个线段集，即求有多少原始线段是包含在询问线段集中的一个线段中的。

要询问一个线段包含的原始线段个数，考虑离线处理，用树状数组维护即可。

具体地，按右端点排序后扫描，扫到一个原始线段就在树状数组的左端点位置加一，扫到一个询问线段就直接扫描部分的后缀和来统计答案（扫描顺序保证了右端点顺序，后缀和保证了左端点关系，故询问线段包含了原始线段）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2000005;

int n,m,cnt,p[N];

struct Segment
{
    int l,r,ans;
    bool operator < (const Segment &obj)
    {
        return r < obj.r;
    }
} seg[N];

vector <Segment> segq;
vector <int> qid[N];
vector <int> segque[N],segsrc[N];

int ar[N]; // index: 1 ~ N
int lowbit(int t)
{
    return t & (-t);
}
void add(int i, int v)
{
    for (; i < N; ar[i] += v, i += lowbit(i));
}
int sum(int i)
{
    if(i==0) return 0;
    int s = 0;
    for (; i > 0; s += ar[i], i -= lowbit(i));
    return s;
}
int query(int l,int r)
{
    return sum(r)-sum(l-1);
}
signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    int mx=1e6+1;
    for(int i=1; i<=n; i++)
    {
        int t1,t2;
        cin>>t1>>t2;
        seg[i]={t1,t2,0};
        segsrc[t2].push_back(i);
        mx=max(mx,max(t1,t2));
    }
    for(int i=1; i<=m; i++)
    {
        int cnt,t,last=0;
        cin>>cnt;
        while(cnt--)
        {
            cin>>t;
            if(t-last>1)
            {
                qid[i].push_back(segq.size());
                segque[t-1].push_back(segq.size());
                segq.push_back({last+1,t-1});
            }
            last=t;
        }
        {
            int t=1e6+1;
            if(t-last>1)
            {
                qid[i].push_back(segq.size());
                segque[t-1].push_back(segq.size());
                segq.push_back({last+1,t-1});
            }
            last=t;
        }
    }
    for(int i=1; i<=mx; i++)
    {
        for(int tid:segsrc[i])
        {
            Segment &tmp=seg[tid];
            add(tmp.l, 1);
            //cout<<"modify "<<tmp.l<<endl;
        }
        for(int tid:segque[i])
        {
            Segment &tmp=segq[tid];
            tmp.ans=query(tmp.l,tmp.r);
            //cout<<"tid="<<tid<<" ans="<<tmp.ans<<endl;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int ans=n;
        for(int tid:qid[i])
        {
            //cout<<"calling tid="<<tid<<endl;
            Segment &tmp=segq[tid];
            ans-=tmp.ans;
        }
        cout<<ans<<endl;
    }
}