test20190904

发表于

闲扯

噫，好，我上当了。

今天的 $T1$ 标题叫树链剖分，按理说肯定正解不是它，但我还是打了。。。

$T2$ 打表的时候出了点问题，最前面两个是直接放在两个端点的，不是用来切的，做题的时候想到了，但打代码就忘了。。。不过虽然规律找错了，但是差别不大，只错了一个点，还有就是 $10^{1000}$ 次方有 $1001$ 位。。。

$T3$ 写的暴力，不过貌似打炸了。。最近做题打暴力的能力欠缺啊。。

题面

题面

$T1$

Solution

对于 $n\leq 10^5$ 的点，我们可以直接上树剖。

根据 $dfn$ ，我们可以知道，一个节点的祖先节点的编号一定是离自己越近就越大的，所以就直接维护最大值即可。

对于 $n\leq 10^6$ 的点，就不能这样了，肯定会 $TLE$ 。

先考虑直接指定有哪些点被选中时怎么做。

因为深度越大，节点的优先级越高，所以我们可以从下往上来统计每个点的管辖范围。

这相当于把这棵树分为几个连通子树，每一个子树的根节点就是这个子树中所有节点的答案。

明显，我们可以用并查集来维护连通性和相应的根节点。

那么动态加点怎么做？

如果我们是顺着来，那么加入一个新节点后，我们需要把它从原来的子树中切出来，不是很好维护。

既然顺着不行，那我们就试试反着来

考虑先维护好加入所有边之后的情况。

如果要查询，可以直接查所在子树的根结点。

如果要修改，那么等价于把一条点给删去。那么它所控制的范围就会并入它父节点所在子树的根结点的管辖范围。这个可以直接把下面的合并到上面去，可以用并查集轻松维护。

这样，问题就变得很简单了。

$ps:$ 数据有锅，可能重复加入同一个节点。对于后面的操作，我们直接忽略掉，不然会对答案造成影响。

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e6+5;
int n,m,opt,u,f[MAXN],fa[MAXN],s1,s2,stk[MAXN*5],top,cnt;
struct Node{
	int opt,u;
}node[MAXN*5];
it find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
il merge(int x,int y){
	ri fx=find(x),fy=find(y);
	if(fx==fy) return ;
	fa[fx]=fy;
}
bool tr[MAXN];
int main()
{
	freopen("decomposition.in","r",stdin);
	freopen("decomposition.out","w",stdout);
	read(n),read(m),tr[1]=1;
	for(ri i=1;i<=n;++i) fa[i]=i;
	for(ri i=2;i<=n;++i) read(f[i]);
	for(ri i=1;i<=m;++i){
		read(opt),read(u);
		if(opt==2&&tr[u]) continue;
		node[++cnt].opt=opt,node[cnt].u=u;
		if(node[cnt].opt==2) tr[node[cnt].u]=1;
	}
	for(ri i=1;i<=n;++i) if(!tr[i]) merge(i,f[i]);
	for(ri i=cnt;i;--i){
		opt=node[i].opt,u=node[i].u;
		if(opt==1) stk[++top]=find(u);
		if(opt==2) merge(u,f[u]);
	}
	while(top){
		ri k=stk[top--];
		s1=(1ll*s1*37+k)%19260817,s2=(1ll*s2*137+k)%998244353;
	}
	print(s1),putchar(' '),print(s2);
	return 0;
}

$T2$

Solution

打表，我们可以发现，除开前 $5$ 个数之外，后面的数就变得很有规律了。

从第 $6$ 个答案开始，序列就变成了很多段连续的自然数。

观察首尾，可以发现在结尾处的点编号都是 $2^k+1$ ，而对应的答案是 $2^{k+1}+1$ 。

再简单推一下，可以发现这一段中所有数的答案都可以写成 $2^{k+1}+n$ 。其中 $k$ 是第一个使 $2^{k+1}+1$ 大于 $n$ 的数。

然后就可以直接从前向后枚举，找到第一个 $k$ ，然后计算答案即可。

因为极限数据是 $10^{1000}$ ，所以我们需要打个高精度。但是注意我们找到的 $k$ 可能会使 $2^{k+1}+1$ 的位数变为 $1001$ 位，所以高精数组需要用 $1001$ 位。

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
char s[1050];
short ans[1050],bas[1050],val[1050],tmp[1050];
ll n;
inl bool check(){
	for(ri i=1;i<=1001;++i) tmp[i]=bas[i];
	tmp[1001]+=1;
	for(ri i=1001;i;--i) if(tmp[i]>=10) tmp[i]%=10,tmp[i-1]++;
	for(ri i=1;i<=1001;++i){
		if(tmp[i]>val[i]) return true;
		if(val[i]>tmp[i]) return false;
	}
	return true;
}
il solve(){
	for(ri i=1;i<=1001;++i) ans[i]=bas[i]+val[i];
	for(ri i=1001;i;--i) if(ans[i]>=10) ans[i]%=10,ans[i-1]++;
	ri pos=0;
	for(ri i=1;i<=1001;++i) if(ans[i]>0){pos=i;break;}
	for(ri i=pos;i<=1001;++i) print(ans[i]);
}
int main()
{
	freopen("tenki.in","r",stdin);
	freopen("tenki.out","w",stdout);
	scanf("%s",s+1);
	ri len=strlen(s+1);
	if(len<=19){
		for(ri i=1;i<=len;++i) n=(n<<1)+(n<<3)+s[i]-'0';
		
		if(n==1) print(1);
		else if(n==2) print(3);
		else if(n==3) print(5);
		else if(n==4) print(8);
		else if(n==5) print(9);
		else{
			rl bas=4;
			for(ri i=3;i<=62;++i){
				bas<<=1;
				if(bas+1>=n){
					print(bas+n);
					return 0;
				}
			}
		}
	
	}
	else{
		for(ri i=len;i;--i) val[1001-len+i]=s[i]-'0';
		bas[1001]=4;
		for(ri i=3;i<=3322;++i){
			for(ri i=1001;i;--i) bas[i]*=2;
			for(ri i=1001;i;--i) if(bas[i]>=10) bas[i]%=10,bas[i-1]++;
			if(check()){
				solve();
				return 0;
			}
		}
	}
	return 0;
}

$T3$

Solution

加入一个点 $y$ ，等价于给 $y$ 到根的路径上所有边加一个权值。

设这条边是 $f\to u$ ，那么加的权值就是 $F(dist[u])-F(dist[f])$ 。

询问时查询 $x$ 到根路径上的所有边权值之和，即差分之和。

对于 $F$ ，我们用线性筛预处理，可以快速求解。

时间复杂度： $O(D+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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
inline int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		b>>=1;
		a=mul(a,a);
	}
	return res;
}
const int N=1e7;
int k;
int prime[N+10],pcnt=0,ism[N+10],phi[N+10],sumphi[N+10];
int pw[N+10];
void Init_Linear()
{
	ism[1]=1;
	pw[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!ism[i])
		{
			prime[++pcnt]=i;
			pw[i]=fpow(prime[pcnt],k);
		}
		for(int j=1;j<=pcnt && i<=N/prime[j];++j)
		{
			ism[i*prime[j]]=1;
			pw[i*prime[j]]=mul(pw[i],pw[prime[j]]);
			if(i%prime[j]==0)
				break;
		}
	}	
	for(int i=2;i<=N;++i)
		pw[i]=add(pw[i-1],pw[i]);
}
const int MAXN=1e5+10;
int n,m;
int ecnt=0,head[MAXN],to[MAXN],nx[MAXN];
int val[MAXN],dist[MAXN];
void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
int siz[MAXN],fa[MAXN],mxson[MAXN],top[MAXN];
int idx=0,dfn[MAXN],rnk[MAXN];
void dfs1(int u,int f)
{
	fa[u]=f;
	siz[u]=1;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dist[v]=dist[u]+val[i];
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	dfn[u]=++idx;
	rnk[idx]=u;
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v!=fa[u] && v!=mxson[u])
			dfs2(v,v);
	}
}
struct Segtree
{
	struct node
	{
		int del,sum;
		int tag;	
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.del=add(lson.del,rson.del);
		root.sum=add(lson.sum,rson.sum);
	}
	void BuildTree(int o,int l,int r)
	{
		root.tag=0;
		if(l==r)
		{
			root.del=add(pw[dist[rnk[l]]],P-pw[dist[fa[rnk[l]]]]);
			root.sum=0;
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void Modify(int o,int c)
	{
		root.sum=add(root.sum,mul(root.del,c));
		root.tag+=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			Modify(o<<1,root.tag);
			Modify(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void upd(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
		{
			Modify(o,1);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root.sum;
		int mid=(l+r)>>1;
		pushdown(o);
		int res=0;
		if(L<=mid)
			res=add(res,query(o<<1,l,mid,L,R));
		if(R>mid)
			res=add(res,query(o<<1|1,mid+1,r,L,R));
		return res;
	}
}T;
void init()
{
	dfs1(1,0);
	dfs2(1,1);
	T.BuildTree(1,1,n);
}
bool vis[MAXN];
void upd(int x)
{
	if(vis[x])
		return;
	vis[x]=true;
	while(x)
	{
		T.upd(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
}
int query(int x)
{
	int res=0;
	while(x)
	{
		res=add(res,T.query(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	return res;
}
int main()
{
	freopen("mafumafu.in","r",stdin);
	freopen("mafumafu.out","w",stdout);
	n=read(),m=read(),k=read();
	Init_Linear();
	for(int i=2;i<=n;++i)
	{
		int f=read();
		int d=read();
		addedge(f,i,d);
	}
	init();
	for(int i=1;i<=m;++i)
	{
		int op=read(),x=read();
		if(op==1)
			upd(x);
		else
			printf("%d\n",query(x));
	}
	return 0;
}

总结

做题还是不够熟练，经验不够。