CF 1557D

D. Ezzat and Grid

題目

給你一個高$N(\leq 3\cdot10^5)$長$10^9$的 01 矩陣。01矩陣會由$m (\leq 3\cdot10^5)$個區間$(h_i,l_i,r_i)$來表示$1$的位置。例如 $n=3,=6$時，且區間為$(1,1,1), (1,7,8), (2,7,7), (2,15,15), (3,1,1), (3,15,15)$這樣的話該矩陣就會長的像下面這樣：

取自 CF1557D 原題面

請問至少要移除多少行才可以讓這個矩陣變成完美的。其中一個矩陣是完美的若且唯若任意的連續兩行存在相同位置使得兩個位置都是$1$。

題解

容易想到一個 DP 式$dp(i)$代表前$i$橫列必選第$i$列最多可以選幾個。而轉移式也可以很輕鬆地列出來：

$dp(i)=\max\limits_{j<i\ and\ a[i] \& a[j] > 0}\{dp(j)+1\}$

有經驗的話就可以很輕鬆地看出套個線段樹優化就結束了~

但是！因為我壓根就忘記了線段樹優化要怎麼用，所以我根本沒發現他可以套線段樹優化(x。

因為沒有發現他是線段樹優化，所以我就想出了另外一個有點神奇的作法：掃描線+建圖

考慮使用掃描線由左至右的掃過去，我們就可以知道每個時間點有哪幾橫列是有$1$的，假設在第$i$直行有$1$的集合叫做$S_i$，這也就代表說在這個$S_i$中的任意兩列放在連續的地方都是完美的。這樣的話我們就可以合理想到建有向圖的方式，任意兩列存在一條邊若且唯若兩列是可以連續放的，並且方向由編號小指向編號大。如此一來當我們把所有的時間點都處理完就可以得到一張所有可能性的有向圖(DAG)了。於是我們就可以直接在上面做最長路結束這一題！

很可惜的，用上面這個建圖方式你可能會既 MLE 又 TLE。為什麼呢？因為如果對任意兩列都建一條邊的話那麼邊數的最糟的情形就會有$O(N^2)$的邊數。

於是我們可以考慮刪掉一些沒有用的邊。觀察可以發現在同一個集合內$S_i$中，我們可以只建排序過後連續的兩個編號的邊就好了，為什麼呢？因為我們只需要找最長路，所以找的過程一定不會想要走捷徑。舉例來說$S_i=\{1,3,6\}$，我們就只需要建$1\rightarrow3,3\rightarrow6$，而不需要建$1\rightarrow6$，因為$1\rightarrow6$這條邊絕對不會出現在任意一條最長路裡面。

那麼我們就可以在維護$S_i$的同時順便建邊。具體來說，每次插入一條橫列時，就建兩條邊，從他建一條往$S_i$裡跟他相鄰且編號比他大的邊，另一條從$S_i$裡跟他相鄰且編號比他小的列建一條到他的邊。這樣子建邊次數就會是插入區間的次數*2，也就是$O(2m)$，考慮用set維護的話就是$O(mlogm)$。

於是總複雜度就是$O(nlogn+mlogm)$，上面可能有點難懂，可以看下面程式碼。

#include "bits/stdc++.h"
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define FFOR(i, a, b) for(int i = a; i <= b; i ++)
#define FOR(i, n) FFOR(i, 1, n)
#define loli ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;
const int maxn = 3e5 + 50;

int n, m, q;
int dep[maxn], ans, pre[maxn], cnt[maxn];
vector<int> vc[maxn], vans;

bitset<maxn> vis;
map<int, vector<int>> mp;
set<int> st;

void dfs(int x) {
    for(int i : vc[x]) {
        if(!dep[i] and i != x) dfs(i);
        if(dep[i] + 1 > dep[x]) {
            pre[x] = i;
            dep[x] = dep[i] + 1;
        }
        ans = max(ans, dep[x]);
    }
}

void solve() {
    st.insert(0), st.insert(n + 1);
    for(auto tmp : mp) {
        int x = tmp.f;
        vector<int> v = tmp.s;
        sort(all(v)); // 先移除掉失效區間再加入區間
        for(int i : v) {
            if(i < 0) {
                cnt[-i] --;
                if(cnt[-i] == 0) st.erase(-i);
                auto it = st.lower_bound(-i);
                vc[*it].pb(*prev(it));
            }
            else {
                if(!cnt[i]) st.insert(i);
                cnt[i] ++;
                auto it = st.lower_bound(i);
                vc[i].pb(*prev(it));
                vc[*next(it)].pb(i);
            }
        }
    }
    FOR(i, n + 1) {
        if(!dep[i]) dfs(i);
    }
    cout << n - ans + 1 << endl;
    int x = n + 1;
    while(x != 0) {
        vans.pb(x);
        x = pre[x];
    }
    sort(all(vans));
    for(int i : vans) vis[i] = 1;
    FOR(i, n) if(!vis[i]) cout << i << ' '; cout << endl;
}

void input() {
    cin >> n >> m;
    FOR(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        mp[b].pb(a);
        mp[c + 1].pb(-a);
    }
}

signed main(){
    loli;
    input();
    solve();
}