回忆旅途的过往
题大意
有 \(n\) 个砝码，每个砝码都有初始重量 \(a_i\) 。 \(Q\) 次操作，每次操作有以下两种
- \(1，l,r,x\)：表示把 \(l\) 到 \(r\) 的所有 \(a_i\) 变成 \(x\)
- \(2 , l , r , x\) ：查询 \([l, r]\) 的所有砝码，每个砝码可以使用无限次，是否能称出重量 \(x\)
\(a_i , x \le m\)
保证 \(a_i , x\) 种数不超过 \(10\)
\(n , Q \le 10^6 , m \le 10^5\)
思路
因为 \(a_i , x\) 的种数不超过 $10 $ ， \(m\le 10^5\)
所以考虑 $O(2^{10} * m) $ 把所有情况的答案都预处理出来
然后用一棵线段树维护区间有什么数。
用二进制实现
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define lp p << 1
#define rp p << 1 | 1
using namespace std;
const int N = 1e6 + 5 , M = 1e5 + 5;
int n , m , Q , vis[N] , tot , cnt , a[N];
bitset<N> ans[2000];
struct Tr {
int val , lzy;
} tr[N << 2];
void pushdown (int p) {
if (!tr[p].lzy) return;
tr[lp].lzy = tr[rp].lzy = tr[p].lzy;
tr[lp].val = tr[rp].val = tr[p].lzy;
tr[p].lzy = 0;
}
void change (int p , int l , int r , int L , int R , int x) {
if (L <= l && R >= r)
tr[p].val = tr[p].lzy = 1 << (x - 1);
else {
pushdown (p);
int mid = l + r >> 1;
if (L <= mid) change (lp , l , mid , L , R , x);
if (mid < R) change (rp , mid + 1 , r , L , R , x);
tr[p].val = tr[lp].val | tr[rp].val;
}
}
int query (int p , int l , int r , int L , int R) {
if (L <= l && R >= r)
return tr[p].val;
else {
pushdown (p);
int mid = l + r >> 1 , ans1 = 0;
if (L <= mid) ans1 = query (lp , l , mid , L , R);
if (mid < R) ans1 |= query (rp , mid + 1 , r , L , R);
return ans1;
}
}
void add (int x) {
if (vis[x]) return;
vis[x] = ++tot;
fu (i , (1 << (tot - 1)) , (1 << tot) - 1) {
ans[i] = ans[i - (1 << (tot - 1))];
fu (j , x , m) {
ans[i][j] = ans[i][j] | ans[i][j - x];
}
}
}
int main () {
int t , opt , l , r , x;
ans[0][0] = 1;
scanf ("%d%d%d" , &n , &m , &Q);
fu (i , 1 , n) scanf ("%d" , &a[i]) , add (a[i]);
fu (i , 1 , n)
change (1 , 1 , n , i , i , vis[a[i]]);
int ans1 = 0;
while (Q --) {
scanf ("%d%d%d%d" , &opt , &l , &r , &x);
if (opt == 1) {
ans1 ++;
if (ans1 == 3)
ans1 --;
if (!vis[x]) add (x);
change (1 , 1 , n , l , r , vis[x]);
}
else {
ans1 ++;
if (ans1 == 2)
ans1 --;
t = query (1 , 1 , n , l , r);
puts (ans[t].test (x) ? "Yes" : "No");
}
}
return 0;
}