解题报告

题解里有个很厉害的 $O((n+s)log_2n)​$ 做法，但是我不会……我只会这种比较好想的做法。

首先这明显是一个二分图完全匹配问题，我们可以把每项工作 $K_i$ 看成 $K_i$ 个点，然后如果 $L_j\le K_i\le R_j$ 那么 $j$ 这个宠物就向工作 $i$ 连边，我们要验证是否对于所有工作的集合 $S$ ，都有 $|E(S)|\ge |S|$ 。

考虑DP，将工作排序之后，定义 $f_i$ 表示前 $i$ 个工作 $i$ 必选时 $|E(S)|-|S|$ 的最小值，如果 $\exists i,f_i<0$ 就凉了。转移时我们需要枚举 $j$ 表示上一次选的工作，这次多出来的 $E(S)$ 就是 $L_j\in(K_j,K_i],R_j\in[K_i,n]$ 的 $j$ ，可以通过主席树预处理，而多出来的 $S$ 就是 $K_i$ 。这样DP时间复杂度为 $O(m^2log_2n)$ ，这非常的凉凉。

我们发现 $K_i$ 相同的工作可以合并起来（因为 $E(S)$ 是一样的），所以可以将 $K_i$ 排序去重，又因为 $\sum K_i\le n$（否则显然无解） ，所以只会剩下 $O(\sqrt n)$ 种不同的 $K_i$ ！就可以把复杂度降到 $O(s\sqrt nlog_2n)$ 啦。

因为这个复杂度还是很危险，需要搞点预处理之类的QAQ……

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const int maxn=500000,maxm=200000,maxt=1e7;

int n,te,si,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5];
vector<int> a[maxn+5];int m,K[maxm+5],cnt[2005][2005],val[maxm+5],f[maxm+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
int Insert(int p,int pos,int l=1,int r=n){
    int now=++si;ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;if (l==r) return now;int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);return now;
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return 0;if (L==l&&r==R) return sum[p];int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1,L,R;i<=n;i++) readi(L),readi(R),a[R].pb(L);
    for (int i=n;i;i--) {ro[i]=ro[i+1];for (int j=0,si=a[i].size();j<si;j++) ro[i]=Insert(ro[i],a[i][j]);}
    for (int i=1;i<=2000&&i<=n;i++) for (int j=1;j<=i;j++) cnt[i][j]=Ask(ro[i],j,i);
    for (readi(te);te;te--){
        readi(m);int sum=0;for (int i=1;i<=m;i++) readi(K[i]),sum+=K[i];
        if (sum>n) {puts("0");continue;}sort(K+1,K+1+m);int tot=m;m=1;val[m]=K[1];
        for (int i=2;i<=tot;i++) if (K[i]!=K[i-1]) K[++m]=K[i],val[m]=K[i]; else val[m]+=K[i];
        for (int i=1;i<=m;i++){
            f[i]=Ask(ro[K[i]],1,K[i])-val[i];if (f[i]<0) goto END;
            for (int j=1;j<i;j++){
                int now=(K[i]<=2000?cnt[K[i]][K[j]+1]:Ask(ro[K[i]],K[j]+1,K[i]));
                f[i]=min(f[i],f[j]+now-val[i]);if (f[i]<0) goto END;
            }
        }puts("1");continue;END:puts("0");
    }return 0;
}