CF1557D

题目

source

题解

首先离散化，让区间值域数量级在1e5。比较容易可以想到一个O(n^2)的做法，即从下到上遍历每一列，在每一列对其下面有交集的列连一条有向边。长度最长的链就是答案。离散化后，就可以直接在线段树上操作区间。线段树维护区间内最长的链长和对应的行的编号。每次加入一行的若干区间更新最长链长即可。有点求最长上升子序列的感觉。

#include <bits/stdc++.h>
 
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;
 
using namespace std;
/*-----------------------------------------------------------------*/
 
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
 
const int N = 1e6 + 10;
const double eps = 1e-5;
 
int lazyid[N << 2], lazymx[N << 2];
int mx[N << 2], id[N << 2];
 
void pushdown(int rt) {
    if(lazymx[rt]) {
        lazymx[rt << 1] = lazymx[rt];
        lazymx[rt << 1 | 1] = lazymx[rt];
        lazyid[rt << 1] = lazyid[rt];
        lazyid[rt << 1 | 1] = lazyid[rt];
        mx[rt << 1] = lazymx[rt];
        mx[rt << 1 | 1] = lazymx[rt];
        id[rt << 1] = lazyid[rt];
        id[rt << 1 | 1] = lazyid[rt];
        lazymx[rt] = 0;
        lazyid[rt] = 0;
    }
}
 
void upd(int l, int r, int L, int R, int val, int ind, int rt) {
    if(l >= L && r <= R) {
        mx[rt] = val;
        id[rt] = ind;
        lazyid[rt] = ind;
        lazymx[rt] = val;
        return ;
    }
    pushdown(rt);
    int mid = (l + r) / 2;
    if(mid >= L) upd(l, mid, L, R, val, ind, rt << 1);
    if(mid < R) upd(mid + 1, r, L, R, val, ind, rt << 1 | 1);
    if(mx[rt << 1 | 1] > mx[rt << 1]) {
        mx[rt] = mx[rt << 1 | 1];
        id[rt] = id[rt << 1 | 1];
    } else {
        mx[rt] = mx[rt << 1];
        id[rt] = id[rt << 1];
    }
}
 
PII que(int l, int r, int L, int R, int rt) {
    if(l >= L && r <= R) {
        return {mx[rt], id[rt]};
    }
    pushdown(rt);
    int mid = (l + r) / 2;
    PII res(0, 0);
    if(mid >= L) res = max(res, que(l, mid, L, R, rt << 1));
    if(mid < R) res = max(res, que(mid + 1, r, L, R, rt << 1 | 1));
    if(mx[rt << 1 | 1] > mx[rt << 1]) {
        mx[rt] = mx[rt << 1 | 1];
        id[rt] = id[rt << 1 | 1];
    } else {
        mx[rt] = mx[rt << 1];
        id[rt] = id[rt << 1];
    }
    return res;
}
 
int up[N];
int cnt[N];
bool del[N];
 
vector<int> sid;
 
vector<PII> segs[N];
 
int getid(int x) {
    return lower_bound(sid.begin(), sid.end(), x) - sid.begin() + 1;
}
 
int main() {
    IOS;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int p, l, r;
        cin >> p >> l >> r;
        segs[p].push_back({l, r});
        sid.push_back(l);
        sid.push_back(r);
    }
    sort(sid.begin(), sid.end());
    sid.erase(unique(sid.begin(), sid.end()), sid.end());
    int mx = sid.size() + 5;
    for(int i = 1; i <= n; i++) {
        for(auto &s : segs[i]) {
            s.first = getid(s.first);
            s.second = getid(s.second);
        }
    }
 
    for(int i = n; i >= 1; i--) {
        if(segs[i].empty()) continue;
        PII res(0, 0);
        for(auto &s : segs[i]) {
            int l = s.first, r = s.second;
            res = max(res, que(1, mx, l, r, 1));
        }
        up[i] = res.second;
        cnt[i] = res.first + 1;
        for(auto &s : segs[i]) {
            int l = s.first, r = s.second;
            upd(1, mx, l, r, res.first + 1, i, 1);
        }
    }
    int tar = 1;
    for(int i = 2; i <= n; i++) {
        if(cnt[i] > cnt[tar]) tar = i;
    }
    vector<int> ans;
    int cur = tar;
    while(cur) {
        del[cur] = 1;
        cur = up[cur];
    }
    for(int i = 1; i <= n; i++) {
        if(!del[i]) ans.push_back(i);
    }
 
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " 
"[i == ans.size() - 1];
}