20230905 比赛总结

反思

B

没有想好就开始写，于是重构了
且犯了数组越界的 sb 错误

C

过度沉迷于写正解，而不写暴力

D

$dp$ 套路见识得太少了！

题解

比赛链接

A

傻子题

B

我是傻子

C

看到子树内距离其不超过 $k$ 的点，有一个套路是主席树 $+dfs$ 序，即在主席树的第 $depth[x]+k$ 层查询区间 $[L[x],R[x]]$
看到数同构，考虑数哈希，当然，用到上面的技巧的话，可以把树哈希变成序列哈希，然后就会简单且精确很多
考虑第一个 $trick$ 放到线段树上维护哈希，然后就可以二分做了
时间复杂度 $O(nlo{g}^{2}n)$

#include 
using namespace std;
const int N=100100;
typedef unsigned long long ull;
vector<int> T[N];
int n,s[N];
int depth[N],mxd[N],dfnL[N],dfnR[N],dfs_clock;
vector<int> d[N];
struct Node{
	int lc,rc,sum;
	ull h;
}seg[N*4+N*20];
int idx,root[N];
ull pw[N],P=131;
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
void dfs(int u,int fa){
	depth[u]=depth[fa]+1,mxd[u]=depth[u];
	dfnL[u]=++dfs_clock;
	d[depth[u]].push_back(u);
	for(int v:T[u]) if(v!=fa) dfs(v,u),mxd[u]=max(mxd[u],mxd[v]);
	dfnR[u]=dfs_clock;
}
int build(int l,int r){
	int p=++idx;
	if(l==r) return p;
	int mid=(l+r)>>1;
	seg[p].lc=build(l,mid),seg[p].rc=build(mid+1,r);
	return p;
}
void merge(Node &rt,Node lc,Node rc){ rt.sum=lc.sum+rc.sum,rt.h=rc.h+lc.h*pw[rc.sum];}
int insert(int p,int l,int r,int pos,int val){
	int q=++idx;seg[q]=seg[p];
	if(l==r){ seg[q].h=val,seg[q].sum=1;return q;}
	int mid=(l+r)>>1;
	if(mid>=pos) seg[q].lc=insert(seg[p].lc,l,mid,pos,val);
	else seg[q].rc=insert(seg[q].rc,mid+1,r,pos,val);
	merge(seg[q],seg[seg[q].lc],seg[seg[q].rc]);
    // cout<
    return q;
}
Node query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R) return seg[p];
	int mid=(l+r)>>1;
	if(mid>=L&&mid<R){
		Node lf=query(seg[p].lc,l,mid,L,R);
		Node ri=query(seg[p].rc,mid+1,r,L,R);
		merge(lf,lf,ri);
		return lf;
	}
	if(mid>=L) return query(seg[p].lc,l,mid,L,R);
	return query(seg[p].rc,mid+1,r,L,R);
}
bool check(int mid){
	set<ull> se;
	int cnt=0;
	for(int i=1;i<=n;i++) if(depth[i]+mid<=mxd[i])
		cnt++,se.insert(query(root[depth[i]+mid-1],1,n,dfnL[i],dfnR[i]).h);
	return cnt!=se.size();
}
int main(){
    freopen("ernd.in","r",stdin);
    freopen("ernd.out","w",stdout);
	n=read();
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*P;
	for(int i=1;i<=n;i++){
		s[i]=read();
		for(int j=1;j<=s[i];j++) T[i].push_back(read());
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		for(int j:d[i]) root[i]=insert(root[i],1,n,dfnL[j],s[j]);
	}
	int l=0,r=n;
	while(l<r-1){
		int mid=(l+r)>>1;
		check(mid)?l=mid:r=mid;
	}
	printf("%d",l);
	return 0;
}

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

D

nb 题！
我一开始以为求本质不同的子序列个数很不可做，后来才发现是我傻逼了
考虑 $d{p}_i$ 表示到 $i$ 的本质不同的子序列个数
考虑如果 $a_i$ 之前未出现过，那么显然所有前面的子序列都可以在后面接上 $a_i$，所以 $d{p}_i=2d{p}_{i-1}+1$
如果 $a_i$ 之前出现过，考虑最后一个出现的位置 $j$，那么在 $j-1$ 前面的子序列后面添上 $a_i$ 就重复了，所以 $d{p}_i=2d{p}_{i-1}-d{p}_{j-1}$
这样可以 $O(n^2)$ 做

考虑 $k$ 的范围极小，所以整个 $dp$ 的过程可以用矩乘优化
区间查询用线段树维护矩乘即可
考虑区间加操作，那么 $k$ 个数一定会形成一个置换，这个可以通过改变转移矩阵的方式进行修改
考虑区间乘操作
当 $k\ne 4$ 时，$k$ 个数一定会形成一个置换，那么和区间加的方法一样改矩阵
这里要注意乘 $0$ 的情况需要特判，预处理出长度为 $i$ 的区间全是 $0$ 的转移矩阵即可
当 $k=4$ 且 $\ast 2$ 时，就比较恶心，因为 $0,2$ 会变成 $0$，$1,3$ 会变成 $2$，所以考虑再维护两个矩阵分别表示区间中 $0,2$ 变成 $0$，$1,3$ 变成 $2$ 的矩阵 和 区间中 $0,2$ 变成 $2$，$1,3$ 变成 $0$ 的矩阵
为什么要维护后面的矩阵，因为当 $+2$ 时，需要交换两个矩阵，这个可以自己体会

时间复杂度 $O(q{k}^{3}logn)$

#include 
using namespace std;
const int P=998244353;
const int N=30100;
struct Matrix{ int n,m,a[6][6];};
Matrix operator *(const Matrix &A,const Matrix &B){
	Matrix C;C.n=A.n,C.m=B.m;
	memset(C.a,0,sizeof(C.a));
	for(int i=0;i<C.n;i++) for(int j=0;j<C.m;j++)
		for(int k=0;k<A.m;k++) C.a[i][j]=(C.a[i][j]+1ll*A.a[i][k]*B.a[k][j])%P;
	return C;
}
Matrix mul0[N],mul2[N];
int n,K,m,v[N];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
Matrix ID(){
	Matrix ret;ret.n=K+1,ret.m=K+1;
	memset(ret.a,0,sizeof(ret.a));
	for(int i=0;i<=K;i++) for(int j=0;j<=K;j++) ret.a[i][j]=1;
	return ret;
}
Matrix ONLYMAT(int col){
	Matrix ret;ret.n=K+1,ret.m=K+1;
	memset(ret.a,0,sizeof(ret.a));
	for(int i=0;i<K;i++)
		if(i!=col) ret.a[i][i]=1;
		else ret.a[K][i]=1;
	ret.a[K][K]=2,ret.a[col][K]=P-1;
	return ret;
}
struct SegmentTree{
	Matrix sum[N<<2],g[N<<2][2];
	//g[][0]:0,2全部变成0 且 1,3全部变成2 之后的矩阵
	//g[][1]:0,2全部变成2 且 1,3全部变成0 之后的矩阵
	int tagadd[N<<2],tagmul[N<<2],len[N<<2];
    void build(int l,int r,int x){
        tagadd[x]=0,tagmul[x]=1,len[x]=r-l+1;
        if(l==r){
			sum[x]=ONLYMAT(v[l]);
			if(K==4){
				if(!v[l]||v[l]==2) g[x][0]=ONLYMAT(0),g[x][1]=ONLYMAT(2);
				else g[x][0]=ONLYMAT(2),g[x][1]=ONLYMAT(0);
			}
			return;
		}
        int mid=(l+r)>>1;
        build(l,mid,x<<1),build(mid+1,r,x<<1^1);
        sum[x]=sum[x<<1]*sum[x<<1^1];
		if(K==4) g[x][0]=g[x<<1][0]*g[x<<1^1][0],g[x][1]=g[x<<1][1]*g[x<<1^1][1];
    }
	void downadd(int x,int val){
		if(!val) return;
		tagadd[x]+=val;
		if(tagadd[x]>=K) tagadd[x]-=K;
		if(K==4&&val!=2) swap(g[x][0],g[x][1]);
		int mat[6][6];
		for(int i=0;i<=K;i++) for(int j=0;j<=K;j++) mat[i][j]=sum[x].a[i][j];
		for(int i=0;i<K;i++){
			int ti=(i+val)%K;
			for(int j=0;j<K;j++){
				int tj=(j+val)%K;
				sum[x].a[ti][tj]=mat[i][j];
			}
			sum[x].a[ti][K]=mat[i][K],sum[x].a[K][ti]=mat[K][i];
		}
	}
	void downmul(int x,int val){
		tagmul[x]=tagmul[x]*val%K,tagadd[x]=tagadd[x]*val%K;
		if(K==4&&val==2){//不形成一个置换
			sum[x]=g[x][0],g[x][0]=mul0[len[x]],g[x][1]=mul2[len[x]];
			return;
		}
        if(!val){
			sum[x]=mul0[len[x]];
			if(K==4) g[x][0]=mul0[len[x]],g[x][1]=mul2[len[x]];
			return;
		}
		int mat[6][6];
		for(int i=0;i<=K;i++) for(int j=0;j<=K;j++) mat[i][j]=sum[x].a[i][j];
		for(int i=0;i<K;i++){
			int ti=i*val%K;
			for(int j=0;j<K;j++){
				int tj=j*val%K;
				sum[x].a[ti][tj]=mat[i][j];
			}
			sum[x].a[ti][K]=mat[i][K],sum[x].a[K][ti]=mat[K][i];
		}
	}
	void pushdown(int x){
		downmul(x<<1,tagmul[x]),downmul(x<<1^1,tagmul[x]);
		downadd(x<<1,tagadd[x]),downadd(x<<1^1,tagadd[x]);
		tagadd[x]=0,tagmul[x]=1;
	}
	void modify(int l,int r,int x,int L,int R,int val,int type){
		if(L<=l&&r<=R){
			if(!type) downadd(x,val);
			else downmul(x,val);
			return;
		}
		pushdown(x);
		int mid=(l+r)>>1;
		if(mid>=L) modify(l,mid,x<<1,L,R,val,type);
		if(mid<R) modify(mid+1,r,x<<1^1,L,R,val,type);
        sum[x]=sum[x<<1]*sum[x<<1^1];
		if(K==4) g[x][0]=g[x<<1][0]*g[x<<1^1][0],g[x][1]=g[x<<1][1]*g[x<<1^1][1];
	}
	Matrix query(int l,int r,int x,int L,int R){
		if(L<=l&&r<=R) return sum[x];
		pushdown(x);
		int mid=(l+r)>>1;
		if(mid>=L&&mid<R) return query(l,mid,x<<1,L,R)*query(mid+1,r,x<<1^1,L,R);
		if(mid>=L) return query(l,mid,x<<1,L,R);
		return query(mid+1,r,x<<1^1,L,R);
	}
}sg;
void work(){
	n=read(),K=read(),m=read();
	for(int i=1;i<=n;i++) v[i]=read();
	mul0[0]=ID(),mul0[1]=ONLYMAT(0);
    for(int i=2;i<=n;i++) mul0[i]=mul0[1]*mul0[i-1];
	mul2[0]=ID(),mul2[1]=ONLYMAT(2);
	for(int i=2;i<=n;i++) mul2[i]=mul2[1]*mul2[i-1];
    sg.build(1,n,1);
	for(int i=1;i<=m;i++){
		int op=read(),l=read(),r=read();
		if(op==1) sg.modify(1,n,1,l,r,read(),0);
		else if(op==2) sg.modify(1,n,1,l,r,read(),1);
		else{
			Matrix A;A.n=1,A.m=K+1;A.a[0][K]=0;
			for(int j=0;j<K;j++) A.a[0][j]=P-1;
			A=A*sg.query(1,n,1,l,r);
			printf("%d\n",A.a[0][K]);
		}
	}
}
int main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
	int T=read();
	while(T--) work();
	return 0;
}

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