codeforces 981 e (선분 트 리 + bitset)

E. Addition on Segments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Grisha come to a contest and faced the following problem.
You are given an array of size nn, initially consisting of zeros. The elements of the array are enumerated from 11 to nn. You perform qqoperations on the array. The ii-th operation is described with three integers lili, riri and xixi (1≤li≤ri≤n1≤li≤ri≤n, 1≤xi≤n1≤xi≤n) and means that you should add xixi to each of the elements with indices li,li+1,…,rili,li+1,…,ri. After all operations you should find the maximum in the array.
Grisha is clever, so he solved the problem quickly.
However something went wrong inside his head and now he thinks of the following question: "consider we applied some subset of the operations to the array. What are the possible values of the maximum in the array?"
Help Grisha, find all integers yy between 11 and nn such that if you apply some subset (possibly empty) of the operations, then the maximum in the array becomes equal to yy.
Input
The first line contains two integers nn and qq (1≤n,q≤1041≤n,q≤104) — the length of the array and the number of queries in the initial problem.
The following qq lines contain queries, one per line. The ii-th of these lines contains three integers lili, riri and xixi (1≤li≤ri≤n1≤li≤ri≤n, 1≤xi≤n1≤xi≤n), denoting a query of adding xixi to the segment from lili-th to riri-th elements of the array, inclusive.
Output
In the first line print the only integer kk, denoting the number of integers from 11 to nn, inclusive, that can be equal to the maximum in the array after applying some subset (possibly empty) of the given operations.
In the next line print these kk integers from 11 to nn — the possible values of the maximum. Print these integers in increasing order.
Examples
input
Copy

4 3
1 3 1
2 4 2
3 4 4

output
Copy

4
1 2 3 4 

input
Copy

7 2
1 5 1
3 7 2

output
Copy

3
1 2 3 

input
Copy

10 3
1 1 2
1 1 3
1 1 6

output
Copy

6
2 3 5 6 8 9 

Note
Consider the first example. If you consider the subset only of the first query, the maximum is equal to 11. If you take only the second query, the maximum equals to 22. If you take the first two queries, the maximum becomes 33. If you take only the fourth query, the maximum becomes 44. If you take the fourth query and something more, the maximum becomes greater that nn, so you shouldn't print it.
In the second example you can take the first query to obtain 11. You can take only the second query to obtain 22. You can take all queries to obtain 33.
In the third example you can obtain the following maximums:
You can achieve the maximim of 22 by using queries: (1)(1).
You can achieve the maximim of 33 by using queries: (2)(2).
You can achieve the maximim of 55 by using queries: (1,2)(1,2).
You can achieve the maximim of 66 by using queries: (3)(3).
You can achieve the maximim of 88 by using queries: (1,3)(1,3).
You can achieve the maximim of 99 by using queries: (2,3)(2,3).
제목: n 길이 의 배열 이 있 습 니 다. 레이 블 은 1 부터 n 까지 입 니 다. 처음에는 0 이 었 습 니 다. 지금 은 q 번 작업 을 할 수 있 습 니 다. 매번 작업 할 때마다 한 구간 의 수 를 하나 더 합 니 다. 지금 은 q 번 작업 만 하 는 부분 집합 입 니 다. 완 료 된 배열 의 최대 수 는 얼마 일 수 있 는 지 물 어보 고 가능 한 모든 것 을 열거 하 십시오.
사고: 구간 내 에서 진행 할 수 있 는 다양한 작업 을 선분 트 리 로 저장 한 다음 STL 라 이브 러 리 에 있 는 bitset 를 이용 하여 위 에서 아래로 찾 아 구간 이 도달 할 수 있 는 모든 값 을 기록 하고 마지막 으로 집합 합 니 다.

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e4+10;
bitset ans,y;
vector tree[maxn << 2];
void update(int l,int r,int rt,int x,int y,int w)
{
    if(x>=l&&y<=r)
    {
        tree[rt].push_back(w);
        return ;
    }
    if(x == y)return;
    int mid = (x+y)>>1;
    update(l,r,rt<<1,x,mid,w);
    update(l,r,(rt<<1)+1,mid+1,y,w);
}
void dfs(int rt,bitsety,int len)
{
    bitsetz=y;
    for(int i=tree[rt].size()-1;i>=0;i--)
    {
        z|=(z<>1));
    dfs((rt<<1)+1,z,len>>1);
}
int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        for(int i=0;i<=(n<<2);i++)tree[i].clear();
        ans = 0;
        y = 0;
        y[0]=1;
        int l,r,w;
        for(int i=0;i