启发式合并，分治，扫描线

用户头像 发布于 2025-08-13 49 次阅读 OI

S+启发式合并，分治，扫描线

A. 集合操作2

并查集+set+二分，模拟即可，
代码：

#include<bits/stdc++.h>
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];
set<long 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<=n;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()) cout<<*it+t[fx]<<'\n';
            else cout<<"-1\n";
        }
    }
    return 0;
}
C++

B. 相邻点查询

并查集+每次加边维护每个点的父节点。
代码：

#include <bits/stdc++.h>
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<int> 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<=n;i++) fa[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<<l<<endl;
        }
    }
    return 0;
}
C++

C. 化学反应

由题意可知，
每一个化合物对应两个瓶子，
而每个瓶子（产生反应后视为一个新瓶子）对应一个化合物。
很容易想到这就是树，
在树上lca即可。
但是也可能形成森林，所以要注意。
代码：

#include<bits/stdc++.h>
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<int> 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=(x<<1)+(x<<3)+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;i<=21;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=0;i<t[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.id<b.id);
}
signed main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) g[i]=read(),pos[i]=i;
    for (int i=1;i<=m;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<=k;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<=idx;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<<ans;
    return 0;
}
C++

D. 三维偏序

一道可以用很多方式解决的模板题，
这里当作CDQ分治的板子：

#include<bits/stdc++.h>
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<=k) node[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.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
bool cmpB(Element x,Element y) {
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.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<=r) {
        while(i<=mid&&ue[i].b<=ue[j].b)
            bit.add(ue[i].c,ue[i].cnt),i++;
        ue[j].res+=bit.ask(ue[j].c),j++;
    }
    for(int k=l;k<i;k++) bit.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<=n;i++) cin>>e[i].a>>e[i].b>>e[i].c;
    sort(e+1,e+n+1,cmpA);
    for(int i=1;i<=n;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;i<=m;i++) res[ue[i].res+ue[i].cnt-1]+=ue[i].cnt;
    for(int i=0;i<n;i++) cout<<res[i]<<'\n';
    return 0;
}
C++