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