Addition on Segments(线段树+bitset)

描述

传送门:Avito Code Challenge 2018 - Problem E

Grisha come to a contest and faced the following problem.

You are given an array of size $n$, initially consisting of zeros. The elements of the array are enumerated from $1$ to $n$. You perform $q$ operations on the array. The $i$-th operation is described with three integers $l_i$, $r_i$ and $x_i$ ($1≤l_i≤r_i≤n$, $1≤x_i≤n$) and means that you should add $x_i$ to each of the elements with indices $l_i,l_{i+1},…,r_i$. 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 $y$ between $1$ and $n$ such that if you apply some subset (possibly empty) of the operations, then the maximum in the array becomes equal to $y$.

Input

The first line contains two integers $n$ and $q$ ($1≤n,q≤10^4$) — the length of the array and the number of queries in the initial problem.

The following $q$ lines contain queries, one per line. The $i$-th of these lines contains three integers $l_i, r_i and x_i$ ($1≤l_i≤r_i≤n$, $1≤x_i≤n$), denoting a query of adding $x_i$ to the segment from $l_i$-th to $r_i$-th elements of the array, inclusive.

Output

In the first line print the only integer $k$, denoting the number of integers from $1$ to $n$, 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 $k$ integers from $1$ to $n$ — the possible values of the maximum. Print these integers in increasing order.

Example

Input Output
1
2
3
4
4 3
1 3 1
2 4 2
3 4 4
1
2
4
1 2 3 4
1
2
3
7 2
1 5 1
3 7 2
1
2
3
1 2 3
1
2
3
4
10 3
1 1 2
1 1 3
1 1 6
1
2
6
2 3 5 6 8 9

思路

  • 区间更新,我们可以想到用线段树来打懒惰标记。但是这题要求的是可以达到的最大值。
  • 容易想到,根据懒惰标记的深度来选择更新的集合可以得到不同的最大值。
  • 于是我们把标记全部存下来后进行DP。$dp[i][j]$表示线段树深度为$i$的结点能否得到$j$的答案。
  • std::bitset大力干就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson

const int N = 1 << 14;
vector<int> T[N << 2];

void update(int L, int R, int x, int l, int r, int rt)
{
if (L <= l && r <= R)
{
T[rt].push_back(x);
return;
}
int m = l + r >> 1;
if (L <= m)
update(L, R, x, Lson);
if (m < R)
update(L, R, x, Rson);
}

bitset<N> bst[16], ans;
void gao(int l, int r, int rt, int dep)
{
bst[dep] = bst[dep - 1];
for (auto& v : T[rt]) bst[dep] |= (bst[dep] << v);
if (l == r)
{
ans |= bst[dep];
return;
}
int m = l + r >> 1;
gao(Lson, dep + 1);
gao(Rson, dep + 1);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
bst[0][0] = 1;
int n, q;
scanf("%d%d", &n, &q);
for (int i = 0, l, r, x; i < q; i++)
{
scanf("%d%d%d", &l, &r, &x);
update(l, r, x, 1, n, 1);
}
gao(1, n, 1, 1);
int ret = 0;
for (int i = 1; i <= n; i++) ret += ans[i];
printf("%d\n", ret);
for (int i = 1; i <= n; i++)
if (ans[i]) printf("%d ", i);
return 0;
捐助作者
0%