S+启发式合并，分治，扫描线 A. 集合操作2 并查集+set+二分，模拟即可， 代码： #include using namespace std; const int N=2e5+5; int n,m,o,a,b; int v[N],f[N],s[N]; long long t[N]; setst[N]; int find(int x){ if(f[x]==x) return x; return f[x]=find(f[x]); } int main(){ cin>>n>>m; for(int i=1;i>v[i]; f[i]=i,s[i]=1; st[i].insert(v[i]); } while(m--){ cin>>o>>a>>b; if(o==1){ int fx=find(a),fy=find(b); if(fx==fy) continue; if(s[fx]>s[fy]) swap(fx,fy); for(long long num:st[fx]) st[fy].insert(num+t[fx]-t[fy]); f[fx]=fy; s[fy]+=s[fx]; st[fx].clear(); } else if(o==2){ int fx=find(a); t[fx]+=b; } else if(o==3){ int fx=find(a); long long adj=b-t[fx]; auto it=st[fx].lower_bound(adj); if(it!=st[fx].end()) cout `#include using namespace std; const int N=2e5+5; int n,m,o,a,b; int v[N],f[N],s[N]; long long t[N]; setlong long>st[N]; int find(int x){ if(f[x]==x) return x; return f[x]=find(f[x]); } int main(){ cin>>n>>m; for(int i=1;i cin>>v[i]; f[i]=i,s[i]=1; st[i].insert(v[i]); } while(m--){ cin>>o>>a>>b; if(o==1){ int fx=find(a),fy=find(b); if(fx==fy) continue; if(s[fx]>s[fy]) swap(fx,fy); for(long long num:st[fx]) st[fy].insert(num+t[fx]-t[fy]); f[fx]=fy; s[fy]+=s[fx]; st[fx].clear(); } else if(o==2){ int fx=find(a); t[fx]+=b; } else if(o==3){ int fx=find(a); long long adj=b-t[fx]; auto it=st[fx].lower_bound(adj); if(it!=st[fx].end()) coutt[fx]'\n'; else cout"-1\n"; } } return 0; }` C++ B. 相邻点查询 并查集+每次加边维护每个点的父节点。 代码： #include using namespace std; #define int long long const int N=1e5+5,mod=998244353; int n,q,l; int fa[N],pa[N],siz[N]; vector t[N]; int find(int x) { if (fa[x]==x) return x; return fa[x]=find(fa[x]); } void dfs(int u,int f) { pa[u]=f; for (int v:t[u]) { if (v==f) continue; dfs(v,u); } } signed main(){ cin>>n>>q; for(int i=1;i>op>>a>>b; op=(op*(1+l)%mod)%2+1; a=(a*(1+l)%mod)%n+1; b=(b*(1+l)%mod)%n+1; if (op==1) { int fx=find(a),fy=find(b); if (siz[fx]>siz[fy]) swap(a,b),swap(fx,fy); siz[fy]+=siz[fx],fa[fx]=fy; t[a].push_back(b),t[b].push_back(a); dfs(a,b); } else { if (pa[a]==pa[b]&&pa[a]) l=pa[a]; else if (pa[pa[a]]==b) l=pa[a]; else if (pa[pa[b]]==a) l=pa[b]; else l=0; cout `#include using namespace std; #define int long long const int N=1e5+5,mod=998244353; int n,q,l; int fa[N],pa[N],siz[N]; vectorint> t[N]; int find(int x) { if (fa[x]==x) return x; return fa[x]=find(fa[x]); } void dfs(int u,int f) { pa[u]=f; for (int v:t[u]) { if (v==f) continue; dfs(v,u); } } signed main(){ cin>>n>>q; for(int i=1;ifa[i]=i,siz[i]=1; while (q--) { int op,a,b; cin>>op>>a>>b; op=(op*(1+l)%mod)%2+1; a=(a*(1+l)%mod)%n+1; b=(b*(1+l)%mod)%n+1; if (op==1) { int fx=find(a),fy=find(b); if (siz[fx]>siz[fy]) swap(a,b),swap(fx,fy); siz[fy]+=siz[fx],fa[fx]=fy; t[a].push_back(b),t[b].push_back(a); dfs(a,b); } else { if (pa[a]==pa[b]&&pa[a]) l=pa[a]; else if (pa[pa[a]]==b) l=pa[a]; else if (pa[pa[b]]==a) l=pa[b]; else l=0; cout } } return 0; }` C++ C. 化学反应 由题意可知， 每一个化合物对应两个瓶子， 而每个瓶子（产生反应后视为一个新瓶子）对应一个化合物。 很容易想到这就是树， 在树上lca即可。 但是也可能形成森林，所以要注意。 代码： #include using namespace std; #define int long long const int N=5e5+5; int n,m,k,idx,ans; int g[N],pos[N]; int fa[N][25],d[N]; struct node { int u,v,dep,id; }e[N]; vector t[N]; inline int read(){ int x=0; bool flag=1; char c=getchar_unlocked(); while(c'9'){ if(c=='-') flag=0; c=getchar_unlocked(); } while(c>='0'&&c=0;i--){ if(d[fa[u][i]]>=d[v]){ u=fa[u][i]; } } if(u==v) return u; for(int i=21;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } bool cmp(node a,node b) { return a.dep>b.dep||(a.dep==b.dep&&a.id=1;i--) if (!d[i]) dfs(i,0); for (int i=1;i `#include using namespace std; #define int long long const int N=5e5+5; int n,m,k,idx,ans; int g[N],pos[N]; int fa[N][25],d[N]; struct node { int u,v,dep,id; }e[N]; vectorint> t[N]; inline int read(){ int x=0; bool flag=1; char c=getchar_unlocked(); while(c'0'||c>'9'){ if(c=='-') flag=0; c=getchar_unlocked(); } while(c>='0'&&c'9'){ x=(x1)+(x3)+c-'0'; c=getchar_unlocked(); } return (flag?x:~(x-1)); } void dfs(int u,int f){ fa[u][0]=f; d[u]=d[f]+1; for(int i=1;i21;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==f) continue; dfs(v,u); } } int lca(int u,int v){ if(d[u]d[v]) swap(u,v); for(int i=21;i>=0;i--){ if(d[fa[u][i]]>=d[v]){ u=fa[u][i]; } } if(u==v) return u; for(int i=21;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } bool cmp(node a,node b) { return a.dep>b.dep||(a.dep==b.dep&&a.idb.id); } signed main(){ n=read(),m=read(),k=read(); for(int i=1;ig[i]=read(),pos[i]=i; for (int i=1;i int u,v; u=read(),v=read(); t[n+i].push_back(pos[u]); t[n+i].push_back(pos[v]); pos[v]=n+i; } for (int i=n+m;i>=1;i--) if (!d[i]) dfs(i,0); for (int i=1;i int u,v; u=read(),v=read(); int l=lca(u,v); if (!l) continue; e[++idx]={u,v,d[l],i}; } sort(e+1,e+1+idx,cmp); for (int i=1;i int sum=min(g[e[i].u],g[e[i].v]); g[e[i].u]=max(0ll,g[e[i].u]-sum); g[e[i].v]=max(0ll,g[e[i].v]-sum); ans+=sum*2; } cout return 0; }` C++ D. 三维偏序 一道可以用很多方式解决的模板题， 这里当作CDQ分治的板子： #include using namespace std; #define int long long const int N=1e5+5; const int K=2e5+5; int n,k,m,t; int res[N]; struct Element { int a,b,c,cnt,res; bool operator!=(Element other) const { return a!=other.a||b!=other.b||c!=other.c; } }e[N],ue[N]; struct BIT { int node[K]; int lowbit(int x) {return x&-x;} void add(int pos,int val) { while(pos>1; cdq(l,mid); cdq(mid+1,r); sort(ue+l,ue+mid+1,cmpB); sort(ue+mid+1,ue+r+1,cmpB); int i=l,j=mid+1; while(j>n>>k; for(int i=1;i>e[i].a>>e[i].b>>e[i].c; sort(e+1,e+n+1,cmpA); for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; const int K=2e5+5; int n,k,m,t; int res[N]; struct Element { int a,b,c,cnt,res; bool operator!=(Element other) const { return a!=other.a||b!=other.b||c!=other.c; } }e[N],ue[N]; struct BIT { int node[K]; int lowbit(int x) {return x&-x;} void add(int pos,int val) { while(posnode[pos]+=val,pos+=lowbit(pos); } int ask(int pos) { int res=0; while(pos) res+=node[pos],pos-=lowbit(pos); return res; } }bit; bool cmpA(Element x,Element y) { if(x.a!=y.a) return x.ay.a; if(x.b!=y.b) return x.by.b; return x.cy.c; } bool cmpB(Element x,Element y) { if(x.b!=y.b) return x.by.b; return x.cy.c; } void cdq(int l,int r) { if(l==r) return; int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r); sort(ue+l,ue+mid+1,cmpB); sort(ue+mid+1,ue+r+1,cmpB); int i=l,j=mid+1; while(j while(iue[i].bue[j].b) bit.add(ue[i].c,ue[i].cnt),i++; ue[j].res+=bit.ask(ue[j].c),j++; } for(int k=l;kbit.add(ue[k].c,-ue[k].cnt); } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>k; for(int i=1;i>e[i].a>>e[i].b>>e[i].c; sort(e+1,e+n+1,cmpA); for(int i=1;i t++; if(e[i]!=e[i+1]) { ue[++m]={e[i].a,e[i].b,e[i].c,t,0}; t=0; } } cdq(1,m); for(int i=1;ires[ue[i].res+ue[i].cnt-1]+=ue[i].cnt; for(int i=0;ires[i]'\n'; return 0; }` C++
启发式合并，分治，扫描线
笔记