图的连通性问题 : 并查集的基础应用
提出背景
在图论问题中，我们经常性遇到一些关于两个点是否连通的问题。
比如在最小生成树kruskal算法中，我们在逐渐选取最小边的时候，我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。
有基础的同学都知道，在大多数图论问题中，我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的，这样能够提高遍历和存储的时间和空间效率。但实际上，这两种方式也有一个严重的缺陷：不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。
这时我们需要一种数据结构能够方便的维护查询图的连通性。
并查集基本概念及操作介绍
所谓并查集，其实是相互连通的各点通过父节点表示法构成的森林（很多棵树的集合），我们判断两点是否相互连通，实际上就是通过他们是否在同一棵树内。很显然同一棵树内的所有点相互连通，这个通过刚才的定义就可以显然得出了，并不需要证明（实际上这里给出的定义是我个人对并查集的理解）。
由上面所说的父节点表示法，并查集这种数据结构自然而然地就是只需要一个一维数组表示就行了，被没有多么麻烦。我们假设为f[i]表示节点i在并查集构成的森林中的父节点。f[i]的初始值设定为i本身
通常来讲，并查集有两种基本操作：
1. 查询操作：查询当前点u的所在的并查集构成的树的根是哪个节点，具体代码实现为：
int find(int x){if(x != f[x])return find(f[x]);//x == f[x]表示节点x即为本并查集的根return x;}
- 合并操作：将两个并查集（两个树）合并，其代表的是这两个连通块之间出现了一条连通边。我们只需要将这两个并查集的树的根进行合并即可，具体操作代码为：
void merge(int u,int v){u = find(u);v = find(v);//分别寻找所在并查集的根f[v] = u;//f[u] = v也可以,通常来讲return;}
这两项就是并查集的基本操作了。
并查集构造、查询方式的优化
上面的并查
#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
e[cnt].next = h[u];h[u] = cnt++;
return;
}
bool spfa(int s,int t){
for(int i = s;i <= t;++i){
d[i] = -INF;
vis[i] = 0;
}
d[t] = 0;
vis[t] = 1;
q.push_back(t);
while(!q.empty()){
int now = q.front();
q.pop_front();
vis[now] = 0;
for(int i = h[now];i != -1;i = e[i].next){
int v = e[i].to;
if(e[i^1].cap && d[v] < d[now] - e[i].cost){
d[v] = d[now] - e[i].cost;
if(!vis[v]){
vis[v] = 1;
if(!q.empty() && d[q.front()] < d[v])q.push_front
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
const int INF = 0x3f3f3f3f
ll n, a[maxn],b[maxn],c[maxn],p[maxn];
ll w[maxn][maxn];
ll lx[maxn] , ly[maxn];
ll linker[maxn];
ll slack[maxn];
bool visy[maxn];
ll pre[maxn];
void bfs( ll k ){
ll x , y = 0 , yy = 0 , delta;
memset( pre , 0 , sizeof(pre) );
for(int i = 1 ; i <= n ; i++ ) slack[i] = INF;
linker[y] = k;
while(1){
x = linker[y]; delta = INF; visy[y] = true;
for(int i = 1 ; i <= n ;i++ ){
if( !visy[i] ){
if( slack[i] > lx[x] + ly[i] - w[x][i] ){
slack[i] = lx[x] + ly[i] - w[x][i];
pre[i] = y;
}
if( slack[i] < delta ) delta = slack[i] , yy = i ;
}
}
for(int i = 0 ; i <= n ; i++ ){
if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
else slack[i] -= delta;
}
y = yy ;
if( linker[y
题目大意
给定一个序列，每次询问参数为pos和k，求问长度为pos的和最大的子序列中第k个元素是什么。
题解
这题其实有一个easy version，用map稍微搞一搞就能过那种
然后这题数据范围到2e5了，就不能用map乱搞了。
首先我们要想一下如何构造这个长为pos且和最大的子序列怎么构造呢？
我们只要对原序列从大到小排一次序，且保证在等大的时候原序列中靠前的元素在排序后也考前，然后我们只需要从排序后的序列中取前pos个数，就是符合要求的子序列了。
但是询问次数过多，我们就不能对于每一个request都重新求一次符合要求的子序列。
我们发现这个序列是递增的，就是如果pos[i] > pos[j]，那么询问i的序列一定就是询问j的序列再接上一段。
于是我们将询问也按照pos从小到大排序。
但是我们怎么找这个子序列中第k个元素是多少呢？
我们在对原序列进行排序的时候同时记录下元素在原序列中的位置，然后在选序列的时候，可以用这样一种经典的记录方式：
将当前被选中的元素加入树状数组进行计数，即将该元素对应的原序列的位置在树状数组上的位置进行update(pos,1)
当我们询问的时候，从1——n进行二分，统计在这个位置mid之前的选中数一共有多少个。
最终二分出来的答案就代表着选中序列第k位在原数组中的位置了。直接去原数组中找就可以了。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n,m;
int a[maxn];
int c[maxn];
int lowbit(int x){
return x & -x;
}
void update(int pos,int x){
while(pos <= n){
c[pos] += x;
pos += lowbit(pos);
}
return;
}
int val(int pos){
int ret = 0;
while(pos > 0){
ret += c[pos];
pos -= lowbit(pos);
}
return ret;
}
struct num{
int id;
int val;
}b[max
可持久化数据结构
众所周知，在竞赛界有这么一种神奇的解决方案，用以解决简单数据结构无法恢复历史版本的问题。
它就是可持久化！
如何可持久化？当然是要记录历史信息了。
但是那消耗空间不会巨大吗？
起始如果我们可以合理运用历史版本信息，我们就可以在创建新版本的时候尽可能地缩减需要的空间。
我们可以在当前版本复用未被修改地上一个版本的信息内存。
然而如何才能尽可能地去复用内存空间呢？这就需要树形结构了。
所以，对于所有的可持久化数据结构而言，都需要可持久化数组（一棵树）这样的基础。
怎么建立可持久化数组呢？可持久化数组的建立类似线段树，也就是可持久化线段树的建树过程。
所以说，可持久化线段树的建树是所有可持久化数据结构的学习基础。
可持久化并查集
并查集是一类用于判断图中两点是否连通的数据结构，其优点是时空复杂度低，但也有缺点，就是无法进行边的删除，只能进行边的添加。
如果我们要删除一些满足特定性质的边怎么办？比如删除最近添加的几条边？
显然最简单的并查集已经无法满足这个需求，所以我们借助可持久化数组将并查集升华成可持久化并查集。
并查集中有一个非常好的优化方法叫做路径压缩，但是如果在可持久化并查集中，这种优化方法就不适用了，因为它不能保持原来的各个连通块之间的关系，这样我们恢复历史版本的时候就会出问题。
为了使回溯历史版本时不出问题，再让并查集尽可能地优化，我们这里使用另外一种优化方法：按秩合并。
按秩合并的基本思路是：合并时将并查集树深度小的树根连到并查集树深度大的树根，以尽可能缩小并查集的深度。从而减少查找祖先的时间复杂度。
这种优化方法虽然没有路径压缩更优，但是非常契合可持久化的要求，所以拿来做可持久化并查集。
这里要注意，可持久化并查集中的可持久化数组的非叶子节点是没有意义的，只是拿来记录当前内存对应的原数组的下标区间，只有叶子节点才真正表示一个历史版本下某个节点的信息。
我们拆分成多个过程来看：
一、可持久化并查集的初始化建立
这一部分跟线段树差不多，只是到叶子节点的时候，其记录的信息要按照并查集按秩合并的初始化，将fa和dep全部初始化。
int build(int l,int r){
int now = ++cnt;
tr[now].l = l;
tr[now].r = r;
tr[now].lc = tr[now].rc = tr[now].fa = tr[now].
题解
第一问快速幂
第二问是扩展欧几里得算法求不定方程
第三问使用BSGS算法求离散模对数
三个函数直接看代码吧……纯板子题……
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
ll num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
ll ret = 1;
while(b > 0){
if(b & 1){
ret = ret * a;
ret %= mod;
}
b >>= 1;
a = a * a;
a %= mod;
}
return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(b == 0){
d = a;
x = 1;
y = 0;
return;
}
exgcd(b,a%b,d,x,y);
ll tp = x;
x = y;
y = tp - (a / b) * y;
return;
}
void BSGS(ll y,ll z,ll p){
mp.clear();
y %= p;
if(y == 0 && z == 0){
cout << "1"
题目大意
给出一些线段，给出这些线段的起始和终止位置，并给出这些线段选取的两个代价A和B，要求选取一些线段覆盖区间[1----t]，使得ΣAi与ΣBi的比值最小。
题解
很经典的01分数规划问题的形式。
当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题，当时还是我们队拿的那题一血，可惜当时的队友现在因为一些原因分开了，真是令人感叹，sigh。
回归正题……
这一类最经典的01分数规划的解题基本思路是十分固定的，如下：
1.二分一个目标值mid
2.贪心地去构造检验是否有一组可行解，使得ΣAi / ΣBi <= mid;
3.如果能构造出这样一组可行解，那么将二分区间向左缩进，否则将二分区间向右缩进。
那么我们如何去构造这样一组可行解呢？
我们将不等式换一下形式，换成没有分式的不等式形式：mid * ΣBi - ΣAi >= 0；
这样我们就需要构造一组线段选取方案去满足上面的那个等式。
为了使得选取的区间完整，我们可以先将区间按照左端点为第一关键字，右端点为第二关键字从小到大进行排序，这样会保证在能构造出一组当前mid值条件下的可行解的时候我们不会漏掉中间的一部分区间。
之后我们先将所有mid * Bi - Ai >= 0的所有区间都选中，并统计加和sum，因为这些区间会使得不等式左边尽可能大。如果这时候已经能够覆盖所有需要覆盖的区间，那么就说明这样就已经能达到一组可行解了。
如果还没有覆盖所有区间，那么我们就要在剩下没有选中的线段中选取一些线段使得他们的ΣAi - mid * ΣBi尽可能小，这样不等式才能尽可能成立。
如何尽可能小？这时候我们可以使用树状数组去统计当前线段起点S前一个位置S-1到t的最小值（这里树状数组需要维护当前点到t的最小代价值），然后将选这个线段的方案统计入树状数组去求最小值。
之后我们去查询到t的最小值，判断sum是否大于等于 query(t)。如果sum >= query(t)，则满足上述不等式，二分区间向左缩进。否则将二分区间向右缩进。
为了保证二分精度，我们可以限定二分次数，而非用eps判定二分区间端点l与r的关系。具体实现见代码吧。
代码
#include <bits/stdc++.h>
using namespace std;
int n,t;
int T;
const int maxn = 1e5+5;
struct interv{
int
题解
首先声明……其实我们的答案跟没太大关系，这一部分只需要在最后的时候对应乘上即可，此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次，那么选择颜色种类的方案数即为,然后我们去用这i个颜色涂这n个位置的时候，实际上就是一个可重排列的计算数，方案总数为,然后剩下的位置任意涂色，一共还剩n-i*S个位置，每个位置有m-i种颜色选择，所以方案数为。
我们记
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候，我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设为恰好i种颜色都恰好出现k次,由容斥原理有：
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
for(int i = 2;i <= x;++i){
fac[i] = fac[i-1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
finv[i] = finv[i-1] * inv[i] % mod;
}
return;
}
ll quick_pow(ll a,ll b,ll mod){
ll ret = 1;
while(b){
if(b & 1)
ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
len = 1;lg = 0;
for(len = 1;len < k;len <<= 1,lg++);
for(int i = 0;i < len;++i)
rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
for(int i = 0;i < len;++i){
if(i < rev[i])
swap(a[i],a[rev[i
题目大意
给定一个n个点的DAG（有向无环图），每个点一开始都是白色，每一次操作会改变一个指定的点的颜色，并询问当前有多少对白点对(u,v)互相可达（存在一条从u到v的有向路径使得路径上全部为白色的点）。
题解
可以认为黑色点与其他点都不连通。
所以我们每一次更改点的颜色实际都是再更改图的联通关系。
我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系（这时候就通过位运算或|来代替Floyd原先的+就好了，因为位运算或即为逻辑加操作）。
但是我们发现这样复杂度是不对的……
这三种最快的topsort复杂度也是O(qnm)的，明显不符合我们的复杂度要求。
这时候我们注意到对于联通关系，两点间的联通关系也即用0表示不连通，1表示联通。
我们对于更新也是这样的：
假设当前检索点为u，下一个点为v，则对于所有联通u的点k，假设mp[i][j]表示是否可从i联通到j，则有
mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];
可以看到这个更新过程实际上只有位运算的或操作，只有0和1的运算，所以可以用bitset进行加速。
当我们检索到当前的点u时，先预处理设定mp[u][u] = 1，表示当前点可以到达当前点。最终因为答案是算不相同的点u和v联通个数，所以最后进行统计的时候答案整体-n即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
for(int i = 1;i <= n;++i)
con[i].reset();
for(int i = 1;i <= n;++i){
if(!c[i])
con[i][i] = 1;
vis[i] = 0;
}
for(int i = 1;i <= n;++i){
tmp[i] = d[i];