NC20098. [HNOI2012]永无乡
描述
输入描述
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。对于 20%的数据 n ≤ 1000,q ≤ 1000对于 100%的数据 n ≤ 100000,m ≤ n，q ≤ 300000
输出描述
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
示例1
输入:
5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3
输出:
-1 2 5 1 2
C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 375ms, 内存消耗: 17032K, 提交时间: 2023-04-18 20:31:27
#include <bits/stdc++.h>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define lowbit(x) ((x) & -(x))
#define all(x) x.begin(), x.end()
#define set_all(x, y) memset(x, y, sizeof (x))
#define endl '\n'
// #define int long long
#define ff first
#define ss second
#define pb push_back
#define typet typename T
#define typeu typename U
#define types typename... Ts
#define tempt template <typet>
#define tempu template <typeu>
#define temps template <types>
#define tandu template <typet, typeu>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) do {} while (false)
#endif
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, bool> PIB;
typedef pair<double, double> PDD;
typedef long double ld;
// typedef __int128_t i128;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
return splitmix64(x + FIXED_RANDOM);
}
};
const int N = 100010, M = 2 * N, K = 31;
const double pi = acos(-1), eps =1e-7;
const ull P = 13331;
struct Node{
int val, x, sz, id;
int l, r;
};
struct fhpTreap {
vector<Node> tr = {{0, 0, 0, 0, 0, 0}};
int idx = 0, rt = 0, dl = 0, dr = 0;
int size = 0;
int get_node(int x, int id)
{
Node temp;
temp.id = id;
temp.x = x;
temp.val = rand();
temp.sz = 1;
temp.l = temp.r = 0;
tr.push_back(temp);
return tr.size() - 1;
}
void push_up(int u)
{
tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
return;
}
void split(int u, int x, int& l, int &r)
{
if (u == 0)
{
l = 0, r = 0;
return;
}
if (tr[u].x <= x)
{
l = u;
split(tr[u].r, x, tr[u].r, r);
}
else
{
r = u;
split(tr[u].l, x, l, tr[u].l);
}
push_up(u);
}
int merge(int l, int r)
{
if (!l || !r) return l | r;
if (tr[l].val <= tr[r].val)
{
tr[l].r = merge(tr[l].r, r);
push_up(l);
return l;
}
else
{
tr[r].l = merge(l, tr[r].l);
push_up(r);
return r;
}
}
void insert(int x, int id)
{
split(rt, x, dl, dr);
int u = get_node(x, id);
rt = merge(merge(dl, u), dr);
size = tr[rt].sz;
}
void delet(int x)
{
split(rt, x - 1, dl, dr);
int temp;
split(dr, x, temp, dr);
temp = merge(tr[temp].l, tr[temp].r);
rt = merge(dl, merge(temp, dr));
size = tr[rt].sz;
}
int get_rank(int x)
{
split(rt, x - 1, dl, dr);
int ans = tr[dl].sz;
rt = merge(dl, dr);
return ans + 1;
}
int get_num(int u, int rk)
{
int lt = tr[u].l, rt = tr[u].r;
int lsz = tr[lt].sz, rsz = tr[rt].sz;
if (rk == lsz + 1) return tr[u].id;
else if (rk <= lsz) return get_num(lt, rk);
else return get_num(rt, rk - (lsz + 1));
}
}Treap[N];
void solut(int I)
{
int n, m;
cin >> n >> m;
vector<int> temp(n + 1);
vector<int> dsu(n + 1);
iota(all(dsu), 0);
function<int(int)> find = [&](int x) {
if (x != dsu[x]) dsu[x] = find(dsu[x]);
return dsu[x];
};
auto merge = [&](int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb)
{
int sza = Treap[fa].size;
int szb = Treap[fb].size;
if (sza > szb) swap(sza, szb);
for (int i = 1; i < Treap[fa].tr.size(); i ++)
Treap[fb].insert(Treap[fa].tr[i].x, Treap[fa].tr[i].id);
dsu[fa] = fb;
}
};
for (int i = 1; i <= n; i ++)
{
cin >> temp[i];
Treap[i].insert(temp[i], i);
}
while (m --)
{
int a, b;
cin >> a >> b;
merge(a, b);
}
int q;
cin >> q;
while (q --)
{
char op;
int a, b;
cin >> op >> a >> b;
if (op == 'B')
{
merge(a,b);
}
else
{
a = find(a);
if (Treap[a].size < b) cout << -1 << endl;
else
{
cout << Treap[a].get_num(Treap[a].rt, b) << endl;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
T = 1;
// cin >> T;
for (int _ = 1; _ <= T; _ ++)
solut(_);
}
C++14(g++5.4) 解法, 执行用时: 508ms, 内存消耗: 24440K, 提交时间: 2020-05-21 17:16:26
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt","r",stdin);
void read(int &val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int INF = 0x3f3f3f3f;
typedef long long LL;
#define mp(x,y) make_pair(x,y)
#define pii pair<int,int>
const int maxn=2e5+100;
const int mod=1e9+7;
//并查集部分
int fa[maxn],rt[maxn];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
//线段树部分
int num[maxn<<5],ls[maxn<<5],rs[maxn<<5],tot;
void up(int o){
num[o]=num[ls[o]]+num[rs[o]];
}
int merge(int a,int b,int l,int r){
if(!a||!b) return a+b;
if(l==r){
num[a]+=num[b];
return a;
}
int mid=l+r>>1;
ls[a]=merge(ls[a],ls[b],l,mid);
rs[a]=merge(rs[a],rs[b],mid+1,r);
up(a);
return a;
}
void upd(int &o,int l,int r,int pos,int v){
if(!o) o=++tot;
if(l==r){
num[o]+=v;return;
}
int mid=l+r>>1;
if(pos<=mid) upd(ls[o],l,mid,pos,v);
else upd(rs[o],mid+1,r,pos,v);
up(o);
}
int qu(int o,int l,int r,int k){
if(!o) return 0;
if(l==r) return l;
int mid=l+r>>1;
if(num[ls[o]]>=k) return qu(ls[o],l,mid,k);
else return qu(rs[o],mid+1,r,k-num[ls[o]]);
}
int x[maxn],to[maxn];
int main(){
// op;
int n,m;
read(n);read(m);
fo(i,1,n) fa[i]=i;
fo(i,1,n) {
read(x[i]),upd(rt[i],1,n,x[i],1),to[x[i]]=i;
}
fo(i,1,m){
int u,v;
read(u);read(v);
int fx=find(u),fy=find(v);
if(fx!=fy){
fa[fy]=fx;
merge(rt[fx],rt[fy],1,n);
}
}
int q;read(q);
while(q--){
char s[10];int l,r;
scanf("%s %d %d",s,&l,&r);
if(s[0]=='Q'){
int fx=find(l);
if(num[rt[fx]]<r) puts("-1");
else printf("%d\n",to[qu(rt[fx],1,n,r)]);
}
else{
int fx=find(l),fy=find(r);
if(fx!=fy){
fa[fy]=fx;
merge(rt[fx],rt[fy],1,n);
}
}
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 412ms, 内存消耗: 59092K, 提交时间: 2022-10-17 22:57:25
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7,M=N*32;
int n,m,q,tot,rt[N],fa[N];
int ls[M],rs[M],id[M],sum[M];
char op;
inline int find(int x){ //并查集查找祖先
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
inline void update(int x){ //更新树的大小
sum[x]=sum[ls[x]]+sum[rs[x]];
}
inline int add(int p,int l,int r,int pos,int idx){ //权值线段树加点
if(!p) p=++tot;
if(l==r){
id[p]=idx;
sum[p]++;
return p;
}
int mid=((l+r)>>1);
if(pos<=mid) ls[p]=add(ls[p],l,mid,pos,idx);
else rs[p]=add(rs[p],mid+1,r,pos,idx);
update(p);
return p;
}
inline int merge(int p,int o,int l,int r){ //相对于两棵权值线段树合并
if(!p||!o) return p+o;
if(l==r) return p;
int mid=((l+r)>>1);
ls[p]=merge(ls[p],ls[o],l,mid);
rs[p]=merge(rs[p],rs[o],mid+1,r);
update(p);
return p;
}
inline int query(int p,int k,int l,int r){ //查询第k大
if(sum[p]<k||!p) return 0;
if(l==r) return id[p];
int mid=((l+r)>>1);
if(k<=sum[ls[p]]) return query(ls[p],k,l,mid);
else return query(rs[p],k-sum[ls[p]],mid+1,r);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1,x;i<=n;++i){ //初始化并查集维护树根
fa[i]=i;
cin>>x;
rt[i]=add(rt[i],1,n,x,i);
}
for(int i=1,x,y;i<=m;++i){ //并查集合并
cin>>x>>y;
x=find(x);y=find(y);
fa[y]=x;
rt[x]=merge(rt[x],rt[y],1,n); //更新树根
}
cin>>q;
for(int i=1,x,y;i<=q;++i){
cin>>op>>x>>y;
if(op=='B'){ //连接两个点
x=find(x);y=find(y);
if(x==y) continue;
fa[y]=x;
rt[x]=merge(rt[x],rt[y],1,n);
}else{ //问与x联通的点中第y大的点
x=find(x);
int ans=query(rt[x],y,1,n);
if(!ans) cout<<"-1\n";
else cout<<ans<<"\n";
}
}
return 0;
}