P4219

Aryper · 2021-08-20 17:46:30 · 个人记录

[BJOI2014]大融合

线段树传参写错，痛。。。

既然题目说要动态回答，那就一定要离线。

先把整棵树建好后，我们进行树链剖分，每个节点存储其子树（还未进行加边操作的）大小。

然后我们每次加边，用并查集将两点合并，接着将深度较浅的点到其连通块根节点的路径的所有子树大小权值加上深度较深的点的子树大小，维护信息的正确性。

查询的时候就是子树大小的乘积，比较好写。

然后这里所有动态子树大小都是通过线段树上查询的，我当然知道线段树可以改成树状数组，而且效率会更高。但是刚想到树状数组的时候线段树就写完了。。。

至于 LCT，咕咕咕。

时间复杂度 O(q\log^2n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,q,ans,cnt,tot;

ll ver[N*2+5],nxt[N*2+5],head[N+5],fath[N+5];

ll dt[N+5],fa[N+5],size[N+5],hs[N+5],id[N+5],top[N+5];

struct node{
    ll u,v;char op;
}a[N+5];

struct sgt{
    ll l,r,laz;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define laz(x) tree[x].laz
}tree[N*4+5];

ll find(ll x) {
    if(x==fath[x]) return x;
    return fath[x]=find(fath[x]);
}

void uni(ll x,ll y) {
    fath[find(x)]=find(y);
}

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) {laz(p)=1;return;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}

void spread(ll p) {
    if(laz(p)) {
        laz(p*2)+=laz(p);laz(p*2+1)+=laz(p);laz(p)=0;
    }
}

void chg(ll p,ll l,ll r,ll k) {
    if(l<=l(p)&&r>=r(p)) {laz(p)+=k;return;}
    spread(p);
    ll mid=(l(p)+r(p))>>1;
    if(l<=mid) chg(p*2,l,r,k);
    if(r>mid) chg(p*2+1,l,r,k);
}

ll siz(ll p,ll x) {
    if(l(p)==r(p)) return laz(p);
    spread(p);
    ll mid=(l(p)+r(p))>>1;
    if(x<=mid) return siz(p*2,x);
    else return siz(p*2+1,x);
}

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;fa[p]=fath;size[p]=1;
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath) continue;
        dfs(ver[i],p);size[p]+=size[ver[i]];
        if(size[ver[i]]>size[hs[p]]) hs[p]=ver[i];
    }
}

void _dfs(ll p,ll topf) {
    id[p]=++cnt;top[p]=topf;
    if(!hs[p]) return;
    _dfs(hs[p],topf);
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fa[p]||ver[i]==hs[p]) continue;
        _dfs(ver[i],ver[i]);
    }
}

void chgpath(ll x,ll y,ll k) {
    while(top[x]!=top[y]) {
        if(dt[top[x]]<dt[top[y]]) swap(x,y);
        chg(1,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dt[x]>dt[y]) swap(x,y);
    chg(1,id[x],id[y],k);
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();q=read();

    for(ll i=1;i<=q;i++) {
        cin>>a[i].op;a[i].u=read();a[i].v=read();
        if(a[i].op=='A') {
            add(a[i].u,a[i].v);add(a[i].v,a[i].u);
        }
    }

    for(ll i=1;i<=n;i++) {
        fath[i]=i;
        if(!top[i]) {
            dfs(i,0);_dfs(i,i);
        }
    }

    build(1,1,n);

    for(ll i=1;i<=q;i++) {
        if(a[i].op=='A') {
            if(dt[a[i].u]>dt[a[i].v]) {
                chgpath(a[i].v,find(a[i].v),siz(1,id[a[i].u]));
                uni(a[i].u,a[i].v);
            }
            else {
                chgpath(a[i].u,find(a[i].u),siz(1,id[a[i].v]));
                uni(a[i].v,a[i].u);
            }
        }
        if(a[i].op=='Q') {
            if(dt[a[i].u]>dt[a[i].v]) {
                ans=siz(1,id[a[i].u])*(siz(1,id[find(a[i].v)])-siz(1,id[a[i].u]));
                write(ans);putchar('\n');
            }
            else {
                ans=siz(1,id[a[i].v])*(siz(1,id[find(a[i].u)])-siz(1,id[a[i].v]));
                write(ans);putchar('\n');
            }
        }
    }

    return 0;
}