ABC372 (D,E)
D
一道比较简单的二分查找题目。
观察到每个数能成为 \(j\) 的条件是独立的，因此想到统计每个数能成为它前面哪些数的 \(j\)。
对于每个\(ed\), 二分 \(1 \sim ed-1\) 中最后一个大于 \(h[ed]\) 的数的位置 \(st\), 那么 \(h[ed]\) 可作为 \(st \sim ed-1\) 的 \(j\).
二分的检查方法中需要求区间max, 写个st表或者线段树就做完了（参考代码用的线段树）
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int h[N], ans[N], mx[N << 2];
int n;
void pushup(int u){
mx[u] = max(mx[u * 2], mx[u * 2 + 1]);
}
void update(int u, int l, int r, int x, int y){
if(l == r) {
mx[u] += y;
return ;
}
int mid = (l + r) >> 1;
if(x<=mid) update(u * 2, l, mid, x, y);
else update(u * 2 + 1, mid + 1, r, x, y);
pushup(u);
}
int query(int u, int l, int r, int x, int y){
if(x <= l && r <= y){
return mx[u];
}
int mid = (l + r) >> 1, ret = 0;
if(x <= mid) ret = query(u * 2, l, mid, x, y);
if(y > mid) ret = max(ret, query(u * 2 + 1, mid + 1, r, x, y));
pushup(u);
return ret;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
F(i, 1, n) cin >> h[i], update(1, 1, n, i, h[i]);
F(i, 1, n){
int l = 0, r = i, mid;
while(l + 1 < r){
mid = (l + r) >> 1;
if(query(1, 1, n, mid,i-1) > h[i]) l = mid;
else r = mid;
}
ans[l] ++, ans[i]--;
}
F(i, 1, n) ans[i] += ans[i - 1], cout << ans[i] << ' ';
return 0;
}
E
关键在于要读懂 type2 考察的对象是 \(u\) 所在连通块，想到这个，并查集就呼之欲出了。
而查询第 \(k\) 大的话，由于 \(k\) 不超过10, 所以暴力查是可以接受的。
合并用启发式合并保证复杂度控制在 \(O(n logn)\).
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int n, q;
int fa[N];
set<int,greater<int>> s[N];
inline int get(int x){
return (fa[x] != x) ? fa[x] = get(fa[x]) : x;
}
void merge(int u, int v){
int fu = get(u), fv = get(v);
if(fu == fv) return ;
if((int)s[fu].size() > (int)s[fv].size()){
fa[fv] = fu;
for(auto x : s[fv]){
s[fu].emplace(x);
}
s[fv].clear();
}
else{
swap(fu, fv);// fu:bigger
fa[fv] = fu;
for(auto x : s[fv]){
s[fu].emplace(x);
}
s[fv].clear();
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
F(i, 1, n) fa[i] = i, s[i].emplace(i);
F(i, 1, q){
int op, u, v;
cin >> op >> u >> v;
if(op == 1){
merge(u, v);
}
else{
u = get(u);
if((int)s[u].size() < v){
cout << "-1\n";
continue;
}
for(auto x : s[u]){
if(--v==0){
cout << x << '\n';
break;
}
}
}
}
return 0;
}