AT_abc224_e [ABC224E] Integers on Grid

比较符合 CCF 造数据水平的题。

思路

首先可以用两个 vector<pair<int,int>> v[N] 分别将每一行、每一列的元素的权值与编号存储下来。

那么可以对所有的 $v_i$ 按照权值从小到大排序。那么发现对于所有的满足 v[i][p].fst < v[i][q].fst 的 $(p,q)$ 都可以建一条从 $p$ 指向 $q$ 的有向边。按照这种方式建图，最坏情况下会有 $\Theta(n^2)$ 级别的边。

考虑一种比较显然的贪心策略，对于一个 $p$ 显然只需要与 $p$ 之后第一个满足 v[i][p].fst < v[i][q].fst 连边。因为如果不这么连，将 $p$ 连向一个拥有更大权值的点 $k$，显然你可以通过 $p \to q \to k$ 的方式获得更大的答案。

于是你写完过后交上去，发现会WA 1。这其中的原因就是对于权值相同的几个点，你直接取第一个是不优的。（不难发现，这种写法是很容易被卡的，但是 AT 只卡了一个点，同时放了一些写法比较优秀的 $\Theta(n^2)$ 算法）

不难发现，我们希望将所有满足条件的相同权值的点都要连边，同时保证边数尽量小。不妨考虑将这些点直接看作一个点，实现的话可以直接将这些权值相同的点连向一个超级原点，在后面连边的时候用超级原点与现在的点连边即可。

现在问题就很简单了，直接建反图，跑一边拓扑就完了。

Code

#include <bits/stdc++.h>  
#define fst first  
#define snd second  
#define re register  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const int N = 1e6 + 10,inf = 1e9 + 10;  
int n,H[2];  
int d[N],rt[N],dp[N];  
int id,idx,h[N],ne[N],e[N],w[N];  
vector<pii> v[2][N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 1) + (r << 3) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline void add(int a,int b,int c){  
    d[b]++;  
    ne[idx] = h[a];  
    e[idx] = b;  
    w[idx] = c;  
    h[a] = idx++;  
}  
  
inline void f(int ty){  
    for (re int i = 1;i <= H[ty];i++){  
        sort(v[ty][i].begin(),v[ty][i].end());  
        int len = v[ty][i].size();  
        for (re int j = 0;j < len;j++){  
            int p = v[ty][i][j].snd;  
            if (!j) rt[p] = ++id;  
            else{  
                if (v[ty][i][j].fst == v[ty][i][j - 1].fst) rt[p] = rt[v[ty][i][j - 1].snd];  
                else rt[p] = ++id;  
            }  
            add(p,rt[p],0);  
        }  
        for (auto x:v[ty][i]){  
            auto it = upper_bound(v[ty][i].begin(),v[ty][i].end(),make_pair(x.fst,inf));  
            if (it == v[ty][i].end()) break;  
            int a = rt[(*it).snd],b = x.snd;  
            add(a,b,1);  
        }  
    }  
}  
  
inline void top_sort(){  
    queue<int> q;  
    for (re int i = 1;i <= id;i++){  
        if (!d[i]){  
            dp[i] = 0;  
            q.push(i);  
        }  
    }  
    while (!q.empty()){  
        int t = q.front();  
        q.pop();  
        for (re int i = h[t];~i;i = ne[i]){  
            int j = e[i];  
            dp[j] = max(dp[j],dp[t] + w[i]);  
            d[j]--;  
            if (!d[j]) q.push(j);  
        }  
    }  
}  
  
int main(){  
    memset(h,-1,sizeof(h));  
    memset(dp,-1,sizeof(dp));  
    for (re int i = 0;i <= 1;i++) H[i] = read();  
    n = id = read();  
    for (re int i = 1;i <= n;i++){  
        int x,y,val;  
        x = read();  
        y = read();  
        val = read();  
        v[0][x].push_back({val,i});  
        v[1][y].push_back({val,i});  
    }  
    f(0);  
    f(1);  
    top_sort();  
    for (re int i = 1;i <= n;i++) printf("%d\n",dp[i]);  
    return 0;  
}