CF981E Addition on Segments 线段树分治+bitset

#include <bits/stdc++.h> 
#define N 10008  
#define lson now<<1 
#define rson now<<1|1   
#define setIO(s) freopen(s".in","r",stdin)   
using namespace std; 
int n,q; 
bitset<N>p,ans; 
vector<int>g[N<<2];    
void update(int l,int r,int now,int L,int R,int v) 
{
    if(l>=L&&r<=R) { g[now].push_back(v); return ; } 
    int mid=(l+r)>>1;  
    if(L<=mid)  update(l,mid,lson,L,R,v);  
    if(R>mid)   update(mid+1,r,rson,L,R,v);    
}
void calc(int l,int r,int now,bitset<N>k) 
{        
    for(int i=0;i<g[now].size();++i) 
    {      
        int val=g[now][i];           
        k|=(k<<val);   
    }     
    if(l==r) { ans|=k;  return ; } 
    int mid=(l+r)>>1;      
    calc(l,mid,lson,k),calc(mid+1,r,rson,k); 
}
int main() 
{  
    // setIO("input");  
    scanf("%d%d",&n,&q);                 
    for(int i=1;i<=q;++i) 
    {
        int l,r,x;  
        scanf("%d%d%d",&l,&r,&x),update(1,n,1,l,r,x);  
    }         
    p[0]=1,calc(1,n,1,p);
    int cnt=0; 
    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);   
    return 0; 
}