Solve this problem using C++. Think hard and think...

Question

Solve this problem using C++. Think hard and think carefully.

When you implemented a code, you must run it with Python analysis tool. Input is samples, If the output is incorrect, fix your code, until it's correct.

Then make small datas, to check code's correctness. The answer should be generated using brute force code that will not Wrong Answer.

After passing stress-testing and samples, give me the final complete code that can pass all data under the constraints..

【题目描述】
H 工厂内有 𝑛 个车间，所有的车间排成一行，车间从左到右编号为 1 ∼ 𝑛。每个车间内恰好有一名设计师和一名工程师。设计师和工程师分别从 1 ∼ 𝑛 编号。
设计师与工程师之间存在一些默契关系。具体来说，存在一个 1 ∼ 𝑛 的排列 𝑝。如果编号为 𝑖 的设计师和编号为 𝑝𝑖 的工程师在同一个车间内工作，那么生产效率会提高。
我们称工厂的效率值为编号为 𝑖 的设计师和编号为 𝑝𝑖 的工程师在同一个车间内的 (𝑖, 𝑝𝑖) 对数。
初始时，第 𝑖 个车间的员工由编号为 𝑎𝑖 的设计师和编号为 𝑏𝑖 的工程师构成。
接下来的第 𝑡 天里，你作为 H 工厂的总管可以进行如下操作任意次：
• 选择一个整数 1 ≤ 𝑖 < 𝑛，满足 𝑎𝑖 , 𝑎𝑖+1 ≤ 𝑡，交换 𝑎𝑖 和 𝑎𝑖+1 。
• 选择一个整数 1 ≤ 𝑖 < 𝑛，满足 𝑏𝑖, 𝑏𝑖+1 ≤ 𝑡，交换 𝑏𝑖 和 𝑏𝑖+1 。
你希望最大化工厂的效率值。请你计算出每一天后，工厂的最大可能效率值。
【输入格式】
第一行输入一个整数 𝑛，表示工厂中的车间数量。
第二行 𝑛 个整数表示排列 𝑎𝑖 ，即初始时每个车间内的设计师编号。
第三行 𝑛 个整数表示排列 𝑏𝑖 ，即初始时每个车间内的工程师编号。
第四行 𝑛 个整数表示排列 𝑝𝑖 ，即与第 𝑖 号设计师产生默契的工程师编号。
【输出格式】
输出一行 𝑛 个整数，第 𝑖 个整数表示第 𝑖 天后工厂的最大可能效率值。
【样例 1 输入】
5
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
【样例 1 输出】
1 1 1 3 5
【样例 2 输入】
4
1 3 2 4
2 3 4 1
2 4 3 1
【样例 2 输出】
4 4 4 4
【样例 3 输入】
6
1 5 3 2 4 6
2 3 4 6 1 5
1 3 4 2 5 6
【样例 3 输出】
1 1 1 1 4 6
【数据范围】
对于所有测试数据，保证 1 ≤ 𝑛 ≤ 10^5 ，𝑎, 𝑏, 𝑝 分别为 1 ∼ 𝑛 的排列。

Answer 1

Here is a C++ implementation running in O(n log n) time using two union‐finds with small-to-large merging of the bipartite maps as described. It has been stress-tested against the sample tests and random small cases via the Python brute above.

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU1 {
    vector<int> p;
    vector<unordered_map<int, pair<int,int>>> m; // key = DSU2 root -> (cap,pairs)
    vector<unordered_set<int>> rev;               // reverse index: DSU2 root -> set of DSU1 roots
    ll &matches;
    DSU1(int n, ll &matches_) : p(n+1), m(n+1), rev(n+1), matches(matches_) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    // merge DSU1 blocks containing u and v (adjacent positions)
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if(u==v) return;
        // small-to-large by map size
        if(m[u].size() < m[v].size()) swap(u,v);
        // u = dest, v = src
        for(auto &kv : m[v]){
            int key = kv.first;
            int cap2 = kv.second.first;
            int pairs2 = kv.second.second;
            auto it = m[u].find(key);
            int cap1 = 0, pairs1 = 0;
            if(it != m[u].end()){
                cap1 = it->second.first;
                pairs1 = it->second.second;
            }
            ll oldc = min(cap1, pairs1) + min(cap2, pairs2);
            int nc = cap1 + cap2;
            int np = pairs1 + pairs2;
            ll newc = min(nc, np);
            matches += (newc - oldc);
            m[u][key] = {nc, np};
            // update reverse index
            rev[key].erase(v);
            rev[key].insert(u);
        }
        m[v].clear();
        p[v] = u;
    }
};

struct DSU2 {
    vector<int> p;
    vector<unordered_set<int>> *rev; // pointer to DSU1.rev
    vector<unordered_map<int, pair<int,int>>> *m; // pointer to DSU1.m
    ll &matches;
    DSU2(int n, vector<unordered_set<int>> *rev_, vector<unordered_map<int,pair<int,int>>> *m_, ll &matches_)
        : p(n+1), rev(rev_), m(m_), matches(matches_) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    // merge DSU2 blocks containing u and v (adjacent positions)
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if(u==v) return;
        // small-to-large by rev size
        if((*rev)[u].size() < (*rev)[v].size()) swap(u,v);
        // u = dest, v = src
        for(int r : (*rev)[v]){
            auto &map_r = (*m)[r];
            // fetch old entries
            auto itU = map_r.find(u);
            int cap1 = (itU!=map_r.end() ? itU->second.first : 0);
            int pairs1 = (itU!=map_r.end() ? itU->second.second : 0);
            auto itV = map_r.find(v);
            int cap2 = (itV!=map_r.end() ? itV->second.first : 0);
            int pairs2 = (itV!=map_r.end() ? itV->second.second : 0);
            ll oldc = min(cap1, pairs1) + min(cap2, pairs2);
            int nc = cap1 + cap2;
            int np = pairs1 + pairs2;
            ll newc = min(nc, np);
            matches += (newc - oldc);
            // update
            map_r[u] = {nc,np};
            map_r.erase(v);
            (*rev)[u].insert(r);
        }
        (*rev)[v].clear();
        p[v] = u;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1), pmap(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    for(int i=1;i<=n;i++) cin >> pmap[i];

    vector<int> posA(n+1), posB(n+1);
    for(int i=1;i<=n;i++) posA[a[i]] = i;
    for(int i=1;i<=n;i++) posB[b[i]] = i;

    ll matches = 0;
    DSU1 dsu1(n, matches);
    // initialize DSU1 maps and reverse index
    for(int i=1;i<=n;i++){
        // capacity = 1 for (i,i)
        dsu1.m[i][i] = {1,0};
        dsu1.rev[i].insert(i);
    }
    // pairs mapping
    for(int x=1;x<=n;x++){
        int pa = posA[x];
        int pb = posB[pmap[x]];
        auto &mp = dsu1.m[pa];
        if(!mp.count(pb)){
            mp[pb] = {0,0};
            dsu1.rev[pb].insert(pa);
        }
        mp[pb].second++;
    }
    // compute initial matches
    for(int i=1;i<=n;i++){
        auto &it = dsu1.m[i];
        auto jt = it.find(i);
        if(jt!=it.end()){
            matches += min(jt->second.first, jt->second.second);
        }
    }

    DSU2 dsu2(n, &dsu1.rev, &dsu1.m, matches);

    // build merge events
    vector<pair<int,int>> E1, E2;
    E1.reserve(n-1);
    E2.reserve(n-1);
    for(int i=1;i<n;i++){
        E1.emplace_back(max(a[i], a[i+1]), i);
        E2.emplace_back(max(b[i], b[i+1]), i);
    }
    sort(E1.begin(), E1.end());
    sort(E2.begin(), E2.end());

    vector<ll> ans(n+1);
    int i1=0, i2=0;
    for(int t=1;t<=n;t++){
        while(i1 < (int)E1.size() && E1[i1].first <= t){
            dsu1.unite(E1[i1].second, E1[i1].second+1);
            i1++;
        }
        while(i2 < (int)E2.size() && E2[i2].first <= t){
            dsu2.unite(E2[i2].second, E2[i2].second+1);
            i2++;
        }
        ans[t] = matches;
    }

    for(int t=1;t<=n;t++){
        cout << ans[t] << (t<n?' ':'\n');
    }
    return 0;
}

Complexity:

We process O(n) DSU merges on each of the two axes.
Each merge uses the small-to-large trick to combine the bipartite maps in overall O(n log n) time.
Total memory is O(n), maps store at most ~2n entries, and reverse-indices another ~2n.

This passes all sample tests and has been cross-checked against a brute-force implementation on random small cases.

Solve this problem using C++. Think hard and think...

问题

Python

Python

思考

Evaluating DSU1 and DSU2 merge complexity

Analyzing DSU1 and DSU2 complexities

Managing DSU1 and DSU2 merges

Choosing DSU2 roots based on size

Implementing DSU functions

Merging logic for DSU1 and DSU2

Handling DSU1 and DSU2 merging

回答

分享这个问答