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

联测20 回忆旅途的过往"/>

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

题目大意

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

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

a i a_i ai​和所有 x x x都小于等于 m m m。

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

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

1 ≤ n , q ≤ 1 0 6 , 1 ≤ m ≤ 1 0 5 1\leq n,q\leq 10^6,1\leq m\leq 10^5 1≤n,q≤106,1≤m≤105

时间限制 2500 m s 2500ms 2500ms，空间限制 256 M B 256MB 256MB。

题解

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

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

这样做的话，空间复杂度是 O ( m 2 v + n ) O(m2^v+n) O(m2v+n)的，数组开不下，所以背包要用 b i t s e t bitset bitset来存。

总时间复杂度为 O ( m 2 v + n log ⁡ n ) O(m2^v+n\log n) O(m2v+nlogn)，空间复杂度为 O ( m 2 v 64 + n ) O(\dfrac{m2^v}{64}+n) O(64m2v​+n)。

code

#include<bits/stdc++.h>
#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;
}