发表于 | 更新于

Link

Solution

就是枚举有多少个1求有多少个含有这些个1的数字。。 然后一开始在Windows计算器上看1e15是几位数，结果可能是少看了几个0少算了几位然后数组开小了然后T飞了然后本地还一切正常 指数不会爆long long，可以直接不膜。如果一定要膜，需要膜φ(p)\varphi(p)。

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
#include "lucida"

const int P=10000007,Phi=9988440,B=50,MAXB=B+5;
int64 C[MAXB][MAXB];
void Prep() {
	C[0][0]=1;
	for(int i=1;i<=B;++i) {
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Phi;
	}
}
int bit[MAXB],len;
int64 Cal(int k) {
	int64 res=0;
	for(int i=len,cnt=0;i;--i)
		if(bit[i]) {
			(res+=C[i-1][k-cnt])%=Phi;
			if(k+1==++cnt)
				break;
		}
	return res;
}
int64 Pow(int64 base,int64 index) {
	int64 res=1;
	for(;index;(base*=base)%=P,index>>=1)
		if(index&1) (res*=base)%=P;
	return res;
}
int main() {
	freopen("input","r",stdin);
	Prep();
	int64 n,x;is>>n;
	for(len=0,x=n+1;x;x>>=1)
		bit[++len]=x&1;
	bit[len+1]=0;
	int64 Ans=1;
	for(int i=1;i<=len;++i)
		(Ans*=Pow(i,Cal(i)))%=P;
	os<<Ans<<'\n';
	return 0;
}
//TLE? 负数吗？？

发表于 | 更新于

Link

真的很想自己做出来，于是就想按套路先DP预处理再用输入去卡DP值。。 然而真的想不出来。 所以套路要有，但只会套路做题也是不行的。

Tips

数位DP可以边DP边卡上下界×2\times 2。 只要在状态里设计上需不需要继续卡边界即可×2\times 2

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
#include "lucida"
const int MAXB=70;
int64 f[MAXB][2][2][2],g[MAXB][2][2][2];
//f个数					g总和
int64 Solve(int64 n,int64 m,int64 K,int P) {
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	f[64][1][1][1]=1;
	--n;--m;
	for(int i=63;~i;--i) {
		int bn=n>>i&1;
		int bm=m>>i&1;
		int bk=K>>i&1;//bn^bm;
		for(int fns=0;fns<2;++fns)
			for(int fms=0;fms<2;++fms)
				for(int fks=0;fks<2;++fks)
					for(int newn=0;newn<2;++newn)
						for(int newm=0;newm<2;++newm) {
							int newk=newn^newm;
							if((fns && newn>bn) || (fms && newm>bm) || (fks && newk<bk)) continue;
							int gns=fns && (newn==bn),
								gms=fms && (newm==bm),
								gks=fks && (newk==bk);
							(f[i][gns][gms][gks]+=f[i+1][fns][fms][fks])%=P;
							(g[i][gns][gms][gks]+=(g[i+1][fns][fms][fks]+(f[i+1][fns][fms][fks]*(((int64)newk<<i)%P))%P))%=P;
						}
	}
	int64 Ans=0;K%=P;
	for(int ns=0;ns<2;++ns)
		for(int ms=0;ms<2;++ms)
			for(int ks=0;ks<2;++ks)
				(Ans+=g[0][ns][ms][ks]-K*f[0][ns][ms][ks])%=P;
	return (Ans+P)%P;
}
int main() {
	freopen("input","r",stdin);
	int T;is>>T;
	while(T--) {
		int64 n,m,K;
		int P;
		is>>n>>m>>K>>P;
		os<<Solve(n,m,K,P)<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

总算明白了大神们口中说的“剖完之后套用链上做法”的方法了。。。

Solution

要对链加标记算前缀和，要想办法转化成序列的问题。然而普通的DFS序可能会把路径弄成很多段，这不好。如果用树链剖分剖出的DFS序，一个路径在DFS序上最多O(logn)O(\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
#include "lucida"
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
using std::lower_bound;
using std::sort;
using std::unique;
using std::vector;
using std::swap;
using std::max;
const int MAXN=100000+11;
int nums[MAXN],nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
int dep[MAXN],sz[MAXN],prefer[MAXN],fa[MAXN],cht[MAXN];
void DFS(int pos) {
	sz[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(fa[pos]!=e->to) {
			int u=e->to;
			fa[u]=pos;
			dep[u]=dep[pos]+1;
			DFS(u);
			sz[pos]+=sz[u];
			if(sz[u]>sz[prefer[pos]])
				prefer[pos]=u;
		}
}
int dfn[MAXN],dfs[MAXN],dc;
void Assign(int pos) {
	dfs[++dc]=pos;
	dfn[pos]=dc;
	if(prefer[pos]) {
		cht[prefer[pos]]=cht[pos];
		Assign(prefer[pos]);
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=prefer[pos] && fa[pos]!=e->to) {
				cht[e->to]=e->to;
				Assign(e->to);
			}
	}
}
void Divide() {
	DFS(1);
	cht[1]=1;
	Assign(1);
}
struct Data {
	int cnt,id;
	Data(int cnt,int id):cnt(cnt),id(id){}
	bool operator <(const Data &a) const {
		return cnt==a.cnt?id>a.id:cnt<a.cnt;
	}
};
struct Tag {
	int v,cnt;
	Tag(int v,int cnt):v(v),cnt(cnt){}
};
vector<Tag> tag[MAXN];
void Modify(int p1,int p2,int c) {
	while(cht[p1]!=cht[p2]) {
		if(dep[cht[p1]]<dep[cht[p2]])
			swap(p1,p2);
		tag[dfn[cht[p1]]].push_back(Tag(c,1));
		tag[dfn[p1]+1].push_back(Tag(c,-1));
		p1=fa[cht[p1]];
	}
	if(dep[p1]>dep[p2])
		swap(p1,p2);
	tag[dfn[p1]].push_back(Tag(c,1));
	tag[dfn[p2]+1].push_back(Tag(c,-1));
}
namespace segtree {
	struct Node {
		Node *son[2];
		Data maxv;
		Node(Data maxv):maxv(maxv) {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN<<2);
			return Me++;
		}
		void Up() {
			maxv=max(son[0]->maxv,son[1]->maxv);
		}
	};
	struct SegTree {
		Node *root;
		int L,R;
		Node *operator ->() {
			return root;
		}
		/*
		operator Node *() {
			return root;
		} */
		void Build(Node *&pos,int L,int R) {
			pos=new Node(Data(0,L));
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int v) {
			if(L==R)
				pos->maxv.cnt+=v;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal,v);
				else
					Edit(pos->son[1],Mid+1,R,goal,v);
				pos->Up();
			}
		}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Edit(int pos,int v) {
			Edit(root,L,R,pos,v);
		}
	};
}using segtree::SegTree;
int main() {
	freopen("input","r",stdin);
	int n,m;
	is>>n>>m;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	Divide();
	static struct {int p1,p2,c;}op[MAXN];
	for(int i=1;i<=m;++i) {
		is>>op[i].p1>>op[i].p2>>op[i].c;
		nums[++nc]=op[i].c;
	}
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
	for(int i=1;i<=m;++i)
		Modify(op[i].p1,op[i].p2,ref(op[i].c));
	SegTree seg(1,nc);
	static int Ans[MAXN];
	for(int i=1;i<=n;++i) {
		for(vector<Tag>::iterator it=tag[i].begin();it!=tag[i].end();++it)
			seg.Edit(it->v,it->cnt);
		Ans[dfs[i]]=nums[seg->maxv.cnt==0?0:seg->maxv.id];		
	}
	for(int i=1;i<=n;++i)
		os<<Ans[i]<<'\n';
	return 0;
}

发表于 | 更新于

Link

一开始被题意唬了一下。。

Solution

对mulx操作，在左边插入一个0，删掉右端点并把系数加到右端点右边的端点 注意含有0，所以需要加加减减，然而Splay内部的空节点也要加加减减，所以要小心

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include "lucida"
const int MAXN=1e5+11,P=20130426;
struct Line {
	int64 k,b;
	Line():k(1),b(0){}
	Line(int64 k,int64 b):k(k),b(b){}
	operator bool() {
		return !(k==1 && b==0);
	}
	int64 operator () (int64 x) {
		return (k*x+b)%P;
	}
	Line operator () (Line x) {
		return Line(k*x.k%P,(k*x.b+b)%P);
	}
};
namespace splay {
	struct Node *null;
	struct Node {
		Node *son[2],*fa;
		int64 v;int sz;Line mrk;
		Node():v(v),sz(0) {
			son[0]=son[1]=fa=null;
		}
		Node(int64 v):v(v),sz(1) {
			son[0]=son[1]=fa=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN<<2);
			return Me++;
		}
		bool isRoot() {
			return fa==null;
		}
		int Kind() {
			return fa->son[1]==this;
		}
		void Modify(Line ln) {
			if(this==null) 
				return;
			v=ln(v);
			mrk=ln(mrk);
		}
		void Up() {
			sz=son[0]->sz+son[1]->sz+1;
		}
		void Down() {
			if(mrk) {
				son[0]->Modify(mrk);
				son[1]->Modify(mrk);
				mrk.k=1;mrk.b=0;
			}
		}
	}*llun=null=new Node;
	struct Splay {
		Node *root;
		Splay(){
			(root=new Node(0))->son[1]=new Node(0);
			(root->son[1]->fa=root)->Up();
		}
		void Trans(Node *pos) {
			Node *f=pos->fa,*grf=f->fa;
			f->Down();pos->Down();//反过来写会导致一些标记下传2次
			int d=pos->Kind();
			if(!f->isRoot())
				grf->son[f->Kind()]=pos;
			pos->fa=grf;//没写??
			f->son[d]=pos->son[!d];pos->son[!d]->fa=f;
			pos->son[!d]=f;f->fa=pos;
			f->Up();
		}
		void SplayTo(Node *pos,Node *goal) {
			Node *f;
			while((f=pos->fa)!=goal) {
				if(f->fa!=goal)
					Trans(f->Kind()==pos->Kind()?f:pos);
				Trans(pos);
			}
			pos->Up();
			if(goal==null)
				root=pos;
		}
		Node *Kth(int K) {
			++K;
			Node *pos=root;int c;
			while(pos!=null) {
				if((c=pos->son[0]->sz+1)==K)
					break;
				else if(K<c)
					pos=pos->son[0];
				else {
					pos=pos->son[1];
					K-=c;
				}
			}
			SplayTo(pos,null);
			return pos;
		}
		Node *Split(int L,int R) {
			Node *p1=Kth(L-1),*p2=Kth(R+1);
			SplayTo(p1,null);
			SplayTo(p2,p1);
			return p2->son[0];
		}
		void Insert(int pos,Node *newn) {
			Node *p1=Kth(pos),*p2=Kth(pos+1);
			SplayTo(p1,null);
			SplayTo(p2,p1);
			p1->Down(),p2->Down();
			p2->son[0]=newn;newn->fa=p2;
			SplayTo(newn,null);
		}
		Node* Insert(int pos,int v) {
			Node *newn=new Node(v);
			Insert(pos,newn);
			return newn;
		}
		void Delete(int pos) {
			Node *rt=Split(pos,pos);
			rt->fa->son[0]=null;//rt->son[0]=null...
			SplayTo(rt->fa,null);
		}
		Node *Build(int L,int R) {
			int Mid=(L+R)>>1;
			Node *pos=new Node(0);
			if(L!=Mid)
				(pos->son[0]=Build(L,Mid-1))->fa=pos;
			if(Mid!=R)
				(pos->son[1]=Build(Mid+1,R))->fa=pos;
			pos->Up();
			return pos;
		}
		void Make(int size) {
			int sz=root->sz-2;
			if((size-=sz)>0)
				Insert(sz,Build(1,size));
		}
		//对外的interface L,R是包含0的
		
		void Modify(int L,int R,Line ln) {
			++L,++R;
			Make(R);
			Node *rt=Split(L,R);
			rt->Modify(ln);
			SplayTo(rt,null);
		}
		int64* Out(Node *pos,int &cnt) {
			static int64 seq[MAXN];
			if(pos!=null) {
				pos->Down();
				Out(pos->son[0],cnt);
				seq[++cnt]=pos->v;
				Out(pos->son[1],cnt);
			}
			return seq;
		}
		void Print() {
			int cnt=0;
			int64 *s=Out(root,cnt);
			for(int i=1;i<=cnt;++i)
				os<<s[i]<<' ';
			os<<'\n';
		}
		int Query(int v) {
			v%=P;
			int cnt=0;
			int64 *s=Out(root,cnt);
			int64 powx=1,res=0;
			for(int i=2;i<=cnt-1;++i) {
				(res+=powx*s[i])%=P;
				(powx*=v)%=P;
			}
			return res;
		}
		void Mulx(int L,int R) {
			++L,++R;
			Make(R+1);
			int rv=Kth(R)->v;
			Delete(R);
			Insert(L-1,0);
			Modify(R,R,Line(1,rv));//Modify是对外部的interface 会自行++
		}
	};
}using splay::Splay;

int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	Splay sp;
	for(int i=1;i<=n;++i) {
		char opt[10];int L,R,v,Ans;
		is>>opt;
		switch(opt[0]) {
			case 'm':
				if(opt[3]=='x') {
					is>>L>>R;
					sp.Mulx(L,R);
				} else {
					is>>L>>R>>v;
					sp.Modify(L,R,Line(v,0));
				}
				break;
			case 'a':
				is>>L>>R>>v;
				sp.Modify(L,R,Line(1,v));
				break;
			case 'q':
				is>>v;
				Ans=sp.Query(v);
				os<<Ans<<'\n';
				break;
		}
	}
	return 0;
}

发表于 | 更新于

Link

Solution

数位DP模板？

然而有一点需要注意：长度不足nn的必须单独算(或者我没想出好办法？)

想了很长时间想巧妙地避免分开处理，发现不好避免。

所以数位DP就可以类比AC自动机DP，可以把长度小于给定串的单独处理。

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
#include "lucida"

int f[15][10];
void DP() {
	for(int i=0;i<10;++i)
		f[1][i]=1;
	for(int i=1;i<=10;++i)
		for(int j=0;j<10;++j)
			for(int k=0;k<10;++k)
				f[i][j]+=(abs(j-k)>=2)*f[i-1][k];
				//j==0? is that right?
}
int Cute(int x) {
	static int bit[15],len;
	//if(x==0) return 0;
	for(len=0,++x;x;x/=10)
		bit[++len]=x%10;
	bit[len+1]=2333;
	int res=0;
	for(int i=len-1;i;--i)
		for(int j=1;j<10;++j)
			res+=f[i][j];
	for(int i=len;i;--i) {
		for(int j=(i==len);j<bit[i];++j)
			res+=(abs(bit[i+1]-j)>=2)*f[i][j];
		if(abs(bit[i+1]-bit[i])<2)
			break;
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	DP();
	int l,r;
	is>>l>>r;
	os<<(Cute(r)-Cute(l-1))<<'\n';
	return 0;
}

发表于 | 更新于

Link

sro orz

Solution

预处理出块与块之间的答案，预处理出每个数字在前ii块的出现次数 然后对于零散部分遍历，记录每个数字的出现次数，利用整块的某个数字的奇偶性判断对答案的贡献+1/-1。

Tips

似乎序列分块的大体套路就是处理块与块的答案和想办法快速地计算零碎部分对答案的贡献？

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
#include "lucida"
using std::swap;
using std::partial_sum;
const int MAXN=1e5+5,MAXB=320;
struct MagicArray {
	int a[MAXN],us[MAXN],ut;
	void Reset() {
		++ut;
	}
	int &operator [](int x) {
		if(us[x]!=ut) {
			us[x]=ut;
			a[x]=0;
		}
		return a[x];
	}
}counter;
int a[MAXN],n,bsz,bc,bn[MAXN],bhe[MAXN],bAns[MAXB][MAXB],cext[MAXN][MAXB];
inline bool valid(int x) {
	return x && (!(x&1));
}
int Query(int l,int r) {
	counter.Reset();
	int res=0,c;
	if(bn[r]-bn[l]<=1) {
		for(int i=l;i<=r;++i) {
			if(valid(c=++counter[a[i]])) res++;
			else if(c!=1) res--;
		}
	} else {
		int lbo=bn[l]+1,rbo=bn[r]-1;
		res=bAns[lbo][rbo];
		for(int i=l;i<bhe[lbo];++i)
			if(valid(c=(++counter[a[i]]+cext[a[i]][rbo]-cext[a[i]][lbo-1]))) res++;
			else if(c!=1) res--;
		for(int i=bhe[bn[r]];i<=r;++i)
			if(valid(c=(++counter[a[i]]+cext[a[i]][rbo]-cext[a[i]][lbo-1]))) res++;
			else if(c!=1) res--;
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	int c,m;
	is>>n>>c>>m;
	bsz=(int)sqrt(n);
	for(int i=1;i<=n;++i) {
		is>>a[i];
		bn[i]=(i-1)/bsz+1;
		bhe[bn[i]]=bn[i-1]!=bn[i]?i:bhe[bn[i]];
	}
	bc=bn[n];
	for(int i=1;i<=n;++i)
		cext[a[i]][bn[i]]++;
	for(int i=1;i<=n;++i)
		partial_sum(cext[i]+1,cext[i]+1+bc,cext[i]+1);
	for(int lb=1;lb<=bc;++lb) {
		counter.Reset();
		int cnt=0,c;
		for(int i=bhe[lb];i<=n;++i) {
			if(valid(c=++counter[a[i]])) cnt++;
			else if(c!=1) cnt--;
			if(bn[i]!=bn[i+1])
				bAns[lb][bn[i]]=cnt;
		}
	}
	int Ans=0;
	#define decode(x) (((x+=Ans)%=n)+=1)
	for(int i=1;i<=m;++i) {
		int l,r;is>>l>>r;
		decode(l),decode(r);
		if(l>r) swap(l,r);
		os<<(Ans=Query(l,r))<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

小时候写过树状数组套主席树的版本，时空O(nlog2n)O(n\log^2n)。众所周知，这个空间复杂度是非常不友好的。 今天翻到jcvb巨神的博客，发现他给了一种非常interesting的做法：值域线段树套区间平衡树。研究一番，写完之后感觉很不错。

树状数组套主席树维护DFS序

Solution

众所周知，序列上的主席树可以利用可持久化实现时空O(nlogn)O(n\log n)的前缀和，从而解决区间K值问题。 放到树上，如果不带修改，那就可以直接用序列的可持久化线段树方法，从根节点DFS下去，在节点uu的值域线段树的[l,r][l,r]区间，维护uu到rootroot路径上值在[l,r][l,r]的节点个数。这样，两点u,vu,v的路径上，值在[l,r][l,r]的节点个数c(u,v)c(u,v)，就是c(u)+c(v)−c(lca)−c(fa[lca])c(u)+c(v)-c(lca)-c(fa[lca])。套用序列的方法查询即可。 现在有了修改，显然不可能暴力重建主席树，因为一次修改会影响子树的所有的点。 等等，一次修改影响子树所有的点？不禁让人思考能否进行区间操作？然后就联想到了DFS序。没错，DFS序就是一个满足子树的所有点是一个区间的序列。 区间操作的两种办法：用兹瓷区间修改的数据结构打标记；或者差分，把区间修改变成单点修改。待修改的树上主席树是通过套一个树状数组，绝对化相对的方法来实现的。这样，线段树就不需要可持久化了，因为本来可持久化是要维护前缀和，但现在树状数组就维护了前缀和。一次修改，会修改O(logn)O(\log n)个线段树，每个线段树修改的时间是O(logn)O(\log n)。一个点的值至多将在O(logn)O(\log n)个线段树出现，粗略地估计总次数，绝对不会超过O(logn)O(\log n)。所以得到了一个时空O(nlog2n)O(n\log ^2n)的优秀做法。

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
#define S(X,NUMO) seg[X].son[NUMO]
	

const int MAXN=80010;
const int MAXLOGN=18;
const int MAXRG=MAXN*2;
const int MAXLOGRG=20;
const int INF=522133279;
const int MAXP=12000000;

int nset[MAXN*2],nc=0;

inline int Get(int x)
{
	return lower_bound(nset+1,nset+nc,x)-nset;
}
int T[MAXN];int N,Q;
int e[MAXN*2],pre[MAXN*2],id[MAXN],ec=0;
int l2(int x)//log x 取下整
{
	int i=0;
	while((1<<i)<=x)
		++i;
	return i-1;
}
void adde(int _f,int _t)
{
	e[++ec]=_t;pre[ec]=id[_f];id[_f]=ec;
	e[++ec]=_f;pre[ec]=id[_t];id[_t]=ec;
}
int dfs[MAXN],dep[MAXN],dc=0,lin[MAXN],rout[MAXN],fa[MAXN];//BIT用
int mdfs[MAXN*2],ml[MAXN],mr[MAXN],mdc=0;//ST用
	//每条边访问一次,而每访问一条边加入2个点 所以总共是2n级别的
void DFS(int pos,int d)
{
	dep[pos]=++d;
	dfs[++dc]=pos;
	mdfs[++mdc]=pos;
	lin[pos]=rout[pos]=dc;
	ml[pos]=mr[pos]=mdc;
	for(int i=id[pos];i;i=pre[i])
		if(fa[pos]!=e[i])
		{
			fa[e[i]]=pos;
			DFS(e[i],d);
			rout[pos]=max(rout[pos],rout[e[i]]);		
			mdfs[++mdc]=pos;
			mr[pos]=max(mr[pos],mdc);
		}
	
}
int f[MAXN*2][20];//i到i+(2^j)-1 [i开始长度为2^j]的最浅点
void outst()
{
	for(int j=0;j<=l2(mdc);j++)
	{
		printf("2^%d:",j);
		for(int i=1;i<=mdc;i++)
			printf("%d-%d  ",i,f[i][j]);
		puts("");
	}
}
void ST()
//dfs
{
	for(int i=1;i<=mdc;i++)
		f[i][0]=mdfs[i];
	int endj=l2(mdc),endi,pl,pr,t;	
	for(int j=1;j<=endj;j++)
	{
		endi=mdc-(1<<j)+1;
		for(int i=1;i<=endi;i++)
		{
			pl=f[i][j-1];
			pr=f[i+(1<<j)-(1<<j>>1)][j-1];
			f[i][j]=dep[pl]<dep[pr]?pl:pr;
		}
	}
}

int LCA(int p1,int p2)
{
	p1=ml[p1],p2=ml[p2];
	if(p1>p2) swap(p1,p2);
	int j=l2(p2-p1+1),ans=-1;
	p1=f[p1][j],p2=f[p2-(1<<j)+1][j];
	return dep[p1]>dep[p2]?p2:p1;
}
int inp[MAXN][3];

struct SegNode
{
	int son[2],cnt;
};

struct BIT
{
	int root[MAXN],pc,n;
	SegNode seg[MAXP];int TL,TR;//1,N
	inline int lowbit(int x){return x&(-x);}
	BIT(){pc=0;}
	inline void valup(int pos)
	{
		seg[pos].cnt=0;
		if(S(pos,0)) seg[pos].cnt+=seg[S(pos,0)].cnt;
		if(S(pos,1)) seg[pos].cnt+=seg[S(pos,1)].cnt;
	}
	int Acs(int pos,int L,int R,int l,int r)
	{
		if(!pos)
			return 0;
		if(L==l && R==r)
			return seg[pos].cnt;
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID)
				return Acs(S(pos,0),L,MID,l,r);
			else if(MID+1<=l)
				return Acs(S(pos,1),MID+1,R,l,r);
			else
				return Acs(S(pos,0),L,MID,l,MID)+Acs(S(pos,1),MID+1,R,MID+1,r);
		}
	}
	int Edit(int pos,int L,int R,int goal,int v)
	{
		int pres=pos?pos:++pc;
		seg[pres]=seg[pos];
		if(L==R)
			seg[pres].cnt+=v;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID)
				S(pres,0)=Edit(S(pos,0),L,MID,goal,v);
			else
				S(pres,1)=Edit(S(pos,1),MID+1,R,goal,v);
			valup(pres);
		}
		return pres;
	}
	int Sum(int pos,int l,int r)
	//得到树上pos位置的线段树[l,r]区间的cnt
	{
		if(!pos)
			return 0;
		int ans=0;
		pos=lin[pos];
		for(;pos;pos-=lowbit(pos))	
			ans+=Acs(root[pos],TL,TR,l,r);
		return ans;
	}
	int add(int pos,int goal,int v)
	//修改dfs序列中的pos对应的树
	{
		for(;pos<=n;pos+=lowbit(pos))
			root[pos]=Edit(root[pos],TL,TR,goal,v);
	}
	int Add(int pos,int goal,int v)
	//修改pos(树上编号)应的子树的区间
	{
		add(lin[pos],goal,v);
		if(rout[pos]<n)
			add(rout[pos]+1,goal,-v);
		
	}
	int Que(int p1,int p2,int K)
	{
		int lca=LCA(p1,p2);
		K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
		if(K<=0)
			return -INF;

		int L=TL,R=TR,MID=(L+R)>>1,sum;
		//int s1,s2,s3;	
		while(K)
		{
			if(L==R)
			{
					return nset[L];
			}
			MID=(L+R)>>1;
			sum=Sum(p1,L,MID)+Sum(p2,L,MID)-Sum(lca,L,MID)-Sum(fa[lca],L,MID);
			
			if(sum<K)
			{
				K-=sum;
				L=MID+1;
			}
			else R=MID;
		}
		return INF;
	}
	void Out()
	{
		for(int i=1;i<=n;i++)
			printf("%d ",Sum(i,TL,TR));
		puts("");
	}
	void OutS()
	{
		for(int i=1;i<=n;i++)
			printf("%d ",Acs(root[i],TL,TR,TL,TR));
		puts("");
	}
}B;
void InitSeg(int pos)
{
	B.Add(pos,Get(T[pos]),1);
	for(int i=id[pos];i;i=pre[i])
		if(e[i]!=fa[pos])
			InitSeg(e[i]);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d%d",&N,&Q);
	B.n=N;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&T[i]);
		nset[++nc]=T[i];
	}
	int t1,t2,t3;
	for(int i=1;i<=N-1;i++)
	{
		scanf("%d%d",&t1,&t2);
		adde(t1,t2);
	}
	DFS(1,0);
	dep[0]=INF;
	ST();
	int *p;
	for(int i=1;i<=Q;i++)
	{
		p=inp[i];
		scanf("%d%d%d",&p[0],&p[1],&p[2]);
		if(!p[0])
			nset[++nc]=p[2];
	}
	sort(nset+1,nset+1+nc);
	nc=unique(nset+1,nset+1+nc)-nset-1;
	B.TL=1,B.TR=nc;
	InitSeg(1);
	for(int i=1;i<=Q;i++)
	{
		p=inp[i];
		if(!p[0])
		{
			B.Add(p[1],Get(T[p[1]]),-1);
			B.Add(p[1],Get(p[2]),1);
			T[p[1]]=p[2];
		}
		else
		{
			t1=B.Que(p[1],p[2],p[0]);
			if(t1!=-INF)
				printf("%d\n",t1);
			else
				puts("invalid request!");
		}
	}
	return 0;
}

线段树套平衡树维护括号序列

Solution

现在考虑优化的话，主要就是要考虑压缩空间，否则太不友好。注意到，空间之所以那么大，是因为把主席树建在了内层，一个点的权值可能出现在O(logn)O(\log n)棵线段树中，出现一次就至多带来O(logn)O(\log n)个节点，比较浪费。 那么考虑把值域线段树建在外层，那么这一部分的空间就是O(n)O(n)。考虑如何在内层维护整个树。 用DFS序列应该就不好弄了。。涉及到路径，DFS序似乎就无力了。。。 于是祭出大杀器：括号序！ 一个树的括号序，指的是每个点在进栈的时候放一个左括号，出栈的时候放一个右括号。 然后把一棵树的括号序写下来，会发现一个惊天大秘密：从第一个括号开始，到pospos的左括号，把匹配的括号删掉，恰好可以得到从根节点到pospos的路径！ 于是就可做了： 在值域线段树的每个节点[l,r][l,r]挂一个平衡树，平衡树维护所有值被[l,r][l,r]覆盖的点的左括号位置和右括号位置。左括号的权值为11，右括号为−1-1，这样做一下前缀和，就可以得到根节点到一个点的路径上有多少点的值在[l,r][l,r]之内了！然后就可以做了。 空间复杂度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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include "lucida"
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
const int MAXN=80000+11,INF=0x1f1f1f1f,MAXLOG=20;
int n,w[MAXN],nums[MAXN<<1],nc=0,dep[MAXN];
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
namespace treap {
	struct Node *null,**rec,*Me;
	const int P=99929,SIZE=(MAXN<<1)*MAXLOG;
	struct Node {
		Node *son[2];
		int val,cnt,sz,py;
		Node():sz(0),py(P) {
			son[0]=son[1]=0;
			val=-INF;
		}
		Node(int val,int cnt):val(val),cnt(cnt),sz(cnt),py(rand()%P) {
			son[0]=son[1]=null;
		}
		void Up() {
			sz=son[0]->sz+son[1]->sz+cnt;
		}
		void *operator new(size_t) {
			return *rec?*rec--:Me++;
		}
		void operator delete(void *p) {
			*++rec=(Node*)p;
		}
	}**cer=rec=alloc(Node*,SIZE),*eM=Me=alloc(Node,SIZE),*llun=null=new Node;
	struct Treap {
		Node *root;
		void Trans(Node *&pos,int d) {
			Node *s=pos->son[d];
			pos->son[d]=s->son[!d];
			s->son[!d]=pos;
			pos->Up();
			(pos=s)->Up();
		}
		int Adjust(Node *&pos) {
			int d=pos->son[0]->py>pos->son[1]->py;
			return pos->py>pos->son[d]->py?(Trans(pos,d),!d):-1;
		}
		void Fall(Node *&pos) {
			int d=Adjust(pos);
			if(d==-1) {
				delete pos;
				pos=null;
			} else {
				Fall(pos->son[d]);
				pos->Up();
			}
		}
		void Delete(Node *&pos,int val) {
			if(pos->val==val) {
				pos->py=P;
				Fall(pos);
			} else {
				Delete(pos->son[pos->val<val],val);
				pos->Up();
			}
		}
		void Insert(Node *&pos,Node *goal) {
			if(pos==null)
				pos=goal;
			else {
				Insert(pos->son[pos->val<goal->val],goal);
				pos->Up();//adjust不一定会adjust啊...
				Adjust(pos);
			}
		}
		typedef Node *Iter;		
		Treap():root(null){}
		int Rank(int v) {
			Node *pos=root;int res=0;
			while(pos!=null) {
				if(pos->val<=v) {
					res+=pos->son[0]->sz+pos->cnt;
					pos=pos->son[1];
				} else
					pos=pos->son[0];
			}
			return res;
		}
		void Delete(int val) {
			Delete(root,val);
		}
		void Insert(int val,int cnt) {
			Insert(root,new Node(val,cnt));
		}

		
	};
}using treap::Treap;
namespace segtree {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		Treap idx;
		Node() {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Pool=alloc(Node,SIZE);
			return Pool++;
		}
	};
	struct SegTree {
		typedef Node *Iter;
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node;
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
			}
		}
		void Point(Node *pos,int L,int R,int goal,int v,int cnt) {
			if(v>0) pos->idx.Insert(v,cnt);
			else pos->idx.Delete(-v);
			if(L!=R) {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Point(pos->son[0],L,Mid,goal,v,cnt);
				else
					Point(pos->son[1],Mid+1,R,goal,v,cnt);
			}
		}
		SegTree(){}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Insert(int pos,int idx,int cnt) {
			Point(root,L,R,pos,idx,cnt);
		}
		void Delete(int pos,int idx) {
			Point(root,L,R,pos,-idx,0);
		}
	};
}using segtree::SegTree;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
namespace _ST_ {
	int mdfs[MAXN<<1],lbd[MAXN],rbd[MAXN],mdc,log_2[MAXN<<1],f[MAXLOG][MAXN<<1];
	void ST() {
		log_2[0]=-1;
		for(int i=1;i<=mdc;++i) {
			f[0][i]=mdfs[i];
			log_2[i]=log_2[i>>1]+1;
		}
		for(int lg=1,elg=log_2[mdc];lg<=elg;++lg)
			for(int pl,pr,i=1,ei=mdc-(1<<lg)+1;i<=ei;++i)
				f[lg][i]=dep[pl=f[lg-1][i]]<dep[pr=f[lg-1][i+(1<<lg>>1)]]?pl:pr;
	}
	int LCA(int p1,int p2) {
		p1=lbd[p1],p2=lbd[p2];
		if(p1>p2) swap(p1,p2);
		int lg=log_2[p2-p1+1],pl,pr;
		return dep[pl=f[lg][p1]]<dep[pr=f[lg][p2-(1<<lg)+1]]?pl:pr;
	}
}
using _ST_::LCA;
int dfs[MAXN<<1],dc,lpt[MAXN],rpt[MAXN],fa[MAXN];
void DFS(int pos) {
	using namespace _ST_;
	dfs[++dc]=pos;lpt[pos]=dc;
	mdfs[++mdc]=pos;lbd[pos]=mdc;
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			fa[e->to]=pos;
			dep[e->to]=dep[pos]+1;
			DFS(e->to);
			mdfs[++mdc]=pos;
		}
	dfs[++dc]=pos;rpt[pos]=dc;
	rbd[pos]=mdc;
}
SegTree seg;
void Build() {
	DFS(1);
	new(&seg) SegTree(1,nc);
	_ST_::ST();
	for(int i=1;i<=n;++i) {
		seg.Insert(w[i],lpt[i],1);
		seg.Insert(w[i],rpt[i],-1);
	}
}
int Query(int p1,int p2,int K) {
	int lca=LCA(p1,p2);
	K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
	if(K<=0)
		return 0;
	else {
		int L=1,R=nc;
		SegTree::Iter pos=seg.root;
		while(L!=R) {
			int Mid=(L+R)>>1;
			Treap &idx=pos->son[0]->idx;
			int d=idx.Rank(lpt[p1])+idx.Rank(lpt[p2])-idx.Rank(lpt[lca])-idx.Rank(lpt[fa[lca]]);
			if(K<=d) {
				R=Mid;
				pos=pos->son[0];
			} else {
				K-=d;
				L=Mid+1;
				pos=pos->son[1];
			}
		}
		return L;
	}
	return 23333;
}
void Change(int pos,int newv) {
	seg.Delete(w[pos],lpt[pos]);
	seg.Delete(w[pos],rpt[pos]);
	w[pos]=newv;
	seg.Insert(w[pos],lpt[pos],1);
	seg.Insert(w[pos],rpt[pos],-1);
}
int main() {
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int Q;is>>n>>Q;
	for(int i=1;i<=n;++i) {
		is>>w[i];
		nums[++nc]=w[i];//=i?????????w[i]????
	}
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	static struct {int k,a,b;}opt[MAXN];
	for(int i=1;i<=Q;++i) {
		is>>opt[i].k>>opt[i].a>>opt[i].b;
		if(!opt[i].k)
			nums[++nc]=opt[i].b;
	}
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
	for(int i=1;i<=n;++i)
		w[i]=ref(w[i]);
	Build();
	for(int i=1;i<=Q;++i)
		if(opt[i].k) {
			int Ans=Query(opt[i].a,opt[i].b,opt[i].k);
			if(Ans) os<<nums[Ans]<<'\n';
			else os<<"invalid request!"<<'\n';
		} else {
			Change(opt[i].a,ref(opt[i].b));
		}
	return 0;
}

发表于 | 更新于

Link

被POI的智商题虐惨了，写几道数据结构颐养身心

Solution

就是普普通通的一个套了二分的点分治。 然而大部分人的做法都被hack了。 考虑一道最典型的点分治：楼教主男人八题Tree 我写的做法是在每层点分治，对每个子树双指针+归并。 极端情况：一个点，一个子树有n2\dfrac n2个点，剩下的是n2−1\dfrac n2-1个一个点的子树。而且，链上点的权值都比剩下的一堆点小。那么归并的总复杂度就是O(n24)O(\dfrac {n^2}4)。所以，这种依赖于线性扫描的点分治，一定要先把子节点按照大小/深度排序。

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
#include "lucida"
using std::max;
using std::min;
using std::fill;
using std::sort;
const int MAXN=100000+11;
const double eps=1e-4,inf=1e11;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(){}
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre){}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
}*G[MAXN];
int deg[MAXN];
void Adde(int f,int t,int v)
{
	deg[f]++,deg[t]++;
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
int lbd,ubd,n;
double ratio;
namespace _DC_ {
	int sz[MAXN],dist[MAXN],tol,f[MAXN];
	bool ud[MAXN];
	double amx[MAXN],smx[MAXN];
	int alen,slen;
	void GetSize(int pos,int fa) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				GetSize(u,pos);
				sz[pos]+=sz[u];
			}
	}
	int DP(int pos,int fa) {
		int mxsize=0,res=0;
		f[pos]=tol-sz[pos];
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				int temp=DP(u,pos);
				res=(res==0 || f[res]>f[temp])?temp:res;
				chkmx(mxsize,sz[u]);
			}
		chkmx(f[pos],mxsize);
		return (res==0 || f[res]>f[pos])?pos:res;
	}
	int GC(int pos) {
		tol=sz[pos];
		return tol<lbd?-1:DP(pos,0);
	}
	bool Calc() {
		for(int i=lbd,endi=min(ubd,slen);i<=endi;++i)
			if(smx[i]>=0) return 1;
		static int Q[MAXN],he,ta;
		he=1,ta=0;
		//枚举在左边取长度为i的部分
		//右边取[lbd-i,min(ubd-i,slen)]
		for(int i=min(alen,ubd-1),p=0;i>=1 && lbd<=slen+i;--i) {
			while(p+1<=min(ubd-i,slen)) { 
				++p;
				while(he<=ta && smx[p]>smx[Q[ta]])
					ta--;
				Q[++ta]=p;
			}
			while(Q[he]<lbd-i)	
				he++,assert(he<=ta);
			if(amx[i]+smx[Q[he]]>=0)
				return 1;
		}
		for(int i=1;i<=slen;++i) {
			amx[i]=i>alen?-inf:amx[i];
			chkmx(amx[i],smx[i]);
			smx[i]=-inf;
		}
		chkmx(alen,slen);
		return 0;
	}
	int DFS(int pos,int fa,int dep,double sumv,double ratio) {
		smx[dep]=chkmx(slen,dep)?-inf:smx[dep];
		chkmx(smx[dep],sumv);
		int dist=dep;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				chkmx(dist,DFS(u,pos,dep+1,e->v-ratio+sumv,ratio));
			}
		return dist;
	}
	int Go(int pos,int fa) {
		dist[pos]=0;
		sz[pos]=1;
		int res=0;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				chkmx(res,max(e->v,Go(u,pos)));
				chkmx(dist[pos],dist[u]);
				sz[pos]+=sz[u];
			}
		++dist[pos];
		return res;
	}
	bool cmpDist(const int &x,const int &y) {
		return dist[x]<dist[y];
	}
	double DC(int pos,double preAns) {
		pos=GC(pos);
		if(pos==-1)
			return 0;
		ud[pos]=1;
		
		static int son[MAXN],vtf[MAXN];
		int sc=0;
		double L=preAns,R=0;
		for(Edge *e=G[pos];e;e=e->pre)
			if(!ud[e->to]) {
				chkmx(R,(double)max(e->v,Go(son[++sc]=e->to,0)));
				vtf[e->to]=e->v;
			}
		sort(son+1,son+1+sc,cmpDist);
		while(R-L>eps) {
			bool tak=0;
			double Mid=(L+R)/2;
			alen=slen=0;
			for(int i=1;i<=sc;++i) {
				int u=son[i];
				slen=DFS(u,0,1,vtf[u]-Mid,Mid);
				if(Calc()) {
					tak=1;
					break;
				}
			}
			if(tak)
				L=Mid;
			else
				R=Mid;
		}
		double res=L;
		for(Edge *e=G[pos];e;e=e->pre)
			if(!ud[e->to])
				chkmx(res,DC(e->to,res));
		return res;
	}
}
using namespace _DC_;
int main() {
//	freopen("input","r",stdin);
	is>>n;
	int maxv=0;is>>lbd>>ubd;
	for(int i=1;i<=n-1;++i) {
		int a,b,v;
		is>>a>>b>>v;
		Adde(a,b,v);
		chkmx(maxv,v);
	}
	GetSize(1,0);
	double Ans=DC(1,0);
	printf("%.3lf\n",Ans);
	return 0;
}

发表于 | 更新于

Link

对我来说算神题了

Solution

先考虑暴力做法 枚举每个与模式串的最后一个颜色相同的点，判断是否合法。 判断方法是从这个点向两边分别贪心地匹配两个模式串，找到一个最靠右的左串匹配位置ll，和最靠左的右串匹配位置rr。然后在[1,l−1][1,l-1]和[r+1,n][r+1,n]中找一下是否有两个颜色相同的点。至于找相同，一种方法就是遍历[1,l−1][1,l-1]，把途径的颜色用bool[]标记，然后再遍历[r+1,n][r+1,n]。 可以看出，这样又做了很多无用功，因为很有可能连续的一段区间，向左右匹配的位置都是相同的。这样就不好了。 所以考虑对这个量进行预处理。然后我就怎么也想不出来了。研究一番Claris巨神的代码，并看不懂复杂度。写完A掉之后，忽然灵光一现，不禁拍案叫绝。 设原序列为c[]c[]，左模式串的序列为x[]x[]。假设当前在计算ls[]ls[]，ls[i]ls[i]表示使得c[]c[]的[a,i−1][a,i-1]中存在一个子序列x[]x[]，且最大的aa，设first[p]first[p]表示在c[]c[]中的第一个颜色pp的位置，next[i]next[i]表示序列c[]c[]中下一个与c[i]c[i]颜色相同的位置。 外层循环从[1,n][1,n]枚举c[]c[]的每一个位置ii，设f[p]f[p]表示使得[a,i−1][a,i-1]能成功匹配x[p..x.length]x[p..x.length]的最大的aa。 然后循环这样做： (在代码中，lx==x.length−1lx==x.length-1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=n;++i) {
    ls[i]=f[1];
    if(c[i]==x[lx]) {
        f[lx]=i;
        for(int u,p=lx-1;p;--p) {
            if((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]) {
                do f[p]=u;
                while((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]);
            } else
                break;
        }
    }
}

如果x[]x[]的倒数第二个字符与c[i]c[i]相同，那就更新f[lx]f[lx]。然后pp从lx−1lx-1开始枚举，将f[p]f[p]挪到最后一个在f[p+1]f[p+1]之前的颜色为x[p]x[p]的位置。 复杂度？ 设x[p]x[p]在c[]c[]中出现了t[x[p]]t[x[p]]次，那么f[p]f[p]至多会向后移动tt次。而x[]x[]的元素互异，那么复杂度就是O(∑t[x[i]])=O(n)O(\sum t[x[i]])=O(n) 处理出来之后，可以发现，随着枚举点ii右移，ls[i]ls[i]和rs[i]rs[i]都是单调不降的。因此可以类比莫队，实现O(n)O(n)计算。 记得特判模式串为11的情况

Tips

唯有泪千行。。 KMP--一个指针的均摊--O(n)O(n) 双指针--两个指针的均摊--O(n)O(n) K指针--K个指针的均摊--O(n)O(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
#include "lucida"
const int MAXN=1000000+11;
using std::reverse;
int K;
void Calc(int c[],int n,int x[],int lx,int ls[]) {
	//处理出 ls[i] 表示i左边的最靠右的匹配
	static int f[MAXN],next[MAXN],first[MAXN];
	if(!lx) {
		for(int i=1;i<=n;++i)
			ls[i]=i;
	} else {
		for(int i=1;i<=K;++i)
			first[i]=n+1;
		for(int i=n;i>=1;--i) {
			next[i]=first[c[i]];
			first[c[i]]=i;
			f[i]=0;
		}
		for(int i=1;i<=n;++i) {
			ls[i]=f[1];
			if(c[i]==x[lx]) {
				f[lx]=i;
				for(int u,p=lx-1;p;--p) {
					if((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]) {
						do f[p]=u;
						while((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]);
					} else
						break;
				}
			}
		}
	}
}

int cnt,val[MAXN][2],n;
void Modify(int pos,int d,int v) {
	if(pos==0 || pos==n+1)
		return;
	val[pos][d]+=v;
	if(v>0 && val[pos][d]==1 && val[pos][d^1])
		cnt++;
	if(v<0 && val[pos][d]==0 && val[pos][d^1])
		cnt--;
}
int main() {
//	freopen("input","r",stdin);
	static int Ans[MAXN],x[MAXN],y[MAXN],c[MAXN],ls[MAXN],rs[MAXN];
	int ac=0,lx,ly;is>>n>>K;
	for(int i=1;i<=n;++i) is>>c[i];
	is>>lx>>ly;
	for(int i=1;i<=lx;++i) is>>x[i];
	for(int i=1;i<=ly;++i) is>>y[i];
	Calc(c,n,x,lx-1,ls);
	reverse(c+1,c+1+n);
	Calc(c,n,y,ly-1,rs);
	reverse(c+1,c+1+n);
	reverse(rs+1,rs+1+n);
	for(int i=1;i<=n;++i) rs[i]=n-rs[i]+1;
	for(int p=1;p<ls[1];++p) 
		Modify(c[p],0,1);
	for(int p=rs[1]+1;p<=n;++p) 
		Modify(c[p],1,1);
	if(c[1]==x[lx] && cnt)
		Ans[++ac]=1;
	
	for(int i=2;i<=n;++i) {
		for(int p=ls[i-1];p<=ls[i]-1;++p)
			Modify(c[p],0,1);
		for(int p=rs[i-1]+1;p<=rs[i];++p)
			Modify(c[p],1,-1);
		if(c[i]==x[lx] && cnt)
			Ans[++ac]=i;
	}
	os<<ac<<'\n';
	for(int i=1;i<=ac;++i)
		os<<Ans[i]<<(i==ac?"":" ");
	//os<<'\n';
	return 0;
}
/*
 * Wa 没有特判1 
 */

发表于 | 更新于

Link

Solution

真的是叶节点！好吧当我没说 只要知道某一条边需要多少蚂蚁流过就可以了，然而这个流量的取值是一个区间，所以要维护一个区间。一开始naive只维护了最小值。 如果知道了一个点的树边上需要流[l,r][l,r]，那么这个点就需要有[deg[u]∗l,(deg[u]+1)∗r−1][deg[u]*l,(deg[u]+1)*r-1]，它下面的边需要有[(deg[u]−1)∗l,(deg[u]−1)∗(r+1)−1][(deg[u]-1)*l,(deg[u]-1)*(r+1)-1]。 注意，即使不乘kk，合法的群数也会爆int。

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
#include "lucida"
using std::sort;
using std::lower_bound;
using std::upper_bound;
const int MAXN=1000000+11;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
};
struct EdgeList {
	Edge *head;int deg;
	void App(int to) {
		head=new Edge(to,head);
		++deg;
	}
	operator Edge*() {
		return head;
	}
}G[MAXN];
void Adde(int f,int t) {
	G[f].App(t);
	G[t].App(f);
}
int UPLIM,c[MAXN],cc;
int count(int64 L,int64 R) {
	/*int cnt=0;
	for(int i=L;i<=R;++i)
		cnt+=ext[i];*/
	int p1=lower_bound(c+1,c+1+cc,L)-c,
		p2=upper_bound(c+1,c+1+cc,R)-c-1;
	if(p1==cc+1)
		return 0;
	else
		return p2-p1+1;
}
bool ud[MAXN];
int64 DFS(int pos,int64 lbd,int64 ubd) {

//	os<<'{'<<pos<<'}'<<lbd<<' '<<ubd<<'\n';

	if(lbd>UPLIM)
		return 0;
	chkmn(ubd,(int64)UPLIM);
	ud[pos]=1;
	int64 res=(G[pos].deg==1?count(lbd*G[pos].deg,(ubd+1)*G[pos].deg-1):0);
	lbd=lbd*(G[pos].deg-1);
	ubd=(ubd+1)*(G[pos].deg-1)-1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(!ud[e->to]) {
			int u=e->to;
			res+=DFS(u,lbd,ubd);
		}
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,K;is>>n>>cc>>K;
	for(int i=1;i<=cc;++i) {
		is>>c[i];
		//ext.Insert(c[i]);ext[c[i]]=1;
		chkmx(UPLIM,c[i]);
	}
	sort(c+1,c+1+cc);
	int from,to;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
		if(i==1) {
			from=x;
			to=y;
		}
	}
	int64 Ans=0;
	ud[from]=1,ud[to]=0;Ans+=DFS(to,K,K);
	ud[to]=1,ud[from]=0;Ans+=DFS(from,K,K);
	os<<(int64)Ans*K<<'\n';
	return 0;
}
/*
 * 题意读错了
 * 数量爆ll了
 */