题解 CF1557D 【Ezzat and Grid】

· · 题解

这次比赛的题解

dp。设 f_{i,j} 表示前 i 行最多能保留几行，且我们考虑了第 i 行第 j 列这个格子是 1。

转移的时候考虑所有值为 1 的 (k,j)，那么：

f_{i,j}=\max_{1\le k\le i-1,grid_{k,j}=1}\{f_{k,j}+1\}

这个可以用线段树优化。具体的，对于每个 j，我们要维护 f_{k,j} 的最大值。

具体细节见代码（非 C++11 党勿入）：

using ll=long long;
using pii=std::pair<int,int>;

// 区间覆盖，区间 max，还要维护方案
struct SegTree{
    struct Node{
        pii mx,ctag;
    };

    std::vector<Node> t;

    SegTree(int n=0){
        t.resize(n*4+5,{{0,-1},{0,-1}});
    }

    std::function<int(int)> ls=[](int x)->int{return x<<1;};
    std::function<int(int)> rs=[](int x)->int{return x<<1|1;};

    std::function<Node(const Node &,const Node &)> pushUp=[](const Node &L,const Node &R)->Node{
        return {std::max(L.mx,R.mx),{0,-1}};
    };

    std::function<void(Node &,const pii &)> pushC=[](Node &now,const pii &ctag)->void{
        now.mx=now.ctag=ctag;
    };

    std::function<void(int)> pushDown=[this](int i)->void{
        if(t[i].ctag!=pii({0,-1})){
            pushC(t[ls(i)],t[i].ctag);
            pushC(t[rs(i)],t[i].ctag);
            t[i].ctag={0,-1};
        }
    };

    std::function<void(int,int,int,int,int,const pii &)> modify=[this](int i,int l,int r,int ql,int qr,const pii &x)->void{
        if(ql<=l&&r<=qr)return pushC(t[i],x),void();
        int mid=(l+r)>>1;
        pushDown(i);
        if(ql<=mid)modify(ls(i),l,mid,ql,qr,x);
        if(qr>mid) modify(rs(i),mid+1,r,ql,qr,x);
        t[i]=pushUp(t[ls(i)],t[rs(i)]);
    };

    std::function<Node(int,int,int,int,int)> query=[this](int i,int l,int r,int ql,int qr)->Node{
        if(ql<=l&&r<=qr)return t[i];
        int mid=(l+r)>>1;
        pushDown(i);
        if(ql>mid) return query(rs(i),mid+1,r,ql,qr);
        if(qr<=mid)return query(ls(i),l,mid,ql,qr);
        return pushUp(query(ls(i),l,mid,ql,qr),query(rs(i),mid+1,r,ql,qr));
    };
};

void mian(){
    int n,m;
    scanf("%d%d",&n,&m);
    std::vector<std::vector<pii>> a(n);
    for(int i=0;i<m;i++){
        int p,l,r;
        scanf("%d%d%d",&p,&l,&r);
        p--;
        a[p].push_back({l,r});
    }
    // 把所有线段离散化
    std::function<void(void)> init=[&]()->void{
        std::vector<int> tmp;
        for(auto i:a)
            for(auto j:i)
                tmp.push_back(j.first),tmp.push_back(j.second);
        std::sort(tmp.begin(),tmp.end());
        auto it=std::unique(tmp.begin(),tmp.end());
        tmp.erase(it,tmp.end());
        for(auto &i:a)
            for(auto &j:i){
                j.first=std::lower_bound(tmp.begin(),tmp.end(),j.first)-tmp.begin()+1;
                j.second=std::lower_bound(tmp.begin(),tmp.end(),j.second)-tmp.begin()+1;
            }
    };
    init();
    std::vector<pii> f(n);
    for(auto &x:f)x.second=-1;
    SegTree t(m*2);
    for(int i=0;i<n;i++){
        for(auto j:a[i]){ // 枚举第 i 行所有的值为 1 的格子
            auto x=t.query(1,1,m*2,j.first,j.second); // max_{k=1..i-1,grid[k][j]}=1} f[j]
            x.mx.first++;
            f[i]=std::max(f[i],x.mx);
        }
        for(auto j:a[i])
            t.modify(1,1,m*2,j.first,j.second,{f[i].first,i}); // 更新 max f[k][j]
    }
    // 输出方案
    int p=0;
    for(int i=0;i<n;i++)
        if(f[i]>f[p])p=i;
    std::set<int> ans;
    for(int i=0;i<n;i++)ans.insert(i);
    for(;p!=-1;p=f[p].second)ans.erase(p);
    printf("%d\n",int(ans.size()));
    for(auto i:ans)printf("%d ",i+1);
    puts("");
}