CSP模拟58联测20 回忆旅途的过往

题目大意

有$n$个砝码，每个砝码的初始重量为$a_i$。有$q$次操作，每次操作分为以下两种类型：

• 1 l r x：表示将$l$到$r$之间的所有$a_i$都变成$x$
• 2 l r x：查询$l$到$r$之间的所有砝码，每个砝码可以用无限次，求是否能称出质量$x$

$a_i$和所有$x$都小于等于$m$。

保证$a_i$和所有操作一的$x$总共最多不超过$10$种数。

注意砝码只能放在同一侧。

$1\le n,q\le 10^6,1\le m\le 10^5$

时间限制$2500ms$，空间限制$256MB$。

题解

设砝码质量的种数为$v$，依照题意，$v\le 10$。我们对于每种数取或者不取，总共有$2^v$种情况。对每种情况做一次背包，每种情况可以在之前的基础上再加一个砝码的贡献而得出，所以这部分的时间复杂度为$O(m{2}^v)$。

然后，用线段树维护每一段有哪几种数。因为数的种数只有不超过$10$种，所以可以将每一段有的数进行状态压缩。那么操作一就是区间修改，操作二就是在查询对应区间中有的数的状态，并将状态在背包中查询是否可以达到即可。这部分的时间复杂度为$O(n\log n)$。

这样做的话，空间复杂度是$O(m{2}^v+n)$的，数组开不下，所以背包要用$bitset$来存。

总时间复杂度为$O(m{2}^v+n\log n)$，空间复杂度为$O(\frac{m{2}^v}{64}+n)$。

code

#include
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=1000000,M=100000;
int n,m,q,v1=0,a[N+5],z[M+5],v[15],ct[1<<10],tr[4*N+5],ly[4*N+5];
bitset<M+5>f[1505];
struct node{
	int tp,l,r,x;
}w[N+5];
int lb(int i){
	return i&(-i);
}
void build(int k,int l,int r){
	if(l==r){
		tr[k]=1<<z[a[l]]-1;
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);build(rc,mid+1,r);
	tr[k]=tr[lc]|tr[rc];
}
void down(int k){
	tr[lc]=tr[rc]=ly[lc]=ly[rc]=ly[k];
	ly[k]=0;
}
void ch(int k,int l,int r,int x,int y,int v){
	if(l>=x&&r<=y){
		tr[k]=ly[k]=1<<v-1;
		return;
	}
	if(ly[k]) down(k);
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x,y,v);
	if(y>mid) ch(rc,mid+1,r,x,y,v);
	tr[k]=tr[lc]|tr[rc];
}
int find(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y) return tr[k];
	if(ly[k]) down(k);
	int mid=(l+r)>>1,re=0;
	if(x<=mid) re|=find(lc,l,mid,x,y);
	if(y>mid) re|=find(rc,mid+1,r,x,y);
	return re;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0;i<=10;i++) ct[1<<i]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!z[a[i]]){
			z[a[i]]=++v1;v[v1]=a[i];
		}
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d%d",&w[i].tp,&w[i].l,&w[i].r,&w[i].x);
		if(w[i].tp==1&&!z[w[i].x]){
			z[w[i].x]=++v1;v[v1]=w[i].x;
		}
	}
	f[0][0]=1;
	for(int s=1;s<1<<v1;s++){
		int t=lb(s),w=ct[t]+1;
		f[s]=f[s^t];
		for(int i=v[w];i<=m;i++){
			f[s][i]=f[s][i]|f[s][i-v[w]];
		}
	}
	build(1,1,n);
	for(int i=1;i<=q;i++){
		if(w[i].tp==1) ch(1,1,n,w[i].l,w[i].r,z[w[i].x]);
		else{
			int tmp=find(1,1,n,w[i].l,w[i].r);
			if(f[tmp][w[i].x]) printf("Yes\n");
			else printf("No\n");
		}
	}
	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