知识点:
原题面 darkbzoj
扯
root :
两年来，已经有接近一半的人认识到BZOJ终将爆炸的本质，改正归邪投入了黑暗爆炸OJ的怀抱！我利用大家凝聚的黑暗力量制造出了定时炸弹，大摇大摆就走进了BZOJ的机房安装了上去，lavendir根本不知道跑哪去了！现在机房已经被炸成一团黑了，地上洒满了年代悠久的机箱、主板和CPU的碎片！还有一些红通通的毛爷爷也被炸得焦黑！目前lavendir正在与CCF合作研制时光机，尝试在去年找回毛爷爷并转入大家100年后的帐号！这一切都是大家齐心协力的成果，可喜可贺！
只能用这个凑活凑活了/fad
之前在爆炸 OJ 上交的代码也没了（悲
题意简述
给定 \(m\) 个操作：
1.新建一个节点，权值为 \(x\)。
2.连接两个节点。
3.将一个节点 \(a\) 所属于的联通块内权值小于 \(x\) 的所有节点权值变成 \(x\)。
4.将一个节点 \(a\) 所属于的联通块内权值大于 \(x\) 的所有节点权值变成 \(x\)。
5.询问一个节点 \(a\) 所属于的联通块内的第 \(k\) 小的权值是多少。
6.比较一个节点 \(a\) 所属联通块内所有节点权值之积与另一个节点 \(b\) 所属联通块内所有节点权值之积的大小。
7.询问 \(a\) 所在联通块内节点的数量。
\(1\le m\le 4\times 10^5\)，所有出现的数均 \(\le 10^9\)。
分析题意
裸的线段树合并，对每一个联通块维护一个权值线段树，并查集维护联通性，直接搞。
注意一些细节：
对于操作 6，需要维护元素的乘积，直接乘起来会爆掉。
考虑对 2 取对数，则有：
\[\prod p > \prod q \iff \log_2\prod p > \log_2\prod q
\]
大小关系不变，又有：
\[\log_2{\prod p} = \sum\log_2 p
\]
处理出 \(\log_2\) 后，可将乘法变成加法进行维护。
动态开点线段树区间赋 0 时，可以直接将该区间代表的节点设为 0。
不需要写懒标记，也方便了合并。
此外还可以对值域进行离散化卡常数。交一发发现过了就没写。
代码实现
//知识点：线段树合并
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define ls (lson[now_])
#define rs (rson[now_])
const int kMaxn = 4e5 + 10;
const int kInf = 1e9;
//=============================================================
int fa[kMaxn];
int n, m, node_num, root[kMaxn], lson[kMaxn << 5], rson[kMaxn << 5], size[kMaxn << 5];
double prod[kMaxn << 5];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void GetMax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
void PushUp(int now_) {
size[now_] = size[ls] + size[rs];
prod[now_] = prod[ls] + prod[rs];
}
void Insert(int &now_, int L_, int R_, int pos_, int num_, double val_) {
if (!now_) now_ = ++ node_num;
if(L_ == R_) {
size[now_] += num_;
prod[now_] += val_;
return ;
}
int mid = (L_ + R_) >> 1;
if (pos_ <= mid) Insert(ls, L_, mid, pos_, num_, val_);
else Insert(rs, mid + 1, R_, pos_, num_, val_);
PushUp(now_);
}
int Merge(int x_, int y_, int L_, int R_) {
if (! x_ || ! y_) return x_ + y_;
if (L_ == R_) {
size[x_] += size[y_];
prod[x_] *= prod[y_];
return x_;
}
int mid = (L_ + R_) >> 1;
lson[x_] = Merge(lson[x_], lson[y_], L_, mid);
rson[x_] = Merge(rson[x_], rson[y_], mid + 1, R_);
PushUp(x_);
return x_;
}
int Modify(int &now_, int L_, int R_, int val_, bool type) {
if (! now_) return 0;
if ((type && R_ < val_) || (! type && L_ > val_)) {
int ret = size[now_];
now_ = 0;
return ret;
}
int mid = (L_ + R_) >> 1, ret = 0;
if (type || (! type && val_ <= mid)) ret += Modify(ls, L_, mid, val_, type);
if (! type || (type && val_ > mid)) ret += Modify(rs, mid + 1, R_, val_, type);
return ret;
}
int QueryKth(int &now_, int L_, int R_, int k_) {
if (L_ == R_) return L_;
int mid = (L_ + R_) >> 1, ls_size = size[ls];
if (ls_size >= k_) return QueryKth(ls, L_, mid, k_);
else return QueryKth(rs, mid + 1, R_, k_ - ls_size);
}
int Find(int x_) {
return fa[x_] == x_ ? x_ : fa[x_] = Find(fa[x_]);
}
void Unite(int x_, int y_) {
x_ = Find(x_), y_ = Find(y_);
if (x_ == y_) return ;
root[x_] = Merge(root[x_], root[y_], 1, kInf);
fa[y_] = x_;
}
//=============================================================
int main() {
m = read();
while (m --) {
int opt = read();
if (opt == 1) {
int x = read();
fa[++ n] = n;
Insert(root[n], 1, kInf, x, 1, log(1.0 * x));
} else if (opt == 2) {
int x = read(), y = read();
Unite(x, y);
} else if (opt < 5) {
int a = Find(read()), x = read();
int ret = Modify(root[a], 1, kInf, x, opt == 3);
Insert(root[a], 1, kInf, x, ret, log(1.0 * x) * 1.0 * ret);
} else if (opt == 5) {
int a = Find(read()), k = read();
printf("%d\n", QueryKth(root[a], 1, kInf, k));
} else if (opt == 6) {
int a = Find(read()), b = Find(read());
printf("%d\n", prod[root[a]] > prod[root[b]]);
} else if (opt == 7) {
int a = Find(read());
printf("%d\n", size[root[a]]);
} else {
int koishi = read();
if (opt == 8) int satori = read();
}
}
return 0;
}