UOJ#435. 【集訓隊作業2018】Simple Tree 樹鍊剖分,分塊

前言

分塊題果然是我這種蒟蒻寫不動的。由于種種原因，我寫代碼的時候打錯了很多東西，最緻命的是數組開小了。**windows不能檢測數組越界，能眼查出來這運氣是真的好。

題解

首先樹鍊剖分，把問題轉化為序列上的問題。

然後我們分塊。

考慮如何維護每一塊的答案。

初始時，我們預處理将每一塊的相同值元素合并。

考慮修改操作：

如果是整塊修改，那麼臨界指針位移即可。

否則就是零散修改，我們可以直接重構整個塊。由于時間複雜度要求比較緊，是以我們需要想一個不帶 log 的重構方法。

首先一個棘手的問題就是我們難以在不帶 log 的前提下對要修改的值在塊内有序序列中的定位。

于是我們考慮再維護一個不離散化的有序表，并提前處理出每一個值在這個有序表中的位置。這樣，我們在修改了一些值之後，隻需要做一次對兩個有序表進行歸并即可。

（寫完代碼後才發現似乎可以簡單些……）

由于套了一層樹鍊剖分，是以看起來時間複雜度是 $O(m\sqrt{n}\log n)$ 的。

但是仔細看可以發現，單次操作中，整塊修改的次數是 $O(\sqrt n)$ 的，塊内重構的次數是 $O(\sqrt n\log n)$ 的。

于是，通過調整塊大小，就可以得到了一個 $O(n\sqrt{n \log n})$ 的算法。

代碼

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Fod(i,b,a) for (int i=b;i>=a;i--)
#define pb(x) push_back(x)
using namespace std;
typedef long long LL;
LL read(){
  LL x=0,f=0;
  char ch=getchar();
  while (!isdigit(ch))
    f|=ch=='-',ch=getchar();
  while (isdigit(ch))
    x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  return f?-x:x;
}
const int N=100005;
int n,m,type;
int a[N];
vector <int> e[N];
int fa[N],depth[N],size[N],son[N],top[N],I[N],O[N],aI[N];
void dfs1(int x,int pre,int d){
  fa[x]=pre,depth[x]=d,size[x]=1,son[x]=0;
  for (auto y : e[x])
    if (y!=pre){
      dfs1(y,x,d+1);
      size[x]+=size[y];
      if (!son[x]||size[y]>size[son[x]])
        son[x]=y;
    }
}
int Time=0;
void dfs2(int x,int Top){
  I[x]=++Time;
  aI[Time]=x;
  top[x]=Top;
  if (son[x])
    dfs2(son[x],Top);
  for (auto y : e[x])
    if (y!=fa[x]&&y!=son[x])
      dfs2(y,y);
  O[x]=Time;
}
int lastans=0;
const int B=50;
int v[N/B+5][B+5],c[N/B+5][B+5],v2[N/B+5][B+5];
int cnt[N/B+5],d[N/B+5],p[N/B+5],tot[N/B+5],cnt2[N/B+5];
int pos[N];
int bid(int x){
  return x==0?-1:(x-1)/B;
}
void getv(int b){
  v[b][1]=a[v2[b][1]];
  c[b][1]=cnt[b]=1;
  For(i,2,cnt2[b]){
    if (a[v2[b][i]]==a[v2[b][i-1]])
      c[b][cnt[b]]++;
    else {
      c[b][++cnt[b]]=1;
      v[b][cnt[b]]=a[v2[b][i]];
    }
  }
  tot[b]=d[b]=0,p[b]=cnt[b]+1;
  while (p[b]>1&&v[b][p[b]-1]>0)
    tot[b]+=c[b][--p[b]];
}
void rebuild(int b,int L,int R,int v){
  static int f[B+5],tmp[B+5],id[B+5];
  For(i,1,cnt2[b])
    a[v2[b][i]]+=d[b];
  d[b]=0,clr(f),clr(tmp);
  For(i,L,R){
    int x=aI[i],ps=pos[x];
    f[ps]=1,tmp[ps]=x,a[x]+=v;
  }
  int idc=0,i=1,j=1;
  while (1){
    while (i<=cnt2[b]&&f[i])
      i++;
    while (j<=cnt2[b]&&!f[j])
      j++;
    if (i>cnt2[b]&&j>cnt2[b])
      break;
    if (i<=cnt2[b]&&(j>cnt2[b]||a[v2[b][i]]<a[tmp[j]]))
      id[++idc]=v2[b][i++];
    else
      id[++idc]=tmp[j++];
  }
  cnt2[b]=idc;
  For(i,1,idc)
    v2[b][i]=id[i];
  For(i,1,cnt2[b])
    pos[v2[b][i]]=i;
  getv(b);
}
void Upd(int L,int R,int w){
  int Lid=bid(L),Rid=bid(R);
  if (Lid==Rid)
    rebuild(Lid,L,R,w);
  else {
    rebuild(Lid,L,(Lid+1)*B,w);
    rebuild(Rid,Rid*B+1,R,w);
    For(i,Lid+1,Rid-1){
      d[i]+=w;
      while (p[i]<=cnt[i]&&v[i][p[i]]+d[i]<=0)
        tot[i]-=c[i][p[i]++];
      while (p[i]>1&&v[i][p[i]-1]+d[i]>0)
        tot[i]+=c[i][--p[i]];
    }
  }
}
bool cmp(int x,int y){
  return a[x]<a[y];
}
void update(int x,int y,int v){
  int fx=top[x],fy=top[y];
  while (fx!=fy){
    if (depth[fx]<depth[fy])
      swap(fx,fy),swap(x,y);
    Upd(I[fx],I[x],v);
    x=fa[fx],fx=top[x];
  }
  if (depth[x]>depth[y])
    swap(x,y);
  Upd(I[x],I[y],v);
}
int Query_block(int L,int R){
  int ans=0,Lid=bid(L),Rid=bid(R);
  if (Lid==Rid){
    For(i,L,R)
      ans+=a[aI[i]]+d[Lid]>0;
  }
  else {
    Fod(i,(Lid+1)*B,L)
      ans+=a[aI[i]]+d[Lid]>0;
    For(i,Rid*B+1,R)
      ans+=a[aI[i]]+d[Rid]>0;
    For(i,Lid+1,Rid-1)
      ans+=tot[i];
  }
  return ans;
}
int Query(int x,int y){
  int ans=0,fx=top[x],fy=top[y];
  while (fx!=fy){
    if (depth[fx]<depth[fy])
      swap(fx,fy),swap(x,y);
    ans+=Query_block(I[fx],I[x]);
    x=fa[fx],fx=top[x];
  }
  if (depth[x]>depth[y])
    swap(x,y);
  ans+=Query_block(I[x],I[y]);
  return ans;
}
int main(){
  n=read(),m=read(),type=read();
  For(i,1,n-1){
    int x=read(),y=read();
    e[x].pb(y),e[y].pb(x);
  }
  For(i,1,n)
    a[i]=read();
  dfs1(1,0,0);
  dfs2(1,1);
  For(i,1,n){
    int b=bid(I[i]);
    v2[b][++cnt2[b]]=i;
  }
  int mxb=bid(n);
  For(i,0,mxb){
    sort(v2[i]+1,v2[i]+cnt2[i]+1,cmp);
    For(j,1,cnt2[i])
      pos[v2[i][j]]=j;
    getv(i);
  }
  while (m--){
    int op=read();
    if (op==1){
      int x=read(),y=read(),w=read();
      if (type)
        x^=lastans,y^=lastans;
      update(x,y,w);
    }
    else if (op==2){
      int x=read(),y=read();
      if (type)
        x^=lastans,y^=lastans;
      printf("%d\n",lastans=Query(x,y));
    }
    else if (op==3){
      int x=read();
      if (type)
        x^=lastans;
      printf("%d\n",lastans=Query_block(I[x],O[x]));
    }
  }
  return 0;
}