隐藏
「NOI2018模拟4」简单树题 - 树链剖分+树状数组+分块 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「NOI2018模拟4」简单树题 - 树链剖分+树状数组+分块

题目大意

    给出一棵$n$个点的树,点从$1\sim n$编号,给出树上每条边的长度。
    你需要顺次执行$m$个操作,操作分为两种:

  1. modify x y:将树上的第$x$条边的长度修改为$y$。
  2. query L R x:对于当前这棵树,查询编号在$[L,R]$内的所有点到点$x$的距离之和。

    数据可能会强制在线。


题目分析

一段编号连续的点,一看就不可做。
此时我们就需要发出毒瘤的声音:分块。
对编号分块,询问的时候拆分成在整块内的和块外零碎的点。
将距离和拆分为(设$dist(x)$为$x$到根的权值和):

$(R-L+1)dist(x)$很好处理,利用分块$\sum_{L\le i\le R}dist(i)$也很好处理。
比较麻烦的就是求$\sum_{L\le i\le R}dist(LCA(i,x))$。

很久以前LZX讲过一种求集合LCA权值和的方法:
每个点将其到根的点全部标记$+1$,另外一个点查询到根的标记数,即为LCA总数。
如此重复,即可求出集体LCA权值和,但这是基于不带权树的。
带权树也很简单,只需要考虑子树的点对每条边长做的贡献即可。
在维护块的答案时,对于每条边的贡献为子树size倍的边长。

然后就变得可做毒瘤了。
修改查询使用树状数组,用树剖会光荣卡常。
另外块大小也很有讲究,开得不好会被卡成暴力分。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=70005,maxb=250;

struct Edge {
int from,to,dist;
Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
} edge[maxn];

int n,m,step=0,Size[maxn],father[maxn],Depth[maxn],Son[maxn],First[maxn],Last[maxn],Top[maxn],Belong[maxn],Left[maxb],Right[maxb];
LL dist[maxn],ans=0;
vector<Edge> edges[maxn];

void Dfs1(int Now,int fa,int depth) {
Size[Now]=1;
father[Now]=fa;
Depth[Now]=depth;
for(Edge &e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
dist[Next]=e.dist;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Next]>Size[Son[Now]])Son[Now]=Next;
}
}

void Dfs2(int Now,int top) {
First[Now]=++step;
Top[Now]=top;
if(Son[Now])Dfs2(Son[Now],top);
for(Edge &e:edges[Now]) {
int Next=e.to;
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
Last[Now]=step+1;
}

int LCA(int x,int y) {
for(; Top[x]!=Top[y]; x=father[Top[x]])if(Depth[Top[x]]<Depth[Top[y]])swap(x,y);
return Depth[x]<Depth[y]?x:y;
}

struct BIT {
LL c[maxn];
#define lowbit(x) (x&(-x))
void add(int x,LL v) {for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;}
LL query(int x) {
LL ans=0;
for(int i=x; i>=1; i-=lowbit(i))ans+=c[i];
return ans;
}
} all;

struct Block {
int left,right;
BIT in;
LL sum;
int Size[maxn];
void Dfs(int Now) {
Size[Now]=(left<=Now&&right>=Now);
for(Edge &e:edges[Now]) {
int Next=e.to;
if(Next==father[Now])continue;
Dfs(Next);
sum+=1ll*e.dist*Size[Next];
Size[Now]+=Size[Next];
}
in.add(First[Now],dist[Now]*Size[Now]);
in.add(Last[Now],-dist[Now]*Size[Now]);
}
void modify(int Now,LL val) {
sum+=Size[Now]*(val-dist[Now]);
in.add(First[Now],(val-dist[Now])*Size[Now]);
in.add(Last[Now],(dist[Now]-val)*Size[Now]);
}
LL query(int Now) {return sum+(right-left+1)*all.query(First[Now])-2*in.query(First[Now]);}
} B[maxb];

LL Dist(int x,int y) {return all.query(First[x])+all.query(First[y])-2*all.query(First[LCA(x,y)]);}

LL Query(int l,int r,int x) {
int L=Belong[l],R=Belong[r];
LL ans=0;
if(R-L<=1) {
for(int i=l; i<=r; i++)ans+=Dist(i,x);
return ans;
}
for(int i=l; i<=Right[L]; i++)ans+=Dist(i,x);
for(int i=Left[R]; i<=r; i++)ans+=Dist(i,x);
return ans+B[R-1].query(x)-B[L].query(x);
}

int main() {
n=Get_Int();
m=Get_Int();
int type=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
edge[i]=Edge(x,y,v);
edges[x].push_back(Edge(x,y,v));
edges[y].push_back(Edge(y,x,v));
}
Dfs1(1,0,1);
Dfs2(1,1);
for(int i=1; i<n; i++)if(Depth[edge[i].from]<Depth[edge[i].to])swap(edge[i].from,edge[i].to);
for(int i=1; i<=n; i++)all.add(First[i],dist[i]),all.add(Last[i],-dist[i]);
int size=300,BCC=0;
for(int i=1; i<=n; i++) {
Belong[i]=(i-1)/size+1;
if(!B[Belong[i]].left)B[Belong[i]].left=1,Left[Belong[i]]=i,BCC++;
B[Belong[i]].right=Right[Belong[i]]=i;
}
for(int i=1; i<=BCC; i++)B[i].Dfs(1);
while(m--) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
if(opt=='m') {
int x=Get_Int()^(type*ans),y=Get_Int()^(type*ans);
x=edge[x].from;
for(int i=1; i<=BCC; i++)B[i].modify(x,y);
all.add(First[x],y-dist[x]);
all.add(Last[x],dist[x]-y);
dist[x]=y;
} else {
int x=Get_Int()^(type*ans),y=Get_Int()^(type*ans),z=Get_Int()^(type*ans);
printf("%lld\n",ans=Query(x,y,z));
ans%=n;
}
}
return 0;
}
姥爷们赏瓶冰阔落吧~