over 3 years ago

之前觉得好难的题……搞了快一天终于过了

orz vfk的题解
orz sillycross的解题报告
orz drcrow的论文。。不过没看懂=_=
hzwer的代码让我彻底理解了这道题whttp://logdown.com/account/posts/252282-bzoj3052-wc2013-trees-dont-candy-park/edit#add-category
对于这个问题,因为修改和查询并存,用数据结构维护目前我没找到好的做法,所以考虑分块。

树的分块

先设block=sqrt(n)
一种是普通块状树的分块,按照dfs序按遍历的顺序,往块里一个个加结点,到达block之后开新块。这样子的话会分出严格block的块和树的枝叶上不到block的块。但是相邻的块在树上的位置不一定连续。
另一种方法是bzoj1086的分块方式。题目已经说得很清楚了。分块的结果是可以分出[block,3*block]的块。这些块内的结点可能并不连通,但是在最坏情况下他们可以仅通过一个公共父亲连通。 这样子分块的话保证相邻的块在树上的位置是挨着的。

关于莫队

因为莫队是针对不修改的离线做法,但是这里出现了修改。所以有了两种做法
1、依旧按照分的块对询问排序,并且记录每个块的时间。在每次回答询问之前进行时光前进或者时光倒流。
维护can数组,can[i]表示i这个点是否在上次的询问(记为prex,prey)的这条路径上。
对于时光流转,只需要改变某个点上的颜色,前进就是正着改,后退就是改成之前的。每次改的时候,如果在路径上,就更新答案,如果不在就直接修改。
对于点的转换。对于(prex,x)这条路径上的点,除了lca(prex,x)不修改以外,剩下的点全部取反即可。所以抛去lca(prex,x)这个特殊点,路径上维护剩下的点,查询的时候把lca(prex,x)插入就好了。关于取反如果有疑问,详见vfkblog的证明。
假设block是块的大小,bn是块的个数。对于每个点的转换,如果在块内的话,复杂度为O(block*q);如果不在块内,因为已经排好序了,所以会执行O(bn*bn),每次复杂度为(n+n+q) ,总计为(bn*bn*q)
所以设block=n^(2/3),这样总的复杂度就变成了O(n^(5/3))
为了减少常数,可以让每个查询变成编号小的块->编号大的块。
因为在某种程度上还是两个块越接近越好,所以第二种分块方式会更好。
2、枚举两个块,遍历整个时间轴,不断地修改修改并回答查询。
这是sillycross的做法。同样假设block是块的大小,bn是块的个数。枚举+遍历时间轴的复杂度为O(bn^2*q),修改点的位置的复杂度为O(block*q)。为了使得总的复杂度最小同样取block=n^(2/3)
写的时候也是因为自己的失误坑了一会。。
wa点:
1、尽可能参加运算的数越小越好
2、记录的precolor只是之前一个的color而已。。

#include<cstdio>
#include<cstring>
#include<algorithm> 
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=1000001,maxm=2000001,base=16;
struct node1{int x,y,t,id;} query[maxn];
struct node2{int x,y,pre;} revise[maxn];
int n,m,widen=0,q,block,bn=0,rn=0,qn=0,top=0;
bool can[maxn];
int value[maxn],c[maxn],pre[maxn],b[maxn]; 
int next[maxm],point[maxn],v[maxm];
LL ans=0,a[maxn],w[maxn];
int tot=0,dfn[maxn];
int fa[maxn][base+1],tim[maxn],dep[maxn],now[maxn],stack[maxn];
inline int read()
{
     char c=getchar();int bj=1,result=0;
     while (c!='-'&&!(c<='9'&&c>='0'))  c=getchar();
     if (c=='-') bj=-1,c=getchar();
     while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
     return result*bj;
}
inline void addedge(int x,int y)
{
     widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
     widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;
}
inline bool cmp(const node1 p,const node1 q)
{
     if (b[p.x]==b[q.x]&&b[p.y]==b[q.y]) return p.t<q.t;
          else if (b[p.x]==b[q.x])return b[p.y]<b[q.y];
               else return b[p.x]<b[q.x];
}
inline int dfs(int now)
{
     stack[++top]=now;dfn[now]=++tot;
     int size=0;
     for (int k=point[now];k!=0;k=next[k])
          if (v[k]!=fa[now][0])
          {
               fa[v[k]][0]=now;dep[v[k]]=dep[now]+1;
               size+=dfs(v[k]);
               if (size>=block)
               {
                    bn++;size=0;
                    while (stack[top]!=now)     b[stack[top--]]=bn;
               }
          }
     return size+1;
}
inline void reverse(int x)
{
     if (can[x]) {ans-=value[c[x]]*w[tim[c[x]]];tim[c[x]]--;}
          else ans+=value[c[x]]*w[++tim[c[x]]];
     can[x]=!can[x];
}
inline void change(int x,int y)
{
     if (can[x])
     {
          reverse(x);c[x]=y;reverse(x);
     }
     else c[x]=y;
}
inline void prepare()
{
     for (int i=1;i<=base;i++)
          for (int j=1;j<=n;j++)
               fa[j][i]=fa[fa[j][i-1]][i-1];
}
inline int lca(int x,int y)
{
     if (dep[x]<dep[y]) swap(x,y);
     if (dep[x]!=dep[y])
          for (int i=base;i>=0;i--)
               if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
     if (x==y) return x;
     for (int i=base;i>=0;i--)
          if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
     return fa[x][0];
}
inline int solve(int x,int y)
{
     if (dep[x]<dep[y]) swap(x,y);
     while (dep[x]!=dep[y])
     {
          reverse(x);x=fa[x][0];
     }
     while (x!=y)
     {
          reverse(x);reverse(y);
          x=fa[x][0];y=fa[y][0];
     }
     return x;
}
int main()
{
     int i,j,k,x,y,z;
     n=read();m=read();q=read();
     for (i=1;i<=m;i++) value[i]=read();
     for (i=1;i<=n;i++) w[i]=read();
     for (i=1;i<=n-1;i++) addedge(read(),read());
     for (i=1;i<=n;i++) pre[i]=now[i]=c[i]=read();
     memset(can,false,sizeof(can));
     block=(int)floor(pow(n,2.0/3));
     dep[1]=1;
     if (dfs(1)>0)
     {
          if (bn==0) bn++;
          while (top) b[stack[top--]]=bn;     
     }
     prepare();
     for (i=1;i<=q;i++)
     {
          z=read();x=read();y=read();
          if (!z) 
          {
               revise[++rn].x=x;revise[rn].y=y;revise[rn].pre=pre[x];
               pre[x]=y;//!!!
          }
          else
          {
               if (b[x]>b[y]) swap(x,y); 
               query[++qn].x=x;query[qn].y=y;query[qn].id=qn;query[qn].t=rn;
          }
     }
     sort(query+1,query+qn+1,cmp);
     for (i=1;i<=query[1].t;i++) change(revise[i].x,revise[i].y);
     k=solve(query[1].x,query[1].y); 
     reverse(k);a[query[1].id]=ans;reverse(k);
     for (i=2;i<=qn;i++)
     {
          for (j=query[i-1].t+1;j<=query[i].t;j++) 
               change(revise[j].x,revise[j].y);
          for (j=query[i-1].t;j>=query[i].t+1;j--) 
               change(revise[j].x,revise[j].pre);
          solve(query[i-1].x,query[i].x);
          solve(query[i-1].y,query[i].y);
          k=lca(query[i].x,query[i].y);
          reverse(k);
          a[query[i].id]=ans;
          reverse(k);
     }
     for (i=1;i<=qn;i++) printf("%lld\n",a[i]);
}
← 【bzoj3689】【XORthinking/可持久化trie+堆】异或之 ABOUT FRIENDS →
 
comments powered by Disqus