【連結】
http://codeforces.com/contest/981/problem/E
【題意】
給定q個區間加的操作,求出這q個操作的所有子集的所有最大值,在[1,n]的範圍内
【分析】
要知道一個數能否可由某個操作集得到,隻要知道對于某個位置上的數的操作中能否構成這個數(好像口胡了)。
對于一個數,我們可以知道能對它進行的所有操作,這個數你組成的數的所有可能性就是個01背包了。但是資料範圍過大,考慮用bitset+線段樹區間加優化,詢問的時候也是線段樹從上到下維護一下。
關于bitset優化01背包問題,可以先看看https://blog.csdn.net/running_acmer/article/details/82953492
【代碼】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 6;
vector<int>v[maxn << 2];
bitset<maxn>ans, a;
int L, R;
int x;
void update(int p, int l, int r) {
if (l >= L && r <= R) {
v[p].push_back(x);
return;
}
int mid = l + r >> 1;
if (L <= mid)update(p << 1, l, mid);
if (R > mid)update(p << 1 | 1, mid + 1, r);
}
void dfs(int l, int r, int p, bitset<maxn>y) {
bitset<maxn>t = y;
for (int x : v[p]) {
t|=(t << x);
}
int mid = (l + r) >> 1;
if (l == r)ans|=t;
else dfs(l, mid, p << 1, t), dfs(mid + 1, r, p << 1 | 1, t);
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
while (q--) {
scanf("%d%d%d", &L, &R, &x);
update(1, 1, n);
}
a[0] = 1;
int cnt = 0;
dfs(1, n, 1, a);
for (int i = 1; i <= n; i++) {
if (ans[i])cnt++;
}
printf("%d\n", cnt);
for (int i = 1; i <= n; i++) {
if (ans[i])printf("%d ", i);
}
}