[cf1491H]Yuezheng Ling and Dynamic Tree

将其按照区间分块（即$[(i-1)K+1,iK]$作为一个块），并定义$f_{x}$表示$x$的祖先中编号最小且与$x$在同一个块内的节点，$f_{x}$可以通过$f_{a_{x}}$转移，即$f_{x}=\begin{cases}f_{a_{x}}\ \ \ (x与a_{x}在一个块中)\\x\ \ \ \ \ \ (x与a_{x}不在一个块中)\end{cases}$

（特别的，若$x$在第一个块中则$f_{x}=1$）

通过$f_{x}$，类似于树剖的方式，即若两者$f_{x}$不同则移动$f_{x}$较大的（移动到$f_{x}$），直至相同再用同样的方式爬$a_{x}$，复杂度显然是$o(q\sqrt{n})$的

接下来是如何维护$f_{x}$，即如何支持修改：

对于边角的两个块，显然是可以暴力维护的，对于整块修改，显然当一个块被修改$\sqrt{n}$次后一定有$f_{x}=x$，因此至多$o(n)$次暴力，复杂度也是$o(n\sqrt{n})$

最终总复杂度即为$o((n+q)\sqrt{n})$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 int n,m,K,p,x,y,z,a[N],bl[N],st[N],ed[N],f[N];

 5 long long tag[N];

 6 int get(int k){

 7     return max(a[k]-tag[bl[k]],1LL);

 8 }

 9 void calc(int x,int y){

10     for(int i=x;i<=y;i++)

11         if (bl[i]==1)f[i]=1;

12         else{

13             int x=get(i);

14             if (bl[x]!=bl[i])f[i]=i;

15             else f[i]=f[x];

16         }

17 }

18 int main(){

19     scanf("%d%d",&n,&m);

20     for(int i=2;i<=n;i++)scanf("%d",&a[i]);

21     K=(int)sqrt(n);

22     for(int i=1;i<=n;i++)bl[i]=(i-1)/K+1;

23     for(int i=1;i<=bl[n];i++){

24         st[i]=(i-1)*K+1;

25         ed[i]=min(i*K,n);

26         calc(st[i],ed[i]);

27     }

28     calc(1,n);

29     for(int i=1;i<=m;i++){

30         scanf("%d%d%d",&p,&x,&y);

31         if (p==1){

32             scanf("%d",&z);

33             if (bl[x]==bl[y]){

34                 for(int j=x;j<=y;j++)a[j]=max(a[j]-z,1);

35                 calc(st[bl[x]],ed[bl[x]]);

36             }

37             else{

38                 for(int j=x;j<=ed[bl[x]];j++)a[j]=max(a[j]-z,1);

39                 calc(st[bl[x]],ed[bl[x]]);

40                 for(int j=st[bl[y]];j<=y;j++)a[j]=max(a[j]-z,1);

41                 calc(st[bl[y]],ed[bl[y]]);

42                 for(int j=bl[x]+1;j<=bl[y]-1;j++){

43                     tag[j]+=z;

44                     if (tag[j]-z<=K)calc(st[j],ed[j]);

45                 }

46             }

47         }

48         else{

49             while (f[x]!=f[y]){

50                 if (f[x]>f[y])swap(x,y);

51                 y=get(f[y]);

52             }

53             if (x==y){

54                 printf("%d\n",x);

55                 continue;

56             }

57             while (get(x)!=get(y)){

58                 if (get(x)>get(y))swap(x,y);

59                 y=get(y);

60             }

61             if (x==y)printf("%d\n",x);

62             else printf("%d\n",get(x));

63         }

64     }

65 }

巴特西

[cf1491H]Yuezheng Ling and Dynamic Tree

最新文章

热门文章