【做題記錄】csp2025-提高組并查集專題
A. Arpa's weak amphitheater and Mehrdad's valuable Hoses
用并查集將每個朋友圈找出，然后 DP。
設 \(dp_{i,j}\) 表示前 \(i\) 個朋友圈，重量為 \(j\) 的最大美麗度。轉移分為從這個朋友圈中選一個轉移、用這個朋友圈的和轉移和不轉移（直接繼承）。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5;
int n,m,tot,dp[maxn][maxn];
int a[maxn],b[maxn];
int fa[maxn],sz[maxn];
int ying[maxn];
vector<int> hao[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m)read(tot);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
}
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
while(m--){
int u,v;
read(u)read(v);
u=find(u),v=find(v);
if(u==v){
continue;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
int num=0;
for(int i=1;i<=n;i++){
hao[find(i)].pb(i);
if(find(i)==i){
ying[++num]=i;
}
}
memset(dp,-0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=num;i++){
for(int j=0;j<=tot;j++){
dp[i][j]=dp[i-1][j];
}
int sa=0,sb=0;
for(int x:hao[ying[i]]){
sa+=a[x],sb+=b[x];
for(int j=a[x];j<=tot;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j-a[x]]+b[x]);
}
}
for(int j=sa;j<=tot;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j-sa]+sb);
}
}
int ans=0;
for(int i=1;i<=tot;i++){
ans=max(ans,dp[num][i]);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
B. Tokitsukaze and Two Colorful Tapes
將 \(a_i\) 與 \(b_i\) 連邊。發現得到若干個相互獨立的環。要求是給每個點賦權，邊權為兩點權的差，使邊權最大。
考慮環上點權比兩邊都大的點，設權值之和為 \(x\)，點權比兩邊都小的點記為 \(y\)，則 \(ans=2(x-y)\)。
發現只有這兩種點會對答案產生貢獻，那么我們盡量讓這兩種點的數量最大。容易發現這兩種點的數量相同。對于一個大小為 \(sz\) 的環，數量最大都為 \(\lfloor sz\rfloor\)，記為 \(num\)。
還是要讓答案最大，那么就讓大的那些點為 \(n-num+1\dots n\)，小的那些為 \(1\dots num\)。則答案為
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int T,n,a[maxn],b[maxn];
int fa[maxn],sz[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
read(n);
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
}
for(int i=1,u,v;i<=n;i++){
u=find(a[i]),v=find(b[i]);
if(u==v){
continue;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
int num=0;
for(int i=1;i<=n;i++){
if(fa[i]==i){
num+=sz[i]>>1;
}
}
printf("%lld\n",num*2ll*(n-num));
}
return 0;
}
}
int main(){return asbt::main();}
C. AND-MEX Walk
因為是不斷按位與，\(w_1,w_1\&w_2,w_1\&w_2\&w_3,\dots\) 這個序列一定是單調不增的。觀察樣例可以發現，答案只可能為 \(0\)，\(1\) 或 \(2\)。
簡單證明一下：
如果答案大于 \(2\)，那么在 \(w_1,w_1\&w_2,w_1\&w_2\&w_3,\dots\) 中一定存在 \(0\)，\(1\) 和 \(2\)。又因為單調不增，則一定是在 \(2\) 后面出現了一個 \(1\)。然而 \(2\) 怎么與都是與不出來 \(1\) 的。因此答案不可能大于 \(2\)。
于是直接去判斷答案是 \(0\)，\(1\) 還是 \(2\) 就行了。
首先是 \(0\) 的情況，即這個序列中沒出現過 \(0\)，那么在二進制位中一定有至少一位是 \(1\)，即走過的每一條邊在這一位都是 \(1\)。于是可以給每一個二進制位開一個并查集，連接在這一位上是 \(1\) 的邊兩邊的點。如果 \(u\) 和 \(v\) 在某一位上在一個集合里，那么答案就是 \(0\)。
考慮判斷答案是 \(1\) 的情況。記 \(w_1,w_1\&w_2,w_1\&w_2\&w_3,\dots\) 為 \(a_1,a_2,a_3,\dots\)，記總共有 \(tot\) 條邊。則一定存在一個 \(k\in[1,tot)\) 滿足 \(a_1,a_2,\dots,a_{k-1}\) 均大于 \(1\)，而 \(a_k,a_{k+1},\dots,a_{tot}\) 都是 \(0\)。前面那部分是好處理的，只需在除了末位的某一位上都是 \(1\) 就好了，和第一種情況類似。考慮要與出 \(0\)，則末位一定得是 \(0\)。因此新開一個并查集，將每條末位為 \(0\) 的邊兩邊的每個點都向一個虛點 \(0\) 連邊，只需檢查 \(u\) 與 \(v\) 中任意一個在除末位以外的某一位與 \(0\) 聯通就行了。這樣正確的原因是，因為答案已經不可能是 \(0\) 了，所以每一位到最后都是一定能被消掉的。
如果以上兩種情況均不滿足，則答案為 \(2\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,q;
struct dsu{
int fa[maxn],sz[maxn];
il void init(){
for(int i=0;i<=n;i++){
fa[i]=i,sz[i]=1;
}
}
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
// cout<<u<<" "<<v<<"\n";
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v];
fa[v]=u;
}
else{
sz[v]+=sz[u];
fa[u]=v;
}
}
il bool check(int u,int v){
return find(u)==find(v);
}
}D[2][35];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
read(n)read(m);
for(int x=0;x<30;x++){
D[0][x].init();
D[1][x].init();
}
for(int i=1,u,v,w;i<=m;i++){
read(u)read(v)read(w);
for(int x=0;x<30;x++){
if(w>>x&1){
// puts("666");
D[0][x].merge(u,v);
D[1][x].merge(u,v);
}
}
if(w&1){
continue;
}
for(int x=0;x<30;x++){
// puts("777");
D[1][x].merge(u,0);
D[1][x].merge(v,0);
}
}
read(q);
while(q--){
int u,v;
read(u)read(v);
for(int x=0;x<30;x++){
if(D[0][x].check(u,v)){
puts("0");
goto togo;
}
}
for(int x=1;x<30;x++){
if(D[1][x].check(u,0)){
puts("1");
goto togo;
}
}
puts("2");
togo:;
}
return 0;
}
}
int main(){return asbt::main();}
D. Anton and Tree
直接說結論：將相同顏色的連通塊縮成點建出新樹，設新樹的直徑上點數為 \(d\)，則答案為 \(\lfloor \frac d 2\rfloor\)。
證明：
縮點后要把整棵樹變成同一個顏色，那直徑肯定也得變成同一種顏色。將直徑變為同一種顏色的最小操作次數顯然為 \(\lfloor \frac d 2\rfloor\)。
然后直徑上的點如果有連出直徑外的邊，這條多出來的鏈長度一定 \(\le\) 這個點與較近的直徑端點的距離，否則就會有更長的路徑充當直徑。因此從這個點開始擴充，擴充到較近的直徑端點時一定已經把這個點連出去的鏈都擴充完了，于是就可以在直徑上換個點來擴充了。因此答案就是 \(\lfloor \frac d 2\rfloor\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,a[maxn],fa[maxn],sz[maxn];
pii ed[maxn];
vector<int> e[maxn];
il int find(int x){
return fa[x]!=x?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
int dep[maxn],mxd[maxn],des[maxn];
il void dfs(int u,int fa){
mxd[u]=dep[u]=dep[fa]+1;
des[u]=u;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
if(mxd[v]>mxd[u]){
mxd[u]=mxd[v];
des[u]=des[v];
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
fa[i]=i,sz[i]=1;
}
for(int i=1,u,v;i<n;i++){
read(u)read(v);
ed[i]=mp(u,v);
if(a[u]==a[v]){
merge(u,v);
}
}
for(int i=1,u,v;i<n;i++){
u=find(ed[i].fir);
v=find(ed[i].sec);
if(u!=v){
e[u].pb(v),e[v].pb(u);
}
}
int rt=find(1);
dfs(rt,0);
rt=des[find(1)];
dfs(rt,0);
printf("%d",mxd[rt]>>1);
return 0;
}
}
int main(){return asbt::main();}
E. Sanae and Giant Robot
記 \(c_i=a_i-b_i\)。問題轉化為每次選擇一個區間 \([l,r]\) 滿足 \(\sum_{i=l}^{r}c_i=0\)，將 \(c_{l\dots r}\leftarrow 0\)。要求是最后要滿足 \(\forall i\in[1,n],c_i=0\)。
再記 \(sc_i\) 為 \(c_i\) 的前綴和。問題再次轉化為每次選擇一個區間 \([l,r]\) 滿足 \(sc_{l-1}=sc_r\)，將 \(sc_{l\dots r-1}\leftarrow sc_r\)。要求是最后要滿足 \(\forall i\in[1,n],sc_i=0\)。
因為最后要將 \(sc\) 數組推平成 \(0\)，所以只有操作 \(sc_{l-1}=sc_r=0\) 的區間才有意義。于是可以用 set 維護 \(sc\) 值不為 \(0\) 的位置，進行 \(bfs\)，每次用 \(sc=0\) 的位置，枚舉它能更新的區間并將區間內的元素從 set 中刪除即可。
因為每個位置最多進出 set 各一次，所以時間復雜度為 \(O(n\log n)\)。
突然發現這道題沒有用到并查集。。。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int T,n,m;
ll a[maxn],b[maxn],sc[maxn];
queue<int> q;
set<int> ji;
vector<int> e[maxn];
il void solve(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
}
for(int i=1,l,r;i<=m;i++){
read(l)read(r);
e[l-1].pb(r),e[r].pb(l-1);
}
for(int i=1;i<=n;i++){
sc[i]=sc[i-1]+a[i]-b[i];
}
ji.clear();
for(int i=0;i<=n;i++){
if(sc[i]){
ji.insert(i);
}
else{
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int v:e[u]){
if(sc[v]){
continue;
}
int l=min(u,v),r=max(u,v);
auto tmp=ji.lwrb(l);
while(tmp!=ji.end()&&*tmp<=r){
sc[*tmp]=0,q.push(*tmp);
tmp=ji.erase(tmp);
}
}
}
puts(ji.empty()?"YES":"NO");
for(int i=0;i<=n;i++){
e[i].clear();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
F. Nene and the Passing Game
先推式子。
令 \(i>j\)，則：
又因為對于 \(i>j\)，\(i+l_i\) 一定大于 \(j-l_j\)。
所以對于所有 \(i\) 和 \(j\)，能相互傳球的條件就是
將這樣的 \(i\) 和 \(j\) 連邊，答案顯然就是連通塊的數量。
于是建虛點，將 \(i\) 向 \([i-r_i,i-l_i]\) 和 \([i+l_i,i+r_i]\) 中的虛點連邊。時間無法接受，因此將 \(i\) 向區間中的一個點連邊，區間內部再互相連邊。這可以用并查集 \(+\) 類似掃描線的方式完成。
但是問題在于，這樣連邊可能會使 \(i\) 和 \(j\) 因為 \([i-r_i,i-l_i]\) 和 \([j-r_j,j-l_j]\) 相交而連通，但這顯然不是我們希望得到的。
那怎么辦呢，答案是對于所有 \(x\)，如果 \(\forall i\in[1,n],x\notin[i-r_i,i-l_i]\) 或者 \(\forall i\in[1,n],x\notin[i+l_i,i+r_i]\)，那就直接將這個點刪掉。這樣就能保證兩個點相連一定是合法的了。這也可以用類似掃描線的方式完成。
連邊時需要二分，復雜度為 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e6+5;
int T,n,a[maxn],b[maxn];
int fa[maxn<<2],sz[maxn<<2];
int cl[maxn<<2],cr[maxn<<2];
int hao[maxn<<2],c[maxn<<2];
bitset<maxn<<2> vis;
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
il int id(int x){
return x+(n<<1|1);
}
il void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i])read(b[i]);
}
// cout<<(n<<2|1);
for(int i=1;i<=(n<<2|1);i++){
// cout<<i<<"\n";
fa[i]=i,sz[i]=1;
cl[i]=cr[i]=c[i]=vis[i]=0;
}
// puts("666");
for(int i=1,l,r;i<=n;i++){
l=id(i-b[i]),r=id(i-a[i]);
cl[l]++,cl[r+1]--;
l=id(i+a[i]),r=id(i+b[i]);
cr[l]++,cr[r+1]--;
}
int tot=0;
for(int i=1;i<=(n<<2|1);i++){
cl[i]+=cl[i-1],cr[i]+=cr[i-1];
if(cl[i]&&cr[i]){
hao[++tot]=i;
}
}
for(int i=1,l,r;i<=n;i++){
l=lwrb(hao+1,hao+tot+1,id(i-b[i]))-hao;
r=uprb(hao+1,hao+tot+1,id(i-a[i]))-hao-1;
if(l<=r){
merge(i,hao[l]);
c[l]++,c[r]--;
}
l=lwrb(hao+1,hao+tot+1,id(i+a[i]))-hao;
r=uprb(hao+1,hao+tot+1,id(i+b[i]))-hao-1;
if(l<=r){
merge(i,hao[l]);
c[l]++,c[r]--;
}
}
for(int i=1;i<=tot;i++){
c[i]+=c[i-1];
if(c[i]){
merge(hao[i],hao[i+1]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[find(i)]){
vis[find(i)]=1;
ans++;
}
}
printf("%d\n",ans);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
G. Clearing Up
思路是首先在不成環的前提下加入所有 \(S\) 邊，然后加入若干條 \(M\) 邊使加入的邊構成一棵樹。此時加入的所有 \(M\) 邊都欽定必須選。然后再刪掉所有 \(S\) 邊，繼續在不成環的前提下加 \(M\) 邊使 \(M\) 邊數量達到 \(\lfloor\frac{n}{2}\rfloor\)。然后再加入 \(\lfloor\frac{n}{2}\rfloor\) 條 \(S\) 邊使圖變成一棵樹即可。操作過程中不斷判無解。
證明看似麻煩，實際一點都不簡單很容易。要證明的其中一點是：如果我們選定的這 \(\lfloor\frac{n}{2}\rfloor\) 條 \(M\) 邊中的一部分能與所有不成環的 \(S\) 邊形成一棵樹，那么就一定能構造出方案。其實這是顯然的，考慮生成樹的構造方式，當前我們選定的 \(M\) 邊因為不成環一定是生成樹的一部分，而剩下的點一定是能由 \(S\) 邊加進來的。所以正確性是有的。
另一點是：一開始加入 \(S\) 邊時加了一些邊而舍去了另一些邊，這會不會影響答案？答案是不會。原因是，首先不論以怎樣的順序加入，加進來的邊數都一定是相同的。其次，在最后加 \(S\) 邊時，可供選擇的 \(S\) 邊實際上是變多了的（就是說第一步中沒選的現在也可以選），而根據上面的證明，一定是能構造出方案的，所以多一些可供選的邊也不會影響正確性。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5,maxm=1e5+5;
int n,m,num1,num2;
int fa[maxn],sz[maxn];
int a[maxm],b[maxm];
pii e[maxm];
bool vis[maxm];
il void wuj(){
puts("-1");
exit(0);
}
il void init(){
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
}
il int find(int x){
return fa[x]!=x?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v];
fa[v]=u;
}
else{
sz[v]+=sz[u];
fa[u]=v;
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
if(n%2==0){
wuj();
}
for(int i=1,u,v;i<=m;i++){
read(u)read(v);
e[i]=mp(u,v);
char w;
scanf(" %c",&w);
if(w=='S'){
a[++num1]=i;
}
else{
b[++num2]=i;
}
}
init();
int cnt1=0,cnt2=0;
for(int i=1,u,v;i<=num1;i++){
u=e[a[i]].fir,v=e[a[i]].sec;
if(find(u)==find(v)){
continue;
}
cnt1++,merge(u,v);
}
if(cnt1<n>>1){
wuj();
}
for(int i=1,u,v;i<=num2;i++){
u=e[b[i]].fir,v=e[b[i]].sec;
if(find(u)==find(v)){
continue;
}
cnt2++,merge(u,v),vis[b[i]]=1;
}
if(cnt1+cnt2<n-1){
wuj();
}
init();
for(int i=1;i<=m;i++){
if(vis[i]){
merge(e[i].fir,e[i].sec);
}
}
for(int i=1,u,v;i<=num2;i++){
if(cnt2==n>>1){
break;
}
u=e[b[i]].fir,v=e[b[i]].sec;
if(find(u)==find(v)){
continue;
}
cnt2++,merge(u,v),vis[b[i]]=1;
}
if(cnt2<n>>1){
wuj();
}
for(int i=1,u,v;i<=num1;i++){
u=e[a[i]].fir,v=e[a[i]].sec;
if(find(u)==find(v)){
continue;
}
merge(u,v),vis[a[i]]=1;
}
printf("%d\n",n-1);
for(int i=1;i<=m;i++){
if(vis[i]){
printf("%d ",i);
}
}
return 0;
}
}
int main(){return asbt::main();}
H. [HEOI2016/TJOI2016] 樹
離這個節點最近的一個祖先，那必然是 \(dfn\) 最大的一個。直接用線段樹區間取 \(\max\) 和單點查詢就行了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,dfn[maxn],idx[maxn],sz[maxn],cnt;
vector<int> e[maxn];
il void dfs(int u,int fa){
dfn[u]=++cnt;
idx[cnt]=u;
sz[u]=1;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
sz[u]+=sz[v];
}
}
int zhi[maxn<<2];
il void build(int id,int l,int r){
zhi[id]=1;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void upd(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
zhi[id]=max(zhi[id],val);
return ;
}
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
}
il int query(int id,int l,int r,int pos){
int res=zhi[id];
if(l==r){
return res;
}
int mid=(l+r)>>1;
if(pos<=mid){
return max(res,query(lid,l,mid,pos));
}
return max(res,query(rid,mid+1,r,pos));
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
dfs(1,0);
build(1,1,n);
while(m--){
char opt;
int u;
scanf(" %c",&opt);
read(u);
if(opt=='Q'){
printf("%d\n",idx[query(1,1,n,dfn[u])]);
}
else{
upd(1,1,n,dfn[u],dfn[u]+sz[u]-1,dfn[u]);
}
}
return 0;
}
}
int main(){return asbt::main();}
本來還以為是又放錯題了，結果去洛谷題解區一看還真能拿并查集做，有點類似 \(tarjan\) 求 \(lca\)。就是離線下來，如果這個點被染色了就把 \(fa\) 指向自己，否則指向自己的父親，倒序處理詢問，操作就將這個節點的染色次數 \(-1\) 就行。方法不錯，就不打了（逃
I. [HNOI2016] 最小公倍數
顯然能將最小公倍數轉化為 \(a\) 和 \(b\) 分別取 \(\max\)。顯然對于一個詢問，只有 \(a\) 和 \(b\) 都不超過它的邊能產生貢獻。將能產生貢獻的邊加入，并查集判斷連通性再判斷 \(a\) 和 \(b\) 的最大值是否都符合要求即可。
將所有邊先按 \(a\) 排序，分塊。然后對于每個詢問，令它歸屬的塊編號為最大的 \(i\)，使 \(1\) 到 \(i-1\) 塊中的邊的 \(a\) 都 \(\le\) 這個詢問的 \(a\)。接下來順序掃描每一個塊，維護當前掃過的所有塊中的邊按 \(b\) 排序的序列。每掃到一個塊，先將這個塊中的詢問插入到維護的序列中，然后遍歷插入后的序列，若遍歷到邊則直接合并，若遍歷到詢問則將當前塊中能對這個詢問產生貢獻的邊加入，統計答案后再撤銷。需要可撤銷并查集。最后再將當前塊中的邊插入序列即可。可以用歸并排序完成。
然后就是玄學的復雜度分析了。設塊長為 \(B\)。加入所有邊的復雜度為 \(O(\frac{m^2\log n}{B})\)，而處理詢問的復雜度為 \(O(qB\log n)\)。令二者相等，顯然最佳的塊長應為 \(\frac{m}{\sqrt{q}}\)，時間復雜度為 \(O(m\log n\sqrt{q})\) 約為 \(3\times 10^8\)，然而會 TLE 2 個點。考慮處理詢問那一塊每個詢問都是跑不滿 \(B\) 次的，不妨將那個 \(\log n\) 舍掉，于是令 \(\frac{m^2\log n}{B}=qB\)，解出塊長應為 \(m\sqrt{\frac{\log n}{q}}\)，然而會 TLE 4 個點。但若將加邊的 \(\log n\) 舍掉，解出塊長為 \(\frac{m}{\sqrt{q\log n}}\)，此時加邊那部分的復雜度為 \(O(m\log n\sqrt{q\log n})\)，是 \(1.3\times 10^9\) 左右的，卻通過了。所以說做分塊時一定要多試試不同的塊長跑極限數據，以實際跑下來的時間為準。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=ch^48;
ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
}
using namespace IO;
const int maxn=1e5+5;
int n,m,q,blen,bnum,st[maxn],ed[maxn],bel[maxn],wel[maxn];
int fa[maxn],sz[maxn],mxa[maxn],mxb[maxn],top;
bool ans[maxn];
vector<int> xwn[maxn];
struct node{
int u,v,a,b,id;
bool typ;
}bian[maxn],wen[maxn],hp1[maxn<<1],hp2[maxn<<1];
il bool cmpa(const node &x,const node &y){
return x.a<y.a;
}
il bool cmpb(const node &x,const node &y){
return x.b<y.b;
}
il void gwel(){
int p1=1,p2=1,p3=1;
while(p1<=m&&p2<=q){
if(cmpa(wen[p2],bian[p1])){
hp1[p3++]=wen[p2++];
}
else{
hp1[p3++]=bian[p1++];
}
}
while(p1<=m){
hp1[p3++]=bian[p1++];
}
while(p2<=q){
hp1[p3++]=wen[p2++];
}
bel[0]=++bnum;
for(int i=1,li=0,cnt=0;i<=p3;i++){
if(hp1[i].typ){
continue;
}
for(int j=li+1;j<i;j++){
wel[hp1[j].id]=bel[hp1[i].id];
xwn[bel[hp1[i].id]].pb(++cnt);
}
li=i;
}
}
il int find(int x){
return x!=fa[x]?find(fa[x]):x;
}
struct unod{
int u,v,fau,fav,mxau,mxbu,mxav,mxbv;
}zhan[maxn];
il void merge(int u,int v,int a,int b){
u=find(u),v=find(v);
zhan[++top]=(unod){u,v,fa[u],fa[v],mxa[u],mxb[u],mxa[v],mxb[v]};
if(u==v){
mxa[u]=max(mxa[u],a),mxb[u]=max(mxb[u],b);
return ;
}
if(sz[u]<sz[v]){
swap(u,v);
}
sz[u]+=sz[v],fa[v]=u;
mxa[u]=max({mxa[u],mxa[v],a});
mxb[u]=max({mxb[u],mxb[v],b});
}
il void che(){
unod tmp=zhan[top--];
int u=tmp.u,v=tmp.v;
fa[u]=tmp.fau,fa[v]=tmp.fav;
mxa[u]=tmp.mxau,mxb[u]=tmp.mxbu;
mxa[v]=tmp.mxav,mxb[v]=tmp.mxbv;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
n=read(),m=read();
for(int i=1,u,v,a,b;i<=m;i++){
u=read(),v=read(),a=read(),b=read();
bian[i]=(node){u,v,a,b,0,0};
}
q=read();
for(int i=1,u,v,a,b;i<=q;i++){
u=read(),v=read(),a=read(),b=read();
wen[i]=(node){u,v,a,b,i,1};
}
sort(bian+1,bian+m+1,cmpa);
sort(wen+1,wen+q+1,cmpa);
blen=max(sqrt(m*1.0*m/q/(log2(n)>1?log2(n):1)),1.0);
bnum=(m+blen-1)/blen;
for(int i=1;i<=bnum;i++){
st[i]=ed[i-1]+1;
ed[i]=min(ed[i-1]+blen,m);
for(int j=st[i];j<=ed[i];j++){
bel[j]=i;
}
}
for(int i=1;i<=m;i++){
bian[i].id=i;
}
gwel();
for(int i=1;i<=bnum;i++){
sort(xwn[i].begin(),xwn[i].end(),[](const int &x,const int &y){return cmpb(wen[x],wen[y]);});
sort(bian+st[i],bian+ed[i]+1,cmpb);
}
st[bnum]=m+1;
for(int i=1,p1,p2,p3;i<=bnum;i++){
p1=p3=1,p2=0;
while(p1<st[i]&&p2<xwn[i].size()){
if(cmpb(wen[xwn[i][p2]],hp2[p1])){
hp1[p3++]=wen[xwn[i][p2++]];
}
else{
hp1[p3++]=hp2[p1++];
}
}
while(p1<st[i]){
hp1[p3++]=hp2[p1++];
}
while(p2<xwn[i].size()){
hp1[p3++]=wen[xwn[i][p2++]];
}
for(int j=1;j<=n;j++){
fa[j]=j,sz[j]=1,mxa[j]=mxb[j]=-1;
}
top=0;
for(int j=1;j<p3;j++){
if(hp1[j].typ){
int tmp=top;
for(int k=st[i];k<=ed[i];k++){
if(bian[k].a<=hp1[j].a&&bian[k].b<=hp1[j].b){
merge(bian[k].u,bian[k].v,bian[k].a,bian[k].b);
}
}
int rt=find(hp1[j].u);
if(rt==find(hp1[j].v)&&mxa[rt]==hp1[j].a&&mxb[rt]==hp1[j].b){
ans[hp1[j].id]=1;
}
while(top>tmp){
che();
}
}
else{
merge(hp1[j].u,hp1[j].v,hp1[j].a,hp1[j].b);
}
}
p1=p3=1,p2=st[i];
while(p1<st[i]&&p2<=ed[i]){
if(cmpb(hp2[p1],bian[p2])){
hp1[p3++]=hp2[p1++];
}
else{
hp1[p3++]=bian[p2++];
}
}
while(p1<st[i]){
hp1[p3++]=hp2[p1++];
}
while(p2<=ed[i]){
hp1[p3++]=bian[p2++];
}
for(int j=1;j<p3;j++){
hp2[j]=hp1[j];
}
}
for(int i=1;i<=q;i++){
puts(ans[i]?"Yes":"No");
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號