P5163 WD与地图（整体二分+权值线段树）

た入场券 2022-01-12 09:29 216阅读 0赞

[传送门][Link 1]

细节要人命.jpg

这题思路太新奇了……首先不难发现可以倒着做变成加边，但是它还需要我们资瓷加边的同时维护强连通分量。显然加边之后暴力跑是不行的

然后有一个想法，对于一条边\\((u,v)\\)，如果所有加入时间在\\((0,t)\\)之间的边能够使\\(u,v\\)在同一个强连通分量里，那么\\((u,v)\\)这条边的成立时间就是最小的满足条件的\\(t\\)。

对于每一个强联通分量维护一棵权值线段树，修改的话就是一个权值出现次数\\(+1\\)，另一个\\(-1\\)，找前\\(k\\)大的总和可以类似于主席树的那种二分，强联通分量的合并可以线段树合并。

于是就可以枚举时间\\(t\\)，对于每一条成立时间为\\(t\\)的边\\((u,v)\\)，我们用并查集把它们连起来，再把他们对应的强连通分量的权值线段树合并起来，这样就查询和修改就直接在权值线段树上进行即可

现在的问题是如何求出每条边的成立时间。这个可以整体二分。每次二分一个\\(mid\\)，把所有加入时间小于等于\\(mid\\)的边加入图中跑一遍\\(tarjan\\)，就可以知道哪些边的成立时间小于等于\\(mid\\)，然后继续二分下去就好了。然后可以用一个什么东西来维护当前并查集的情况，这样左边做完之后就不用再做一次，可以直接进右边做了

注意细节

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define ll long long
    #define pi pair<int,int>
    #define IT vector<pi>::iterator
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    #define gg(mp) for(IT it=mp.begin();it!=mp.end();++it)
    template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
    template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    char sr[1<<21],z[20];int C=-1,Z=0;
    inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
    void print(R ll x){
        if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
        while(z[++Z]=x%10+48,x/=10);
        while(sr[++C]=z[Z],--Z);sr[++C]='\n';
    }
    const int N=1e6+5;
    struct eg{int v,nx;}e[N];int head[N],tot;
    struct node{int u,v,t;}a[N],b[N];vector<node>path[N];
    struct point{int ls,rs,s;ll sum;}t[N<<5];ll ans[N];set<pi>s;
    int fa[N],rt[N],low[N],dfn[N],st[N],ins[N],q[N],type[N],aa[N],bb[N],val[N];
    int n,m,tim,qaq,top,cnt,h,u,v,lim;
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void unite(R int x,R int y){
        x=find(x),y=find(y);if(x==y)return;
        fa[x]=y;
    }
    void tarjan(int u){
        dfn[u]=low[u]=++tim,st[++top]=u,ins[u]=1;
        go(u)if(!dfn[v])tarjan(v),cmin(low[u],low[v]);
        else if(ins[v])cmin(low[u],dfn[v]);
        if(low[u]==dfn[u])do{ins[st[top]]=0,unite(st[top],u);}while(st[top--]!=u);
    }
    void update(int &p,int l,int r,int k,int x){
    //  printf("%d %d\n",l,r);
        if(!p)p=++cnt;t[p].s+=k,t[p].sum+=x*k;if(l==r)return;
        int mid=(l+r)>>1;
        x<=mid?update(t[p].ls,l,mid,k,x):update(t[p].rs,mid+1,r,k,x);
    }
    ll query(int p,int l,int r,int k){
        if(k>=t[p].s)return t[p].sum;
        if(l==r)return t[p].sum/t[p].s*k;
        int mid=(l+r)>>1;
        if(t[t[p].rs].s>=k)return query(t[p].rs,mid+1,r,k);
        return query(t[p].ls,l,mid,k-t[t[p].rs].s)+t[t[p].rs].sum;
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        t[x].s+=t[y].s,t[x].sum+=t[y].sum;
        t[x].ls=merge(t[x].ls,t[y].ls);
        t[x].rs=merge(t[x].rs,t[y].rs);
        return x;
    }
    void solve(int l,int r,int ql,int qr){
    //  printf("%d %d %d %d\n",l,r,ql,qr);
        if(l==r){
            fp(i,ql,qr)path[l].push_back(a[i]);
            return;
        }if(ql==qr){
            if(find(a[ql].u)==find(a[ql].v))
                path[a[ql].t].push_back(a[ql]);
            return;
        }int mid=(l+r)>>1;tot=h=0;
        fp(i,ql,qr)if(a[i].t<=mid){
            int u=find(a[i].u),v=find(a[i].v);
            q[++h]=u,q[++h]=v,head[u]=head[v]=0;
        }for(R int i=1;i<=h;i+=2){
            int u=q[i],v=q[i+1];
            e[++tot]={v,head[u]},head[u]=tot;
            dfn[u]=low[u]=ins[u]=0;
            dfn[v]=low[v]=ins[v]=0;
        }top=tim=0;
        fp(i,1,h)if(!dfn[q[i]])tarjan(q[i]);
        vector<pi>mp;int t1=0,t2=ql;
        h=1;
        fp(i,ql,qr){
            int flag=0;
            if(a[i].t<=mid){
                int u=q[h],v=q[h+1];h+=2;
                if(find(u)==find(v))flag=1;
                mp.push_back(pi(u,fa[u]));
                mp.push_back(pi(v,fa[v]));
            }if(flag)a[t2++]=a[i];
            else b[++t1]=a[i];
        }fp(i,t2,qr)a[i]=b[i-t2+1];
        fp(i,1,h-1)fa[q[i]]=q[i];
    //  printf("%d %d\n",t1,t2);
        if(ql<t2)solve(l,mid,ql,t2-1);
        gg(mp)fa[it->first]=it->second;
        if(qr>=t2)solve(mid+1,r,t2,qr);
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
    //  freopen("testdata.out","w",stdout);
        n=read(),m=read(),qaq=read();
        fp(i,1,n)val[i]=read(),fa[i]=i;
        fp(i,1,m)u=read(),v=read(),s.insert(pi(u,v));
        fd(i,qaq,1){
            int op=read(),u=read(),v=read();
            type[i]=op,aa[i]=u,bb[i]=v;
            if(op==1)a[++tot]={u,v,i},s.erase(pi(u,v));
            else if(op==2)val[u]+=v;
        }for(set<pi>::iterator it=s.begin();it!=s.end();++it)a[++tot]={it->first,it->second,0};
        solve(0,qaq+1,1,m);
        tot=top=0,type[0]=1;
        fp(i,1,n)cmax(lim,val[i]),fa[i]=i;
        fp(i,1,n)update(rt[i],1,lim,1,val[i]);
    //  puts("QAQ");
        fp(i,0,qaq)if(type[i]==1){
            for(vector<node>::iterator it=path[i].begin();it!=path[i].end();++it){
                it->u=find(it->u),it->v=find(it->v);
                if(it->u==it->v)continue;
                fa[it->v]=it->u;
                rt[it->u]=merge(rt[it->u],rt[it->v]);
            }
        }else if(type[i]==2){
            int u=find(aa[i]);update(rt[u],1,lim,-1,val[aa[i]]);
            val[aa[i]]-=bb[i];update(rt[u],1,lim,1,val[aa[i]]);
        }else ans[++top]=query(rt[find(aa[i])],1,lim,bb[i]);
        while(top)print(ans[top--]);
        return Ot(),0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10208483.html

[Link 1]: https://www.luogu.org/problemnew/show/P5163