5861

myee · 2023-06-09 16:32:46 · 题解

前言

不会正解，所以写了个根号做法。

思路

先考虑 q=1 怎么做。

我们考虑贪心，从小到大扫描线，遇上左边界就插入有边界的小根堆，遇上需求就弹出对应个数的堆顶元素，遇上右边界就弹出堆顶元素（如果存在的话）。

当某个需求无法解决时直接无解，否则必然有解。

考虑 q>1 的情况。

我们考虑求出覆盖一段区间的需求的人的数目是多少。这样每次本质不同的人只有 O(\min(m^2,n)) 种。

直接主席树是 O(m\sqrt n\log n) 的，不优。

考虑根号平衡，我们把人按左端点排序，每 \sqrt n 个分一块，每个块内的人再按右端点逆序排序。记录每个位置对应多少个前 k 个块内的人，查询时再额外统计散块的贡献。

这样我们就知道每段需求区间被多少个人完全覆盖，进一步通过容斥得到恰好覆盖。

这样就把人划分成了 O(\min(m^2,n)) 种。

然后暴力模拟前面的贪心，容易做到 O(m\sqrt n)。

总复杂度 O((n+m)\sqrt n)，空间 O(n\sqrt n)。

平衡复杂度时块长取 3000 实际跑得很快。

由于洛谷上的版本来自 bzoj，允许离线，所以空间其实可以做到 O(n)。不过我懒，所以直接写了空间根号的做法。

Code

代码很好写。

const uint Block=3000,Lim=500000;
std::pair<uint,uint>P[Lim+5];
uint C[Lim/Block+5][Lim+5],F[Lim/Block+5];
uint W[1005][1005],n,c;
bol solve(std::vector<uint>S)
{
    std::vector<uint>A,B;
    std::sort(S.begin(),S.end());uint v=0;
    for(auto s:S)
    {
        if((v+=s)>n)return false;
        if(A.size()&&A.back()==s)B.back()+=A.back();else A.push_back(s),B.push_back(s);
    }
    for(uint i=0,p,r;i<A.size();i++)
    {
        p=0;while(p+1<c&&F[p+1]<=A[i])p++;
        r=std::min((p+1)*Block,n);
        for(uint j=A.size()-1,k=p*Block,c=0;j>=i&&~j;j--)
        {
            while(k<r&&P[k].second>=A[j])c+=P[k++].first<=A[i];
            W[i][j]=c+C[p][A[j]];
        }
    }
    for(uint i=0;i<A.size();i++)for(uint j=0;i+j<A.size();j++)
    {
        if(j)W[j][i+j]-=W[j-1][i+j];
        if(i+j+1<A.size())W[j][i+j]-=W[j][i+j+1];
        if(j&&i+j+1<A.size())W[j][i+j]+=W[j-1][i+j+1];
    }
    for(uint i=0;i<A.size();i++)
    {
        for(uint j=i;j<A.size();j++)if(B[i]>=W[i][j])B[i]-=W[i][j],W[i][j]=0;else W[i][j]-=B[i],B[i]=0;
        if(B[i])return false;
        for(uint j=i+1;j<A.size();j++)W[i+1][j]+=W[i][j];
    }
    return true;
}
int main()
{
    uint q;scanf("%u",&n);for(uint i=0;i<n;i++)scanf("%u%u",&P[i].first,&P[i].second);
    std::sort(P,P+n);
    for(uint j=0,r;j<n;j+=Block)
    {
        F[j/Block]=P[j].first;
        std::sort(P+j,P+(r=std::min(j+Block,n)),
            [&](std::pair<uint,uint>a,std::pair<uint,uint>b){return a.second>b.second;}),c++;
        for(uint k=0;k<r;k++)C[c][P[k].second]++;
        for(uint k=n;k;k--)C[c][k-1]+=C[c][k];
    }
    scanf("%u",&q);
    while(q--)
    {
        uint m;scanf("%u",&m);
        std::vector<uint>S(m);
        for(auto&v:S)scanf("%u",&v);
        puts(solve(S)?"1":"0");
    }
}