BZOJ 4777 Usaco2017 Open Switch Grass Kruskal+替罪羊树+权值线段树

这道题首先可以看出答案一定是一条边，而且答案一定在最小生成树上，那么我们就可以在这个最小生成树上维护他与异色儿子的边最小值，所以我们就可以已通过Kruskal和一棵平衡树来解决，时间复杂度是O(n*logn)级别的但是那个大常数..........然后在最外面独立一棵权值线段树来存最终答案.....

证明：若答案不是一条边，那么在这个答案里一定有中间点可以推翻答案；若答案不是在最小生成树内，那么在最小生成树上一定用答案可以更新他（这个答案边与最小生成树内这两个点的路径形成回路，那么他一定会被推翻）（最小生成树外的边与最小生成树形成回路，那个路径一定比回路内其它边大（或等），会被其它边替代）

一定要注意当查询时替罪羊的中间点可以生效时当且仅当，他在区间内并且他存在。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<queue>

#include<algorithm>

#define MAXN 200005

#define Inf 1000000

using namespace std;

double alpha=0.756;

inline int read()

{

    int sum=;

    char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')

    {

        sum=(sum<<)+(sum<<)+ch-;

        ch=getchar();

    }

    return sum;

}

int sz;

struct Seg_Tree

{

    Seg_Tree *ch[];

    int l,r,mid,size;

}node[Inf<<],*seg;

inline Seg_Tree *New(int l,int r)

{

    Seg_Tree *p=&node[++sz];

    p->l=l;

    p->r=r;

    p->mid=(l+r)>>;

    p->size=;

    return p;

}

inline int Min(int x,int y)

{

    return x<y?x:y;

}

struct ScapeGoat_Tree

{

    ScapeGoat_Tree *ch[],*f;

    int key,size,col,ex,cover,min;

    void pushup()

    {

        size=ch[]->size+ex+ch[]->size;

        cover=ch[]->cover++ch[]->cover;

        min=Min(ch[]->min,ch[]->min);

        if(ex)min=Min(key,min);

    }

    bool bad()

    {

        return cover*alpha+<ch[]->cover||cover*alpha+<ch[]->size;

    }

}mempool[MAXN<<],*list[MAXN<<],*stack[MAXN<<],*null,*root[MAXN],*pos[MAXN];

int len,top;

inline void pre()

{

   null=mempool;

   for(int i=;i<(MAXN<<);i++)stack[++top]=mempool+i;

   null->ch[]=null->ch[]=null->f=null;

   null->key=null->min=0x7fffffff;

   for(int i=;i<MAXN;i++)root[i]=null;

}

inline ScapeGoat_Tree *New(int key,ScapeGoat_Tree *fa,int co)

{

    ScapeGoat_Tree *p=stack[top--];

    p->ch[]=p->ch[]=null;

    p->min=p->key=key;

    p->f=fa;

    p->col=co;

    p->size=p->cover=p->ex=;

    return p;

}

struct Tr

{

    int to,next,w;

}C[MAXN<<];

int Head[MAXN],T;

inline void Add(int x,int y,int z)

{

    C[++T].to=y;

    C[T].next=Head[x];

    Head[x]=T;

    C[T].w=z;

}

int col[MAXN],Ans[MAXN];

struct E

{

    int x,y,z;

}e[MAXN];

int n,m,k,q;

int Fa[MAXN];

int comp(const E a,const E b)

{

    return a.z<b.z;

}

int f[MAXN];

int find(int x)

{

    return Fa[x]==x?x:(Fa[x]=find(Fa[x]));

}

inline void unit(int x,int y)

{

    if(x!=y)Fa[x]=y;

}

inline void Kruskal()

{

   sort(e+,e+m+,comp);

   for(int i=;i<=n;i++)

    Fa[i]=i;

   int had=;

   for(int i=;i<=m;i++)

    if(find(e[i].x)!=find(e[i].y))

    {

        Add(e[i].x,e[i].y,e[i].z);

        Add(e[i].y,e[i].x,e[i].z);

        unit(find(e[i].x),find(e[i].y));

        had++;

        if(had==n)break;

    }

}

ScapeGoat_Tree **insert(int key,int co,ScapeGoat_Tree *&p,int id,ScapeGoat_Tree *fa)

{

    if(p==null)

    {

        p=New(key,fa,co);

        pos[id]=p;

        return &null;

    }

    ScapeGoat_Tree **ret=insert(key,co,p->ch[p->col<=co],id,p);

    if(p->bad())ret=&p;

    p->pushup();

    return ret;

}

void travel(ScapeGoat_Tree *p)

{

    if(p==null)return;

    travel(p->ch[]);

    if(p->ex)list[++len]=p;

    else stack[++top]=p;

    travel(p->ch[]);

}

ScapeGoat_Tree *divide(int l,int r,ScapeGoat_Tree *fa)

{

    if(l>r)return null;

    int mid=(l+r)>>;

    list[mid]->ch[]=divide(l,mid-,list[mid]);

    list[mid]->ch[]=divide(mid+,r,list[mid]);

    list[mid]->f=fa;

    list[mid]->pushup();

    return list[mid];

}

inline void rebuild(ScapeGoat_Tree *&p)

{

    len=;

    ScapeGoat_Tree *fa=p->f;

    travel(p);

    p=divide(,len,fa);

}

inline void Insert(int key,int co,ScapeGoat_Tree *&Root,int id)

{

    ScapeGoat_Tree **p=insert(key,co,Root,id,null);

    if(*p!=null)rebuild(*p);

}

void dfs(int x)

{

    for(int i=Head[x];i;i=C[i].next)

    if(C[i].to!=f[x])

    {

      f[C[i].to]=x;

      Insert(C[i].w,col[C[i].to],root[x],C[i].to);

      dfs(C[i].to);

    }

}

void build(Seg_Tree *p)

{

    if(p->l==p->r)return;

    p->ch[]=New(p->l,p->mid);

    p->ch[]=New(p->mid+,p->r);

    build(p->ch[]);

    build(p->ch[]);

}

inline int Rank(int co,ScapeGoat_Tree *Root)

{

    ScapeGoat_Tree *p=Root;

    int ret=;

    while(p!=null)

     if(p->col>=co)

      p=p->ch[];

     else

      ret+=p->ch[]->size+p->ex,p=p->ch[];

    return ret;

}

int query(ScapeGoat_Tree *p,int l,int r)

{

    if(l>r)return 0x7fffffff;

    if(p==null)return 0x7fffffff;

    if(l<=&&r>=p->size)

     return p->min;

    int ans=0x7fffffff;

    if(p->ex&&l<=p->ch[]->size+p->ex&&r>=p->ch[]->size+p->ex)

     ans=p->key;

    if(l<=p->ch[]->size)

     ans=Min(ans,query(p->ch[],l,r));

    if(r>p->ch[]->size+p->ex)

     ans=Min(ans,query(p->ch[],l-(p->ch[]->size+p->ex),r-(p->ch[]->size+p->ex)));

    return ans;

}

inline int Query(int x)

{

    int l=Rank(col[x],root[x]);

    int ans=query(root[x],,l);

    int r=Rank(col[x]+,root[x])+;

    ans=Min(ans,query(root[x],r,root[x]->size));

    return ans;

}

void update(Seg_Tree *p,int key)

{

    if(key>Inf)return;

    p->size++;

    if(p->l==p->r)return;

    update(p->ch[p->mid<key],key);

}

inline void Init()

{

    n=read(),m=read(),k=read(),q=read();

    for(int i=;i<=m;i++)

        e[i].x=read(),e[i].y=read(),e[i].z=read();

    Kruskal();

    for(int i=;i<=n;i++)col[i]=read();

    dfs();

    seg=New(,Inf);

    build(seg);

    for(int i=;i<=n;i++)

     update(seg,(Ans[i]=Query(i)));

}

inline void Del(int x)

{

    pos[x]->ex=;

    ScapeGoat_Tree *p=pos[x];

    while(p!=null)

     p->pushup(),p=p->f;

}

void del(Seg_Tree *p,int key)

{

    if(key>Inf)return;

    p->size--;

    if(p->l==p->r)return;

    del(p->ch[p->mid<key],key);

}

int get_ans(Seg_Tree *p)

{

    if(p->l==p->r)return p->mid;

    if(p->ch[]->size)return get_ans(p->ch[]);

    else return get_ans(p->ch[]);

}

inline void work()

{

  while(q--)

  {

     int x=read(),y=read();

     if(x!=)Del(x);

     if(x!=)if(root[f[x]]->bad())rebuild(root[f[x]]);

     col[x]=y;

     if(x!=)Insert(pos[x]->key,y,root[f[x]],x);

     del(seg,Ans[x]);

     if(x!=)del(seg,Ans[f[x]]);

     update(seg,(Ans[x]=Query(x)));

     if(x!=)update(seg,(Ans[f[x]]=Query(f[x])));

     printf("%d\n",get_ans(seg));

  }

}

int main()

{

  pre();

  Init();

  work();

  return ;

}