BZOJ-1095: [ZJOI2007]Hide 捉迷藏

[文章目录]

Description

某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的距离。 N ≤100000, M ≤500000

动态点分治
维护每一块可行点到上一层的fa的距离的最大值,以及(每个儿子的块中可行点到自己的最大距离【每个不同儿子维护一个】)的最大值和次大值的和。
那么答案就是所有节点的两个不同儿子到自己的最大值的和(最大+次大),维护所有节点的答案的最大值。
以上用2n+1个可删除堆维护即可。
P.S.一定要封装,维护堆、删除堆、最大+次大

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
const int inf=0x3f3f3f3f;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char f=0,ch=nc();
    while(!isdigit(ch)) f|=(ch=='-'),ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return f?-re:re;
}
inline char s_read() {char re=nc(); while(re!='C'&&re!='G') re=nc(); return re;}
inline int Min(int x,int y){return x<y ? x:y;}
inline int Max(int x,int y){return x>y ? x:y;}
//********************************************************************
int n,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int tot,pos[N],dep[N],lca[N<<1][20],Log[N<<1],bin[20];
void dfs(int x,int pre)
{
    dep[x]=dep[pre]+1; pos[x]=++tot; lca[tot][0]=dep[x];
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
        dfs(to[i],x),lca[++tot][0]=dep[x];
}
inline int dis(int x,int y)
{
    if(pos[x]>pos[y]) swap(x,y);
    int lo=Log[pos[y]-pos[x]+1];
    return dep[x]+dep[y]-(Min(lca[pos[x]][lo],lca[pos[y]-bin[lo]+1][lo])<<1);
}
//********************************************************************
int nn,rot,root,fa[N],msi[N],siz[N],ran[N],now1[N],now2[N];
bool vis[N],ope[N];
struct heap
{
    priority_queue<int>he,del;
    void rush(){while(!del.empty()&&del.top()==he.top()) del.pop(),he.pop();}
    void push(int x){he.push(x);}
    void era(int x){del.push(x);}
    int siz(){return he.size()-del.size();}
    int top(){rush(); return (siz()==0) ? -1 : he.top();}
    int sec()
    {
        if(siz()<=1) return siz()-1;
        rush(); int t=he.top(); he.pop();
        rush(); int re=t+he.top(); he.push(t);
        return re;
    }
}h1[N],h2[N],ans;//h1:当前联通子图到父亲的长度集合 h2:儿子h1的top()集合+当前点 ans:h2的sec()集合
void getroot(int x,int pre)
{
    siz[x]=1; msi[x]=0;
    for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
        getroot(to[i],x),msi[x]=Max(msi[x],siz[to[i]]),siz[x]+=siz[to[i]];
    msi[x]=Max(msi[x],nn-siz[x]);
    if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre)
{
    ran[++tot]=x,siz[x]=1;
    for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
        Dfs(to[i],x),siz[x]+=siz[to[i]];
}
void build(int x,int pre)
{
    fa[x]=pre; tot=0; Dfs(x,pre); vis[x]=1;
    if(pre) for(int i=1;i<=tot;++i) h1[x].push(dis(pre,ran[i]));
    now1[x]=h1[x].top(); int p;
    for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
    {
        root=0,nn=siz[to[i]],getroot(to[i],x);
        build(p=root,x); if(now1[p]!=-1) h2[x].push(now1[p]);
    }
    h2[x].push(0); now2[x]=h2[x].sec(); ans.push(now2[x]);
}
//********************************************************************
void Del(int x)
{
    h2[x].era(0);
    if(h2[x].sec()!=now2[x])
    {
        ans.era(now2[x]);
        ans.push(now2[x]=h2[x].sec());
    }
    for(int p=x;p;p=fa[p]) if(fa[p])
    {
        h1[p].era(dis(fa[p],x));
        if(h1[p].siz()==0||h1[p].top()!=now1[p])
        {
            if(now1[p]!=-1) h2[fa[p]].era(now1[p]);
            if(h1[p].siz()==0) now1[p]=-1;
            else h2[fa[p]].push(now1[p]=h1[p].top());
            if(h2[fa[p]].sec()!=now2[fa[p]])
            {
                ans.era(now2[fa[p]]);
                ans.push(now2[fa[p]]=h2[fa[p]].sec());
            }
        }
    }
}
void Insert(int x)
{
    h2[x].push(0);
    if(h2[x].sec()!=now2[x])
    {
        ans.era(now2[x]);
        ans.push(now2[x]=h2[x].sec());
    }
    for(int p=x;p;p=fa[p]) if(fa[p])
    {
        h1[p].push(dis(fa[p],x));
        if(h1[p].siz()==0||h1[p].top()!=now1[p])
        {
            if(now1[p]!=-1) h2[fa[p]].era(now1[p]);
            if(h1[p].siz()==0) now1[p]=-1;
            else h2[fa[p]].push(now1[p]=h1[p].top());
            if(h2[fa[p]].sec()!=now2[fa[p]])
            {
                ans.era(now2[fa[p]]);
                ans.push(now2[fa[p]]=h2[fa[p]].sec());
            }
        }
    }
}
int main()
{
    n=read(); int i,j;
    for(i=1;i<n;++i) add(read(),read());
    dfs(1,0);
    for(i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
    for(i=0;i<=Log[tot];++i) bin[i]=1<<i;
    for(i=1;i<=Log[tot];++i)
        for(j=1;j+bin[i]-1<=tot;++j)
            lca[j][i]=Min(lca[j][i-1],lca[j+bin[i-1]][i-1]);
    msi[0]=inf,nn=n,getroot(1,0); rot=root; build(root,0);
    int m=read(); char op;
    while(m--)
    {
        op=s_read();
        if(op=='G') printf("%d\n",ans.top());
        else
        {
            i=read();
            (ope[i]) ? Insert(i) : Del(i);
            ope[i]^=1;
        }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注