BZOJ 4012 开店

发表于 | 更新于

Link

Solution 树链剖分套主席树

先不管颜色的限制 形式化条件：(len[x]len[x]为xx到根节点的距离) Ans=∑poslen[u]+len[pos]−len[lca(pos,u)]Ans=\sum\limits_{pos} len[u]+len[pos]-len[lca(pos,u)] 可以把len[u]len[u]和len[pos]len[pos]都提出来，答案就变成了计算∑poslen[lca(pos,u)]\sum\limits_{pos}len[lca(pos,u)] 也就是u,posu,pos到根节点路径的交集。这个可以通过先把每个点到根节点的路径都覆盖一遍，查询时候只需要统计出∑v[e]coverCnt[e]\sum v[e]coverCnt[e]即可。可以通过线段树实现。其中标记永久化的处理非常有意思。 套上了颜色的限制，就仿照序列主席树的做法，把点按照颜色排序，顺序依次覆盖。 空间上界是O(nlog2n)O(n\log^2 n)的，但是似乎跑不满。 时间是O(nlog2n)O(n\log^2 n)，常数小，跑得非常快。

Code

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include "lucida"
using std::min;
using std::max;
using std::fill;
using std::sort;
using std::unique;
using std::lower_bound;
using std::upper_bound;
using std::partial_sum;
const int MAXN=150000+11,MAXLOGN=20;
int nums[MAXN],nc,a[MAXN],order[MAXN];
bool CompareValue(const int &i,const int &j) {
	return a[i]<a[j];
}
struct Edge {
	int to,v;Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int v) {
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
int64 pref[MAXN];
namespace segtree {
	const int SIZE=MAXN*MAXLOGN*7;
	struct Node *null;
	struct Node {
		Node *son[2];
		int64 sumv;int covc;
		Node():sumv(0) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE),*Pool=Me;
			assert(Me-Pool<SIZE);
			return Me++;
		}
	}*_null=null=new Node,*_null_son=null->son[0]=null->son[1]=null;
	class SegTree {
	public:
		SegTree() {}
		SegTree(int n,int L,int R):root(alloc(Node*,n+1)),L(L),R(R) {
			fill(root,root+1+n,null);
		}
		void Add(int rc,int l,int r) {
			Edit(root[rc]=root[rc]==null?root[rc-1]:root[rc],L,R,l,r);
		}
		int64 Sum(int cl,int cr,int l,int r) {
			return Access(root[cl-1],root[cr],L,R,l,r);
		}
	private:
		Node **root;int L,R;
		void Edit(Node *&pos,int L,int R,int l,int r) {
			pos=new Node(*pos);
			if(L==l && R==r) {
				pos->covc++;
			} else {
				pos->sumv+=pref[r]-pref[l-1];
				int Mid=(L+R)>>1;
				if(r<=Mid) {
					Edit(pos->son[0],L,Mid,l,r);
				} else if(Mid+1<=l) {
					Edit(pos->son[1],Mid+1,R,l,r);
				} else {
					Edit(pos->son[0],L,Mid,l,Mid);
					Edit(pos->son[1],Mid+1,R,Mid+1,r);
				}
			}
		}
		int64 Access(Node *pl,Node *pr,int L,int R,int l,int r) {
			int64 res=(pref[r]-pref[l-1])*(pr->covc-pl->covc);
			if(L==l && R==r) {
				res+=pr->sumv-pl->sumv;//covc
			} else {
				int Mid=(L+R)>>1;
				if(r<=Mid) {
					res+=Access(pl->son[0],pr->son[0],L,Mid,l,r);
				} else if(Mid+1<=l) {
					res+=Access(pl->son[1],pr->son[1],Mid+1,R,l,r);
				} else {
					res+=Access(pl->son[0],pr->son[0],L,Mid,l,Mid)+Access(pl->son[1],pr->son[1],Mid+1,R,Mid+1,r);
				}
			}
			return res;
		}
	};
}using segtree::SegTree;
SegTree seg;
int fa[MAXN],dep[MAXN],sz[MAXN],prefer[MAXN],cht[MAXN],dfn[MAXN],dfs[MAXN],dc,total[MAXN];
int64 len[MAXN],cpfLen[MAXN];
void DFS(int pos) {
	sz[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		len[u]=len[pos]+e->v;
		fa[u]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
		sz[pos]+=sz[u];
		prefer[pos]=sz[u]>sz[prefer[pos]]?u:prefer[pos];
	}
}
void Assign(int pos) {
	dfs[dfn[pos]=++dc]=pos;
	if(prefer[pos]) {
		cht[prefer[pos]]=cht[pos];Assign(prefer[pos]);
		for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos] && e->to!=prefer[pos]) {
			int u=e->to;
			cht[u]=u;
			Assign(u);
		}
	}
}
void Divide() {
	dep[1]=1;DFS(1);
	cht[1]=1;Assign(1);
	new(&seg) SegTree(nc,1,dc);
	for(int i=1;i<=dc;++i) {
		pref[i]=pref[i-1]+len[dfs[i]]-len[fa[dfs[i]]];
		cpfLen[a[i]]+=len[i];
	}
	partial_sum(cpfLen+1,cpfLen+1+nc,cpfLen+1);
}
void Modify(int pos) {
	int color=a[pos];
	while(pos) {
		seg.Add(color,dfn[cht[pos]],dfn[pos]);//把路径上的边都覆盖一下
		pos=fa[cht[pos]];
	}
}
int64 Query(int pos,int cl,int cr) {
	int64 res=(int64)(total[cr]-total[cl-1])*len[pos]+cpfLen[cr]-cpfLen[cl-1];//total[]
	while(pos) {
		res-=seg.Sum(cl,cr,dfn[cht[pos]],dfn[pos])<<1;//统计路径上覆盖的边权和(可以重复)
		pos=fa[cht[pos]];
	}
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,Q,A;is>>n>>Q>>A;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		nums[i]=a[i];
	}
	sort(nums+1,nums+1+n);
	nc=unique(nums+1,nums+1+n)-nums-1;
	for(int i=1;i<=n;++i) {
		a[i]=lower_bound(nums+1,nums+1+nc,a[i])-nums;//+nc
		order[i]=i;
		total[a[i]]++;
	}
	partial_sum(total+1,total+1+n,total+1);
	sort(order+1,order+1+n,CompareValue);
	for(int i=1;i<=n-1;++i) {
		int a,b,c;is>>a>>b>>c;
		Adde(a,b,c);
	}
	Divide();
	for(int i=1;i<=n;++i) {
		Modify(order[i]);
	}
	int64 last=0;
	for(int i=1;i<=Q;++i) {
		int x;int64 a,b,l,r;is>>x>>a>>b;
		l=min((a+last)%A,(b+last)%A);
		r=max((a+last)%A,(b+last)%A);
		last=Query(x,lower_bound(nums+1,nums+1+nc,l)-nums,upper_bound(nums+1,nums+1+nc,r)-nums-1);
		os<<last<<'\n';
	}
	return 0;
}

Solution 点分治

这个做法比较显然，保留分治结构，用vector记录按照颜色排序之后的前缀和。查询时二分查找。 时间O(nlog2n)O(n\log^2n)，空间O(nlogn)O(n\log n)。然而常数非常大

Code

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include "lucida"
import max;
import sort;
import swap;
import pair;
import unique;
import upper_bound;
import lower_bound;
const int MAXN=150000+11,MAXLOG=20;
int nums[MAXN],nc,a[MAXN];
struct Edge {
	int to,v;Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int v) {
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
namespace lca {
	int dep[MAXN],stdfs[MAXN<<1],stdc,stdfn[MAXN<<1],st[MAXLOG][MAXN<<1],log_2[MAXN<<1];int64 len[MAXN];
	void DFS(int pos) {
		stdfs[stdfn[pos]=++stdc]=pos;
		for(Edge *e=G[pos];e;e=e->pre) if(!stdfn[e->to]) {
			dep[e->to]=dep[pos]+1;
			len[e->to]=len[pos]+e->v;
			DFS(e->to);
			stdfs[++stdc]=pos;
		}
	}
	void Init() {
		DFS(1);
		log_2[0]=-1;
		for(int i=1;i<=stdc;++i) {
			st[0][i]=stdfs[i];
			log_2[i]=log_2[i>>1]+1;
		}
		for(int pl,pr,lg=1;lg<=log_2[stdc];++lg) {
			for(int i=1;i<=stdc-(1<<lg)+1;++i) {
				st[lg][i]=dep[pl=st[lg-1][i]]<dep[pr=st[lg-1][i+(1<<(lg-1))]]?pl:pr;
			}
		}
	}
	int LCA(int p1,int p2) {
		p1=stdfn[p1],p2=stdfn[p2];
		if(p1>p2) {
			swap(p1,p2);
		}
		int lg=log_2[p2-p1+1],pl=st[lg][p1],pr=st[lg][p2-(1<<lg)+1];
		return dep[pl]<dep[pr]?pl:pr;
	}
	int64 Dist(int p1,int p2) {
		int lca=LCA(p1,p2);
		return len[p1]+len[p2]-2*len[lca];
	}
}using lca::Dist;	
namespace dc {
	//分治完了之后，保存分治结构
	//在每个重心，记录下方的点，按照颜色排序，并且计算到这个点的距离的前缀和 用vector 空间? n log n
	//查询?
	//从该点沿着分治结构向上走，记录路径长度，另一段乘上个数 加上去
	int sz[MAXN],tol;
	bool ud[MAXN];
	void GetSize(int pos,int from) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			GetSize(u,pos);
			sz[pos]+=sz[u];
		}
	}
	int DP(int pos,int from) {
		static int f[MAXN]={INT_MAX};
		int res=0,mxs=0;
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			int temp=DP(u,pos);
			res=f[res]<f[temp]?res:temp;
			chkmx(mxs,sz[u]);
		}
		f[pos]=max(mxs,tol-sz[pos]);
		return f[pos]<f[res]?pos:res;
	}
	int Center(int rt) {
		GetSize(rt,0);
		tol=sz[rt];
		return DP(rt,0);
	}
	struct Node {
		int color;
		int64 sum;
		Node(int color,int64 sum):color(color),sum(sum) {}
		friend bool operator <(const Node &a,const Node &b) {
			return a.color<b.color;
		}
	};
	
	array<Node> path[MAXN],anti[MAXN];int uplayer[MAXN];
	void DFS(int pos,int from,int64 dist,array<Node> &arr) {
		arr.push_back(Node(a[pos],dist));
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			DFS(u,pos,dist+e->v,arr);
		}
	}
	void DC(int pos) {
		ud[pos]=1;
		path[pos].push_back(Node(a[pos],0));//..
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to]) {
			int u=e->to,gcu=Center(u);
			DFS(u,pos,e->v,anti[gcu]);
			uplayer[gcu]=pos;
			path[pos].insert(path[pos].end(),anti[gcu].begin(),anti[gcu].end());
			sort(anti[gcu].begin(),anti[gcu].end());
			for(int i=1,ei=anti[gcu].size();i<ei;++i) {//i=1?????
				anti[gcu][i].sum+=anti[gcu][i-1].sum;
			}
			DC(gcu);
		}
		sort(path[pos].begin(),path[pos].end());
		for(int i=1,ei=path[pos].size();i<ei;++i) {
			path[pos][i].sum+=path[pos][i-1].sum;
		}
	}
	void Run() {
		DC(Center(1));
	}
	pair<int64,int> Calc(array<Node> &ar,int l,int r) {
		int pl=lower_bound(ar.begin(),ar.end(),Node(l,0))-ar.begin(),
			pr=upper_bound(ar.begin(),ar.end(),Node(r,0))-ar.begin()-1;
		return pl!=(int)ar.size() && ~pr?pair<int64,int>(ar[pr].sum-(pl?ar[pl-1].sum:0),pr-pl+1):pair<int64,int>(0,0);
	}
	int64 Query(int pos,int l,int r) {
		int64 res=Calc(path[pos],l,r).first;int s=pos;
		while(uplayer[pos]) {
			pair<int64,int> cur=Calc(path[uplayer[pos]],l,r),ant=Calc(anti[pos],l,r);
			res+=cur.first-ant.first+(cur.second-ant.second)*Dist(s,uplayer[pos]);
			pos=uplayer[pos];
		}
		return res;
	}
}using dc::Run;using dc::Query;
int main() {
//	freopen("input","r",stdin);
	int n,Q,A;is>>n>>Q>>A;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		nums[i]=a[i];
	}
	sort(nums+1,nums+1+n);
	nc=unique(nums+1,nums+1+n)-nums-1;
	for(int i=1;i<=n;++i) {
		a[i]=lower_bound(nums+1,nums+1+nc,a[i])-nums;
	}
	for(int i=1;i<=n-1;++i) {
		int a,b,c;is>>a>>b>>c;
		Adde(a,b,c);
	}
	lca::Init();
	dc::Run();
	int64 last=0;
	for(int i=1;i<=Q;++i) {
		int x;int64 a,b,l,r;is>>x>>a>>b;
		l=(a+last)%A;r=(b+last)%A;
		a=l<r?l:r;b=l<r?r:l;
		l=a;r=b;
		last=Query(x,lower_bound(nums+1,nums+1+nc,l)-nums,upper_bound(nums+1,nums+1+nc,r)-nums-1);
		os<<last<<'\n';
	}
	return 0;
}