AtCoder Beginner Contest 355

C - Bingo 2

题意

有一个 $n\times n$ 的网格，初始全白，有 $t$ 次操作，每次操作涂黑一个指定的格子。
问执行第几个操作后，有一行或一列或对角线的格子全部被涂黑。

思路

如果暴力判断，那么总时间复杂度是 $O(n^{2}t)$ 的，而 $n\le 2000,t\le 200000$ ，会超时。

我们可以记录每行、每列、主次对角线中被涂黑的格子数量 $r_i,c_i,d_0,d_1$，每次操作后检查该格子对应的行列对角线的黑格子数是否 $=n$ 即可。

代码

#include <iostream>
#include <vector>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, t;
    cin >> n >> t;

    vector<int> r(n, 0), c(n, 0), d(2, 0);
    for(int i = 0, num; i < t; i++){
        cin >> num; 
        num--;

        int x = num / n, y = num % n;

        r[x]++; c[y]++;
        if(x == y) d[0]++;
        if(x + y == n - 1) d[1]++;

        if(r[x] == n || c[y] == n || d[0] == n || d[1] == n){
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

D - Intersecting Intervals

题意

给定 $n$ 个区间 $[l_i,r_i]$，问两两相交的区间对数，交点重叠也算入。

思路

暴力枚举的时间复杂度是 $O(n^2)$，不能满足要求。
发现直接求相交的对数不好想，但正难则反，我们可以求出不相交的区间对数 $cnt$，易知 $\frac{n(n-1)}{2}-cnt$ 就是答案。

发现不相交的两个区间 $i,j$一定满足 $r_j\le l_i$（这里假定区间 $j$ 在区间 $i$ 左边）。

我们可以用双指针，将 $l_i$ 和 $r_i$ 分别升序排序。
记对于每个$i$，满足 $r_j\le l_i$ 的 $j$ 的个数为 $c_i$。
由于 $r$ 升序，满足 $r_j\le l_i$ 的 $j$ 递增，因此可以得到以下算法：

按照 $i=1,2,\cdots ,n$ 的顺序执行以下操作：

1. 令 $c=1$。
2. 如果 $r_c\le l_i$，那么 $c=c+1$，直到不满足前述条件。
3. 令 $c_i=c-1$。

但稍加分析可以发现，上述算法的时间复杂度仍为 $O(n^2)$，我们需要进一步优化。

发现 $c_i$ 一定不降，所以计算 $c_{i+1}$ 时，可以直接从 $c_i$ 开始，这样时间复杂度就可以优化至 $O(n) $。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    vector<int> l(n), r(n);
    for(int i = 0; i < n; i++) cin >> l[i] >> r[i];

    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    int ans = n * (n - 1) / 2, j = 0;
    for(int i = 0; i < n; i++){
        while(r[j] < l[i]) j++;
        ans -= j;
    }
    cout << ans << endl;
    return 0;
}

E - Guess the Sum

题意

交互题。
有一个长度为 $2^n$ 的序列 $a$，但是你不知道它。你需要用最少的询问次数求出 $({\sum }_{i=l}^r{a}_i)\mathrm{mod}100$ 的值。（下标从 $0$ 开始）。
每次询问给出 $i,j$，回答 $l=2^{i}j,r=2_i(j+1)-1,({\sum }_{i=l}^r{a}_i)\mathrm{mod}100$ 的值。

思路

审完题可以想到 ABC349D ，将区间变成左闭右开区间。
但是那题不能将两个区间相减，而本题可以，比如询问 $[1,7]$，如果按照那题的思路，需要询问区间 $[1,1]+[2,3]+[4,7]$ 即询问 $(0,1),(1,1),(2,1)$，共三个询问。
但是可以用 $[0,7]-[0,0]$，即询问 $(3,0),(0,0)$。

于是相当于在一张 $2^n$ 个点的无向图上，对于所有 $i,j$，连接 $2^{i}j$ 和 $2^i(j+1)$，求 $l$ 到 $r+1$ 的最短路。

由于边权为 $1$，我们直接 bfs，记录下路径。
接下来遍历路径，考虑如何提问，实际上这很简单，每次查询时往左跳就减去查询的和，往右跳就加上，如果从后往前的话就反过来。

为了省空间，可以不建图，直接bfs时判断（其实没必要）。

代码

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, l, r;
    cin >> n >> l >> r;
    r++;
    
    int v = 1 << n;
    vector<int> pre(v + 1, -1);
    queue<int> q;
    q.push(l);
    pre[l] = l;

    while(q.size()) {
        int x = q.front();
        q.pop();
        
        for (int i = 1; i <= v; i *= 2) {
            for (auto y : {x - i, x + i}) {
                if (y < 0 || y > v) continue;
                if (pre[y] == -1) {
                    pre[y] = x;
                    q.push(y);
                }
            }
            if (x & i) break;
        }
    }

    int ans = 0;
    for (int i = r; i != l; i = pre[i]) {
        int a = pre[i], b = i, t = 1;
        if (a > b) {
            swap(a, b);
            t = -1;
        }
        int p = __lg(b - a), q = a / (b - a), res;
        cout << "? " << p << " " << q << endl;
        cin >> res;
        ans = (ans + t * res + 100) % 100;
    }
    cout << "! " << ans << endl;
    return 0;
}

F - MST Query

题意

给你一棵 $n$ 个点的带边权的树，有 $q$ 次询问，每次询问添加一条边，输出当前的最小生成树的边权和。
所有边权不大于 $10$。

思路

首先否决掉跑 $q$ 次 kruskal 的做法。

可以LCT做，但是这道题中边的权值非常小，那么我们从可以这里找突破口.

考虑维护每个边权选择的数量，算出生成树边权，删边的话，可以维护边权为 $i$ 的边所形成的连通性， 这样加一条边权为 $i$ 的边时，看有没有边权 $>i$ 的使得那两点连通，从而决定删除哪条边。但会发现不好维护，因为会产生依赖关系。

为了不依赖其他情况，我们可以用并查集维护边权 $ \le i$ 的边所形成的连通性情况，这样我们就建立 $10$ 个互不依赖的并查集。

接下来看如何求出最小生成树的边权，关键是求出每个边权的在MST中的个数。由于每加一条边，连通块的个数就会少一。
所以边权为 $i$ 使用的个数就是 $d_i$ 的连通块个数减去 $d_{i-1}$ 的连通块个数。

代码

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

struct DSU {
    vector<int> f;
    
    DSU() {}
    DSU(int n){
        init(n);
    }
    
    void init(int n){
        f.resize(n);
        iota(f.begin(), f.end(), 0);
    }
    
    int find(int x){
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }
    
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return false;
        f[y] = x;
        return true;
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector<DSU> dsu(10, DSU(n));
    vector<int> cnt(10, n);

    for(int i = 0, a, b, c; i < n - 1; i++){
        cin >> a >> b >> c;
        a--, b--;
        for(int j = c; j <= 10; j++) cnt[j - 1] -= dsu[j - 1].merge(a, b);
    }

    for(int i = 0, u, v, w; i < q; i++){
        cin >> u >> v >> w;
        u--, v--;
        for(int j = w; j <= 10; j++) cnt[j - 1] -= dsu[j - 1].merge(u, v);

        int ans = 0, last = n;
        for(int j = 1; j <= 10; j++){
            ans += j * (last - cnt[j - 1]);
            last = cnt[j - 1];
        }
        cout << ans << endl;
    }
    return 0;
}