回滚线段树+bitset优化01背包——cf981E

/*首先考虑如何计算一个点的可能凑出的值，这就是一个01可行性背包问题那么再拓展到一段区间[1..n]的点上，每个query都可以看做是一段区间上的点[l,r]加上一个体积为x的物品，转换到01背包上就是进行一次更新那么用线段树来维护每个query的区间更新 每个位置(区间)维护一个bitset，每次加入a都进行一次01背包 用线段树来维护区间的bitset，表示一段区间能组成的值 但是没法用lazy，每次区间更新只能停留在一段区间可以把每次停留在区间的数a用vector保存下来，当进行完所有的更新时，从线段树叶子结点开始向上回滚每个区间的可行性是左儿子的可行性|右儿子的可行性|vector里存的每个a提供的可行性贡献 */ #include<bits/stdc++.h> using namespace std; int n,m; #define maxn 10005 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Node{int l,r,x;}p[maxn]; bitset<10005>seg[maxn<<2]; vector<int>v[maxn<<2]; void build(int l,int r,int rt){ seg[rt][0]=1; if(l==r)return; int m=l+r>>1; build(lson); build(rson); } void update(int L,int R,int x,int l,int r,int rt){ if(L<=l && R>=r){ v[rt].push_back(x); return; } int m=l+r>>1; if(L<=m)update(L,R,x,lson); if(R>m)update(L,R,x,rson); } void debug(int l,int r,int rt){ cout<<rt<<" "<<l<<" "<<r<<'\n'; for(int i=0;i<=n;i++) cout<<seg[rt][i]; puts(""); } void roll(int l,int r,int rt){ if(l==r){ for(int i=0;i<v[rt].size();i++) seg[rt]|=seg[rt]<<v[rt][i]; //debug(l,r,rt); return; } int m=l+r>>1; roll(lson); roll(rson); seg[rt]|=seg[rt<<1]; seg[rt]|=seg[rt<<1|1]; for(int i=0;i<v[rt].size();i++){ int a=v[rt][i]; seg[rt]|=seg[rt]<<a; } //debug(l,r,rt); } int main(){ cin>>n>>m; for(int i=1;i<=m;i++) scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].x); build(1,n,1); for(int i=1;i<=m;i++) update(p[i].l,p[i].r,p[i].x,1,n,1); roll(1,n,1); int ans=0; for(int i=1;i<=n;i++) if(seg[1][i])ans++; cout<<ans<<'\n'; for(int i=1;i<=n;i++) if(seg[1][i])cout<<i<<" "; }

 

转载于:https://www.cnblogs.com/zsben991126/p/11184568.html