BZOJ 1095
WC2013 糖果公园

SPOJ QTREE5

HJWJBSR posted @ 2015年9月06日 23:28 in 题解 , 819 阅读

话说这博客我自己都有的时候上不去不知道是smg

题面:给n(n<=10w)个点,一开始全部都是黑色的,有(好像是)10w个操作,每次改变一个节点的颜色(黑白转换)或者询问一个点与其最近白点的距离(如果没有就是-1)

这题比QTREE4(BZOJ 1095)好写到不知道哪里去了,反正我是用了树链剖分

就是每个节点把其所有轻儿子的子树的节点的白点距离用set存起来,每次变颜色就只会改变log n个,然后弄两棵线段树存下一条重链上所有点set的顶部的值+其到链首/链尾的距离,所以也可以直接查询。

动态树分治的思路跟QTREE4差不多,只不过查询那个点到重心的距离+重心的其它子树的最小值的和的最小值,反正也是用几个set搞一下什么的,但是感觉麻烦些。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
multiset <int> a[N];
set <int> :: iterator it;
int fa[N],c[N*2][2],fi[N],sg[N],st=0,ss=1,n,m;
int h[N][3],rf[N],dep[N],tot,sum[N];bool b[N];
struct Segment_Tree
 {
 	int a[N*3];
 	void Set_up(int x,int y,int z)
 	 {
 	 	int i=x + y >> 1,j=z << 1;
 	 	a[z]=INF;
 	 	if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
 	 }
 	void Ins(int x,int y,int z,int o,int p)
 	 {
 	 	int i=x + y >> 1,j=z << 1;
 	 	if (x==y) {a[z]=p;return;}
 	 	if (o<=i) Ins(x,i,j,o,p);else
 	 	  Ins(i+1,y,j+1,o,p);
 	 	a[z]=min(a[j],a[j+1]);
 	 }
 	int Que(int x,int y,int z,int o,int p)
 	 {
 	 	int i=x + y >> 1,j=z << 1,k=INF;
 	 	if (x==o&&y==p) return a[z];
 	 	if (o<=i) k=Que(x,i,j,o,min(p,i));
 	 	if (p>i) k=min(k,Que(i+1,y,j+1,max(o,i+1),p));
 	 	return k;
 	 }
 	void Insert(int x,int y)
 	  {Ins(1,n,1,x,y);}
 	int Query(int x,int y)
 	  {return Que(1,n,1,x,y);}
 } mi[2];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 }
void DFS(int x)
 {
 	h[x][0]=h[fa[x]][0]+1;sum[x]=1;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x])
 	   fa[c[i][0]]=x,DFS(c[i][0]),sum[x]+=sum[c[i][0]];
 	return;
 }
int DSF(int x,int y)
 {
 	int k=0;sg[x]=++st;
 	rf[x]=y;h[x][1]=h[x][0]-h[y][0];
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x]&&sum[c[i][0]]>sum[k])
 	   k=c[i][0];
 	dep[x]=!k?x:DSF(k,y);
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x]&&c[i][0]!=k)
 	   DSF(c[i][0],c[i][0]);
 	h[x][2]=h[dep[x]][0]-h[x][0];
 	return dep[x];
 }
void Insert(int x)
 {
 	int s=0;
 	while (x)
 	 {
 	 	it=a[x].begin();
 	 	int k=it==a[x].end()?INF:*it;
 	 	a[x].insert(s);
 	 	if (s<k)
 	 	  mi[0].Insert(sg[x],s+h[x][1]),
 	 	  mi[1].Insert(sg[x],s+h[x][2]);
 	 	s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
 	 }
 }
void Delete(int x)
 {
 	int s=0;
 	while (x)
 	 {
 	 	it=a[x].begin();int k=*it;
 	 	it=a[x].lower_bound(s);a[x].erase(it);
 	 	it=a[x].begin();int l=it==a[x].end()?INF:*it;
 	 	if (k!=l)
 	 	  mi[0].Insert(sg[x],l==INF?INF:l+h[x][1]),
 	 	  mi[1].Insert(sg[x],l==INF?INF:l+h[x][2]);
 	 	s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
 	 }
 }
int Query(int x)
 {
 	int s=0,ans=INF;
 	while (x)
 	 {
 	 	ans=min(ans,s+mi[0].Query(sg[x],sg[dep[x]])
 	 	  -h[x][0]+h[rf[x]][0]);
 	 	ans=min(ans,s+mi[1].Query(sg[rf[x]],sg[x])
 	 	  -h[dep[x]][0]+h[x][0]);
 	 	s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
 	 }
 	return ans;
 }
int main()
 {
 	n=Read();
 	for (int i=1;i<n;i++) Line(Read(),Read());
 	DFS(1);DSF(1,1);
    mi[0].Set_up(1,n,1);mi[1].Set_up(1,n,1);
    m=Read();
    while (m--)
     if (!Read())
      {
      	 int k=Read();b[k]=!b[k];
      	 if (!b[k]) Delete(k),tot--;else Insert(k),tot++;
      } else
      {
      	 int k=Read();
      	 printf("%d\n",tot?Query(k):-1);
      }
    return 0;
 }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter