Sequence Recovery
Contest: Codeforces Round 408 (Div. 2)
Difficulty rating: 2800
Tags: bitmasks, data structures, greedy

Zane once had a good sequence a consisting of n integers a1, a2, ..., an — but he has lost it.

A sequence is said to be good if and only if all of its integers are non-negative and do not exceed 109 in value.

However, Zane remembers having played around with his sequence by applying m operations to it.

There are two types of operations:

1. Find the maximum value of integers with indices i such that l ≤ i ≤ r, given l and r.

2. Assign d as the value of the integer with index k, given k and d.

After he finished playing, he restored his sequence to the state it was before any operations were applied. That is, sequence a was no longer affected by the applied type 2 operations. Then, he lost his sequence at some time between now and then.

Fortunately, Zane remembers all the operations and the order he applied them to his sequence, along with the distinct results of all type 1 operations. Moreover, among all good sequences that would produce the same results when the same operations are applied in the same order, he knows that his sequence a has the greatest cuteness.

We define cuteness of a sequence as the bitwise OR result of all integers in such sequence. For example, the cuteness of Zane's sequence a is a1 OR a2 OR ... OR an.

Zane understands that it might not be possible to recover exactly the lost sequence given his information, so he would be happy to get any good sequence b consisting of n integers b1, b2, ..., bn that:

1. would give the same results when the same operations are applied in the same order, and

2. has the same cuteness as that of Zane's original sequence a.

If there is such a sequence, find it. Otherwise, it means that Zane must have remembered something incorrectly, which is possible.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the number of integers in Zane's original sequence and the number of operations that have been applied to the sequence, respectively.

The i-th of the following m lines starts with one integer ti ($$t_{i} \in \{1,2\}$$) — the type of the i-th operation.

If the operation is type 1 (ti = 1), then three integers li, ri, and xi follow (1 ≤ li ≤ ri ≤ n, 0 ≤ xi ≤ 109) — the leftmost index to be considered, the rightmost index to be considered, and the maximum value of all integers with indices between li and ri, inclusive, respectively.

If the operation is type 2 (ti = 2), then two integers ki and di follow (1 ≤ ki ≤ n, 0 ≤ di ≤ 109) — meaning that the integer with index ki should become di after this operation.

It is guaranteed that xi ≠ xj for all pairs (i, j) where 1 ≤ i < j ≤ m and ti = tj = 1.

The operations are given in the same order they were applied. That is, the operation that is given first was applied first, the operation that is given second was applied second, and so on.

Output format:
If there does not exist a valid good sequence, print "NO" (without quotation marks) in the first line.

Otherwise, print "YES" (without quotation marks) in the first line, and print n space-separated integers b1, b2, ..., bn (0 ≤ bi ≤ 109) in the second line.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it is easy to verify that this good sequence is valid. In particular, its cuteness is 19 OR 0 OR 0 OR 0 OR 1  =  19.

In the second sample, the two operations clearly contradict, so there is no such good sequence.

Example input:
5 4
1 1 5 19
1 2 5 1
2 5 100
1 1 5 100

Example output:
YES
19 0 0 0 1

Example input:
5 2
1 1 5 0
1 1 5 100

Example output:
NO

Editorial:
First, let’s find the maximum value each integer can be. Chronologically considering the operations, you can see that once an integer is involved in type 2 operation, future type 1 operations can tell nothing about its initial value. You can find naively find the maximum value each integer can be in O(nm), but that’s obviously way too slow.
This can be solved using segment trees. You might be familiar with point updates and range queries, but now you have to consider point queries and range updates. No—lazy propagation is not needed. This process can be solved in $${ \mathcal { O } } \left( ( n + m ) \log n \right)$$.
After that, let each integer has its maximum possible value as its value. Go through the operations once again one by one (both type 1 and type 2), and check with another segment tree whether this sequence gives correct results for type 1 operations. If it is not, you can be sure that there is no valid sequence. Why? Let’s consider two cases. If the result is smaller than what the input says, this integer can’t really be bigger than it is (other type 1 operations needed it to be this small, or maybe type 2 operation forced it to become this value). If the result is bigger than what the input says, this happens only when there is a contradiction between type 1 and type 2 operations, and nothing can be done (because type 2 operations say so).
Let’s complete the final step — make the bitwise OR maximal. You should consider 2 cases.
1) There is more than one free integer. (Free integer is the one such that no type 1 operation limits it maximum value.)
The optimal bitwise OR is simply 230 - 1. Just make one of the free integers 229 - 1 and the others 109 (any value no less than 229 but also no more than 109 will work). You can be sure that this is optimal. Other integers can simply remain untouched.
2) Otherwise
For case 2, for each value appearing in more than one integer of the sequence (do not consider the one without maximum value yet), you can lower one of them. Lowering more than one of them will not give a better result if you lower it in this way: sacrifice the most significant bit for ALL other less significant bits. It’s obvious that the operations remain satisfied. As for the free integer, if any, you can greedily assign some bit to it, starting from the most significant bit, but make sure that it doesn’t exceed 109 in value.