bzoj 3991 寻宝游戏

题目大意：

一颗树有一个点的集合

对于每个集合的答案为从集合内一个点遍历集合内所有点再返回的距离最小值

每次可以选择一个点若在集合外便加入集合若在集合内就删除

求每次操作后这个集合的答案

思路：

对于每个集合

它的答案一定为从dfs序最小的开始依次遍历再回来

当加入一个点x的时候可以找到它dfs序的前驱与后继画图可得 ans+=dis(pre,x)+dis(x,sub)-dis(pre,sub) 删除的时候为ans-=

特别地当x没有前驱或后继时前驱为最大值后继为最小值（当做一个环

因此我们维护一颗平衡树搞一下即可

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #define inf 2139062143

 #define ll long long

 #define MAXN 100100

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int ch[MAXN][],fa[MAXN],sz,cnt[MAXN],val[MAXN],size[MAXN],rt;

 int which(int x) {return x==ch[fa[x]][];}

 int find_pre()

 {

     int pos=ch[rt][];

     while(ch[pos][]) pos=ch[pos][];

     return pos;

 }

 int find_max()

 {

     int pos=ch[rt][];

     while(ch[pos][]) pos=ch[pos][];

     return pos;

 }

 int find_min()

 {

     int pos=ch[rt][];

     while(ch[pos][]) pos=ch[pos][];

     return pos;

 }

 int find_sub()

 {

     int pos=ch[rt][];

     while(ch[pos][]) pos=ch[pos][];

     return pos;

 }

 void upd(int x)

 {

     if(!x) return ;

     size[x]=cnt[x]+size[ch[x][]]+size[ch[x][]];

 }

 void rotate(int pos)

 {

     int f=fa[pos],ff=fa[f],k=which(pos);

     ch[f][k]=ch[pos][k^],fa[ch[f][k]]=f,fa[f]=pos,ch[pos][k^]=f,fa[pos]=ff;

     if(ff) ch[ff][ch[ff][]==f]=pos;

     upd(f);upd(pos);

 }

 void splay(int x)

 {

     for(int f;f=fa[x];rotate(x))

         if(fa[f]) rotate((which(x)==which(f)?f:x));

     rt=x;

 }

 void Insert(int x)

 {

     int pos=rt,f=;

     while()

     {

         if(val[pos]==x) {cnt[pos]++,upd(pos);upd(f);splay(pos);return ;}

         f=pos,pos=ch[pos][x>val[pos]];

         if(!pos)

         {

             ch[++sz][]=ch[sz][]=,fa[sz]=f,val[sz]=x,cnt[sz]=size[sz]=,ch[f][x>val[f]]=sz;

             upd(f);splay(sz);return ;

         }

     }

 }

 void insert(int x)

 {

     if(!rt) {val[++sz]=x,ch[sz][]=ch[sz][]=fa[sz]=,cnt[sz]=size[sz]=,rt=sz;return;}

     Insert(x);

 }

 int find_rank(int x)

 {

     int res=,pos=rt;

     while()

     {

         if(x<val[pos]) pos=ch[pos][];

         else

         {

             res+=size[ch[pos][]];

             if(val[pos]==x) {splay(pos);return res+;}

             res+=cnt[pos],pos=ch[pos][];

         }

     }

 }

 void dlt(int x)

 {

     if(cnt[rt]>) {cnt[rt]--;return ;}

     if(!ch[rt][]&&!ch[rt][]) {rt=;return ;}

     if(!ch[rt][]||!ch[rt][])

     {

         int k=!ch[rt][]?:;

         rt=ch[rt][k],fa[rt]=;

         return ;

     }

     int k=find_pre(),tmp=rt;

     splay(k);fa[ch[tmp][]]=rt;

     ch[rt][]=ch[tmp][],rt=k;

 }

 int n,m,nxt[MAXN<<],fst[MAXN],to[MAXN<<],Val[MAXN<<],Cnt;

 int f[MAXN][],dep[MAXN],s[MAXN],k[MAXN],tot,hsh[MAXN],HSH[MAXN],vis[MAXN];

 ll ans,dis[MAXN];

 void add(int u,int v,int w) {nxt[++Cnt]=fst[u],fst[u]=Cnt,to[Cnt]=v,Val[Cnt]=w;}

 void dfs(int x)

 {

     for(int i=;(<<i)<=dep[x];i++) f[x][i]=f[f[x][i-]][i-];

     hsh[x]=++tot,HSH[tot]=x;

     for(int i=fst[x];i;i=nxt[i])

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

         {

             dis[to[i]]=dis[x]+Val[i],dep[to[i]]=dep[x]+;

             f[to[i]][]=x;dfs(to[i]);

         }

 }

 int lca(int u,int v)

 {

     int t;

     if(dep[u]<dep[v]) swap(u,v);

     t=dep[u]-dep[v];

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

         if((<<i)&t) u=f[u][i];

     if(u==v) return u;

     for(int i=;i>=;i--)

         if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];

     return f[u][];

 }

 inline ll calc(int u,int v) {return dis[HSH[u]]+dis[HSH[v]]-(dis[lca(HSH[u],HSH[v])]<<);}

 int main()

 {

     n=read(),m=read();int a,b,c;

     for(int i=;i<n;i++) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);}

     dfs();

     while(m--)

     {

         c=hsh[read()],vis[c]^=;

         if(vis[c])

         {

             if(!rt) {puts("");insert(c);continue;}insert(c);

             a=val[find_pre()],b=val[find_sub()];

             if(!a) a=val[find_max()];if(!b) b=val[find_min()];

             if(!a) a=val[rt];if(!b) b=val[rt];

             ans+=calc(a,c)+calc(b,c)-calc(a,b);

         }

         else

         {

             a=find_rank(c);

             a=val[find_pre()],b=val[find_sub()];

             if(!a) a=val[find_max()];if(!b) b=val[find_min()];

             if(!a) a=val[rt];if(!b) b=val[rt];

             ans-=calc(a,c)+calc(b,c)-calc(a,b);

             dlt(c);

         }

         printf("%lld\n",ans);

     }

 }

巴特西

bzoj 3991 寻宝游戏

最新文章

热门文章