首页 > 其他 > 详细

CF1109F Sasha and Algorithm of Silence's Sounds

时间:2019-12-05 23:27:49      阅读:82      评论:0      收藏:0      [点我收藏+]

题目
越写越短的LCT
我们可以把树转化成两个限制:
\(1.\)无环。
\(2.|E|=|V|-1\)
很显然第一个限制看上去比第二个好做,所以我们先搞第一个。
容易知道如果一段区间\([l,r]\)形成的图(我们成为生成图)如果有环,那么包含\([l,r]\)的区间的生成图一定有环。
我们要求每个左端点\(l\)求出其最大能扩展到的右端点\(r\)。由于上面的结论,这个\(r\)一定单调递增。
所以我们可以用双指针来搞。而加边删边判断有没有环则可以用LCT来搞。
这样我们就解决了第一个限制,然后来搞第二个。
我们考虑维护这样一个东西:确定了左端点\(l\)时,以\(i\)为右端点的区间的\(|V|-|E|\),记做\(f_i\)
先不管这个东西怎么维护,假如我们能够维护这个东西,那么我们查询的就是\([l,r]\)内(\(r\)为上面求的那个最大能扩展到的右端点)\(f=1\)的数量。
然后我们连边删边就是区间加。
这东西乍一看是没法做的,但是注意到由于第一个限制,我们是不会出现环的,也就是说\(|V|-|E|\ge1\),那么我们就可以只要维护区间最小值的数量了。
这东西就可以直接线段树来做了。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
namespace IO
{
    char ibuf[(1<<21)+1],*iS,*iT;
    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
}using IO::read;
const int N=2007,M=200007;
int n,m;
namespace Graph
{
    int f[N][N],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    vector<int>E[M];
    void buildG()
    {
    for(int i=1,j;i<=n;++i)for(j=1;j<=m;++j) f[i][j]=read();
    for(int i=1,j,k,x,y;i<=n;++i)
        for(j=1;j<=m;++j)
        for(k=0;k<4;++k)
        {
            x=i+dx[k],y=j+dy[k];
            if(x>=1&&x<=n&&y>=1&&y<=m) E[f[i][j]].pb(f[x][y]);
        }
    }
}using namespace Graph;
namespace LCT
{
    int fa[M],ch[M][2],rev[M];
#define lc ch[x][0]
#define rc ch[x][1]
    int nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
    void pushrev(int x){swap(lc,rc),rev[x]^=1;}
    void pushdown(int x){if(!rev[x])return ;rev[x]=0,pushrev(lc),pushrev(rc);}
    void pushall(int x){if(nroot(x))pushall(fa[x]);pushdown(x);}
    void rotate(int x)
    {
    int y=fa[x],z=fa[y],k=ch[y][1]==x;
    if(nroot(y)) ch[z][ch[z][1]==y]=x;
    fa[x]=z,fa[ch[x][!k]]=y,ch[y][k]=ch[x][!k],fa[y]=x,ch[x][!k]=y;
    }
    void splay(int x)
    {
    pushall(x);
    for(int y;nroot(x);rotate(x)) if(nroot(y=fa[x])) rotate((ch[fa[y]][0]==y)^(ch[y][0]==x)? x:y);
    }
    void access(int x){for(int y=0;x;x=fa[y=x])splay(x),rc=y;}
    void makeroot(int x){access(x),splay(x),pushrev(x);}
    int findroot(int x){access(x),splay(x);while(lc)x=lc;return splay(x),x;}
    int link(int x,int y){return makeroot(x),findroot(y)==x? 0:fa[x]=y;}
    void cut(int x,int y){makeroot(x);if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=ch[x][1]=0;}
#undef lc
#undef rc
}using namespace LCT;
namespace SegTree
{
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
    int mn[M<<2],sum[M<<2],tag[M<<2];
    void pushup(int p)
    {
    if(mn[ls]<mn[rs]) mn[p]=mn[ls],sum[p]=sum[ls];
    if(mn[rs]<mn[ls]) mn[p]=mn[rs],sum[p]=sum[rs];
    if(mn[ls]==mn[rs]) mn[p]=mn[ls],sum[p]=sum[ls]+sum[rs];
    }
    void modify(int p,int v){mn[p]+=v,tag[p]+=v;}
    void pushdown(int p){modify(ls,tag[p]),modify(rs,tag[p]),tag[p]=0;}
    void buildS(int p,int l,int r)
    {
    if(l==r) return (void)(sum[p]=1);
    buildS(ls,l,mid),buildS(rs,mid+1,r),pushup(p);
    }
    void update(int p,int l,int r,int L,int R,int x)
    {
    if(L<=l&&r<=R) return modify(p,x);
    if(tag[p]) pushdown(p);
    if(L<=mid) update(ls,l,mid,L,R,x);
    if(R>mid) update(rs,mid+1,r,L,R,x);
    pushup(p);
    }
    int query(int p,int l,int r,int L,int R)
    {
    if(L<=l&&r<=R) return mn[p]==1? sum[p]:0;
    if(tag[p]) pushdown(p);
    return (L<=mid? query(ls,l,mid,L,R):0)+(R>mid? query(rs,mid+1,r,L,R):0);
    }
#undef ls
#undef rs
#undef mid
}using namespace SegTree;
int main()
{
    ll ans=0;int l=1,r=0,S;
    n=read(),m=read(),buildG(),buildS(1,1,S=n*m);
    for(int f,c;l<=S;++l)
    {
    for(;r<S;)
    {
        f=c=0,++r;
        for(int v:E[r]) if(v<=r&&v>=l&&!link(v,r)) {f=1;break;}
        for(int v:E[r]) cut(v,r);
        if(f==1) {--r;break;}
        for(int v:E[r]) if(v<=r&&v>=l) link(v,r),++c;
        update(1,1,S,r,r,r-l+1),update(1,1,S,r,S,-c);
    }
    ans+=query(1,1,S,l,r);
    for(int v:E[l]) if(v<=r&&v>=l) cut(v,l),update(1,1,S,v,S,1);
    update(1,1,S,l,r,-1);
    }
    printf("%lld",ans);
}

CF1109F Sasha and Algorithm of Silence's Sounds

原文:https://www.cnblogs.com/cjoierShiina-Mashiro/p/11992530.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!