atcoder abc372 启发式合并， dp

A delete

代码：

#include <bits.stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    for(auto t: s) if(t != '.') cout << t;
}

B 3 ^ A

思路：三进制转换，可以参考二进制，先把当前可以加入的最大的3的幂次加入,这样一定可以凑出答案

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a;
    int tmp = n;
    while(tmp) {
        int l = 0, r = 10;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(pow(3, mid) <= tmp) l = mid;
            else r = mid - 1;
        }
        tmp -= pow(3, l);
        a.push_back(l);
    }
    cout << a.size() << endl;
    for(auto t: a) cout << t << " ";
    return 0;
}

C Count ABC Again

思路：判断当前变化的位置对结果是否会产生影响，在询问前先计算有多少ABC, 每次变换位置x前后扫描一下[x - 2, x + 2]范围内是否有ABC，变换前有让cnt --， 变换后有让cnt ++

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<char> s(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> s[i];
    int cnt = 0;
    for(int i = 3; i <= n; i ++ )
        if(s[i - 2] == 'A' && s[i - 1] == 'B' && s[i] == 'C')
            cnt ++;
    
    while(q -- ) {
        int x;
        char c;
        cin >> x >> c;
        string t;
        t += s[max(1, x - 2)];
        t += s[max(1, x - 1)];
        t += s[x];
        string t1;
        t1 += s[max(1, x - 1)];
        t1 += s[x];
        t1 += s[min(n, x + 1)];
        string t2;
        t2 += s[x];
        t2 += s[min(n, x + 1)];
        t2 += s[min(n, x + 2)];
        if(t1 == "ABC" || t2 == "ABC" || t == "ABC") cnt --;
        s[x] = c;
        t = s[max(1, x - 2)];
        t += s[max(1, x - 1)];
        t += s[x];
        t1 = s[max(1, x - 1)];
        t1 += s[x];
        t1 += s[min(n, x + 1)];
        t2 = s[x];
        t2 += s[min(n, x + 1)];
        t2 += s[min(n, x + 2)];
        if(t1 == "ABC" || t2 == "ABC" || t == "ABC") cnt ++;
        cout << cnt << "\n";
    }
    return 0;
}

D buildings

思路：首先对于每个点i，我们可以很容易用单调栈求出第一个大于该点的位置j,因此点i只有在(j + 1, i)这个区间内对答案有贡献, 这里可以用差分的方式计算贡献

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    a[0] = 0x3f3f3f3f;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    vector<int> pos(n + 1);
    stack<int> stk;
    stk.push(0);
    for(int i = 1; i <= n; i ++ ) {
        while(a[stk.top()] <= a[i]) stk.pop();
        pos[i] = stk.top();
        stk.push(i);
    }

    vector<int> ans(n + 1);
    for(int i = 1; i <= n; i ++ ) {
        ans[pos[i]] += 1;
        ans[i] -= 1;
    }
    
    for(int i = 1; i <= n; i ++ ) {
        ans[i] += ans[i - 1];
        cout << ans[i] << " ";
    }
    return 0;
}

E K-th Largest Connected Components

思路：注意到k很小，因此在查询的时候可以直接遍历。现在考虑如何存数据。可以用并查集合并两个集合，并且在合并的时候一定要将小的集合合并到大的集合中去，因为小集合合并到大集合中，最后的集合一定大于小集合元素数量的两倍，因此合并的时间复杂度不会超过logn

代码：
 

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

struct node {
    int num;
    priority_queue<int> q;
    /*bool operator += (node W) const {
        while(!W.q.empty()) {
            q.push(W.q.top());
            W.q.pop();
        }
    }*/
}_size[N];
int p[N];

int find(int x) {
    if(x != p[x]) {
        p[x] = find(p[x]);
    }   
    return p[x];
}

int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) {
        p[i] = i;
        _size[i].num = 1;
        _size[i].q.push(i);
    }
    while(q -- ) {
        int op;
        cin >> op;
        if(op == 1) {
            int u, v;
            cin >> u >> v;
            int pu = find(u);
            int pv = find(v);
            if(pu != pv) {
                if(_size[pu].num >= _size[pv].num){
                    while(!_size[pv].q.empty()) {
                        _size[pu].q.push(_size[pv].q.top());
                        _size[pv].q.pop();
                    }
                    _size[pu].num += _size[pv].num;
                    p[pv] = pu;
                } else {
                    while(!_size[pu].q.empty()) {
                        _size[pv].q.push(_size[pu].q.top());
                        _size[pu].q.pop();
                    }
                    _size[pv].num += _size[pu].num;
                    p[pu] = pv;
                }
            }
        } else {
            int k, v;
            cin >> v >> k;
            auto q1 = _size[find(v)].q;
            for(int i = 1; i <= k - 1 && !q1.empty(); i ++ ) {
                q1.pop();
            }
            
            if(!q1.empty()) cout << q1.top() << endl;
            else cout << -1 << endl;
        }
    }
    return 0;
}
/*
2
1
-1
4
2
-1
*/

这里留下个疑问

int k, v;
            cin >> v >> k;
            auto q1 = _size[find(v)].q;
            for(int i = 1; i <= k - 1 && !q1.empty(); i ++ ) {
                q1.pop();
            }
            
            if(!q1.empty()) cout << q1.top() << endl;
            else cout << -1 << endl;

为什么在查询时直接查询_size[p[v]]答案会出错，是路径压缩不彻底的原因吗

F