BZOJ2794: [Poi2012]Cloakroom 离线+背包

题解：

就是给定$q$个区间A，再给定$n$个区间B，对于每个区间A询问是否存在一个区间B的集合使得每个B区间都完全包含A区间同时所有B区间的权值和与这个A区间的权值相同。

考虑离线将所有A,B按照左端点区间排序，依次枚举区间B，每次在背包中添加左端点$\leq$B区间左端点的A区间，在维护能够凑成的同时维护若能够凑成，A区间集合右端点最小值的最大值是多少。

这样就能实现$O(1)$回答询问。

时间复杂度$O(qlogq+nlogn+nk)$。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
bool f[2][100010];
int g[2][100010];
bool ok[1000010];
struct Que{
    int m,k,s,lab;
    Que(){}
    Que(int _m,int _k,int _s,int _lab):m(_m),k(_k),s(_s),lab(_lab){}
    bool operator<(const Que&B)const{
        return m<B.m;
    }
}Q[1000010];
struct Blo{
    int a,b,c;
    bool operator<(const Blo&B)const{
        return a<B.a;
    }
}B[1010];
int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int Min(int a,int b){
    if(a==0)
        return b;
    else if(b==0)
        return a;
    return min(a,b);
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n=getint(),i,j,k;
    for(i=1;i<=n;++i){
        B[i].c=getint();
        B[i].a=getint();
        B[i].b=getint();
    }
    sort(B+1,B+n+1);
    int q=getint();
    for(i=1;i<=q;++i){
        Q[i].m=getint();
        Q[i].k=getint();
        Q[i].s=getint();
        Q[i].lab=i;
    }
    sort(Q+1,Q+q+1);
    int now=0,last=1;
    f[now][0]=1;
    for(j=1,i=1;i<=q;++i){
        while(j<=n&&B[j].a<=Q[i].m){
            swap(now,last);
            memcpy(f[now],f[last],sizeof f[now]);
            memcpy(g[now],g[last],sizeof g[now]);
            for(k=B[j].c;k<=100000;++k)
                if(f[last][k-B[j].c]){
                    f[now][k]=1;
                    g[now][k]=max(g[now][k],Min(g[last][k-B[j].c],B[j].b));
                }
            ++j;
        }
        ok[Q[i].lab]=g[now][Q[i].k]>Q[i].m+Q[i].s;
    }
    for(i=1;i<=q;++i)
        puts(ok[i]?"TAK":"NIE");
    return 0;
}