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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include <cinttypes>
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <optional>

/**
 * Możliwe łatwa do modyfikowania implementacja drzewa przedziałowego.
 * 
 * Przyjęte konwencje:
 * #) Wewnętrznie wierzchołki są indeksowane od 1 (pole zerowe w tablicy z danymi jest nieużywane)
 * #) Wysokość drzewa to długość ścieżki od korzenia do liścia
 * #) Korzeń ma głębokość 0
 * #) W szczególności głębokość każdego węzła jest mniejsza *lub równa* wysokości drzewa
 * #) Dodatkowo wprowadzamy *indeksację zewnętrzną*, gdzie wszystkie liście są ponumerowane od 0. Węzły, które nie są
 *    liśćmi w tej indeksacji nie występują
 */
template<class T>
class BasicIntervalTree
{
public:
    using DataType = T;
    
private:
    /**
     * Możliwie użyteczny wrapper dla węzła drzewa przedziałowego.
     * Drzewo nie przechowuje w nim danych ale dostarcza wiele użytecznych operacji do poruszania się po drzewie.
     */
    template<class TreeType>
    class BasicNode
    {
    protected:
        /// Drzewo do którego należy
        TreeType *tree_;
        /// Indeks wierzchołka w tablicy 
        size_t index_;
        /// Głębokość węzła. Korzeń ma głębokość 0; jest mniejsza *lub równa* wysokości drzewa
        size_t depth_;
        
    public:
        BasicNode(TreeType &parent, size_t index):
            tree_(&parent),
            index_(index),
            depth_(std::floor(std::log2(index)))
        {
            assert(0 < index_ && index_ < tree_->data_.size());
        }
        
        bool operator==(const BasicNode &other)
        {
            return index_ == other.index_ && tree_ == other.tree_;
        }
        
        bool operator!=(const BasicNode &other)
        {
            return index_ != other.index_ || tree_ != other.tree_;
        }
        
        /// Czy węzeł jest korzeniem
        bool is_root() const noexcept
        {
            return index_ == 1;
        }
        
        /// Czy węzeł jest liściem
        bool is_leaf() const noexcept
        {
            return index_ >= tree_->capacity_;
        }
        
        /// Czy węzeł jest lewym synem swojego ojca (korzeń nie jest)
        bool is_left() const noexcept
        {
            return index_ % 2 == 0 && !is_root();
        }
        
        /// Czy węzeł jest lewym synem swojego ojca (korzeń nie jest)
        bool is_right() const noexcept
        {
            return index_ % 2 == 1 && !is_root();
        }
        
        /// Brat tego węzła (drugi syn jego rodzica)
        BasicNode sibling() const
        {
            assert(!is_root());
            return BasicNode(*tree_, index_ ^ 1);
        }
        
        /// Lewe dziecko tego węzła
        BasicNode left_child() const 
        {
            assert(!is_leaf());
            return BasicNode(*tree_, index_ * 2);
        }
        
        /// Prawe dziecko tego węzła
        BasicNode right_child() const 
        {
            assert(!is_leaf());
            return BasicNode(*tree_, index_ * 2 + 1);
        }
        
        /// Rodzic tego węzła
        BasicNode parent() const
        {
            assert(!is_root());
            return BasicNode(*tree_, index_ / 2);
        }
        
        /// O ile liść o podanym indeksie znajduje się w poddrzewie tego węzła, to zwraca kolejny (niższy) węzeł
        /// na ścieżce do tego liścia. Liście są numerowane jak w <c>leaf_index()</c>
        std::optional<BasicNode> next_on_path(size_t target_leaf_index) 
        {
            auto range = leaves_range();
            assert(range.first <= target_leaf_index && target_leaf_index <= range.second);
            if (is_leaf())
                return std::optional<BasicNode>{};
            if (right_child().leaves_range().first > target_leaf_index)
                return left_child();
            return right_child();
        }
        
        /// Wewnętrzny indeks wierzchołka w drzewie (1 dla korzenia)
        size_t index() const noexcept
        {
            assert(0 < index_ && index_ < tree_->data_.size());
            return index_;
        }
        
        /// Indeks liścia (liście indeksujemy od <c>0</c> do <c>tree_->capacity_</c>),
        /// o ile dany wierzchołek jest liściem
        size_t leaf_index() const noexcept
        {
            
            assert(is_leaf());
            return index_ - tree_->capacity_;
        }
        
        /// Głębokość, na jakiej znajduje się liść (<c>0</c> korzenia; głębokość liści jest równa wysokości drzewa)
        size_t depth() const noexcept
        {
            return depth_;
        }
        
        /// Wysokość poddrzewa ukorzenionego w tym węźle (<c>0</c> dla liści)
        size_t height() const noexcept
        {
            return tree_->height_ - depth_;
        }
        
        /// Liczba liści w poddrzewie ukorzenionym w tym wierzchołku. Działa także dla liści i zwraca <c>1</c>
        size_t count_leaves() const noexcept
        {
            return (1 << height());
        }
        
        /// Najmniejszy i największy indeks liścia dla poddrzewa ukorzenionego w tym wierzchołku. 
        /// Działa też dla liści — wówczas obie wartości pary są równe
        std::pair<size_t, size_t> leaves_range() const
        {
            auto first = (index_ << height()) - tree_->capacity_;
            return {first, first + count_leaves() - 1};
        }
        
        /// Dane drzewa związane z tym wierzchołkiem
        const DataType &data() const noexcept
        {
            return tree_->data_[index_];
        }
        
        /// Dane drzewa związane z tym wierzchołkiem
        template<class FOO = DataType>
        typename std::enable_if<!std::is_const<TreeType>::value, FOO&>::type &data() noexcept
        {
            return tree_->data_[index_];
        }
        
        template<class F>
        friend std::ostream &operator<<(std::ostream &os, const BasicNode &node);
    };
    
public:
    using Node = BasicNode<BasicIntervalTree>;
    using ConstNode = BasicNode<const BasicIntervalTree>;
    
    
protected:    
    /// Wysokość drzewa (długość ścieżki od korzenia do liścia)
    size_t height_;
    /// Liczba liści w drzewie
    size_t capacity_;
    /// Dane przechowywane w kolejnych węzłach
    std::vector<DataType> data_;
    
    /// Zwraca opakowany w <c>Node</c> korzeń drzewa
    Node root_() 
    {
        return Node(*this, 1);
    }
    
    /// Zwraca opakowany w <c>Node</c> liść o podanym indeksie (indeksacja jak w <c>Node::leaf_index()</c>)
    Node leaf_(size_t index) 
    {
        return Node(*this, capacity_ + index);
    }
    
    
public:
    /**
     * Konstruuje drzewo przedziałowe.
     * Stworzone drzewo spełnia następujące warunki:
     * - Jest pełnym drzewem binarnym
     * - Ma przynajmniej <c>min_leaves_number</c> liści i mniej niż <c>2 * min_leaves_number</c>
     */
    explicit BasicIntervalTree(size_t min_leaves_number):
        height_(static_cast<unsigned int>(std::ceil(std::log2(min_leaves_number)))),
        capacity_(1 << height_),
        data_(2 * capacity_, 0)
    {}
};

using Color = std::bitset<3>;
constexpr Color COLOR_YELLOW = 0b001;
constexpr Color COLOR_BLUE   = 0b010;
constexpr Color COLOR_RED    = 0b100;
const Color COLOR_GREEN  = COLOR_YELLOW | COLOR_BLUE;
constexpr bool DEBUG = false;

class PaintBuckets: BasicIntervalTree<Color>
{
public:
    using BasicIntervalTree<Color>::BasicIntervalTree;
    
    Color operator[](const size_t index)
    {
        Color c = 0;
        auto node = std::optional{root_()};
        while (node) {
            c |= node->data();
            node = node->next_on_path(index);
        }
        return c;
    }

    void add_color(size_t f, size_t l, Color color)
    {
        auto left = leaf_(f);
        auto right = leaf_(l);

        left.data() |= color;
        right.data() |= color;

        while (left.parent() != right.parent()) {
            if (left.is_left())
                left.sibling().data() |= color;
            left = left.parent();

            if (right.is_right())
                right.sibling().data() |= color;
            right = right.parent();
        }
    }
};

Color nr_to_color(size_t nr) 
{
    switch (nr) {
    case 1: return COLOR_YELLOW;
    case 2: return COLOR_BLUE;
    case 3: return COLOR_RED;
    }
    assert(false);
}

int main()
{
    std::ios::sync_with_stdio(false);
    size_t n, m;
    std::cin >> n >> m;

    PaintBuckets buckets{n};
    for (size_t i = 0; i < m; ++i) {
        size_t l, r, k;
        std::cin >> l >> r >> k;
        buckets.add_color(l - 1, r - 1, nr_to_color(k));

        if constexpr (DEBUG) {
            for (unsigned i = 0; i < n; ++i)
                std::cerr << std::setw(3) << i << ' ';
            std::cout << '\n';
            for (unsigned i = 0; i < n; ++i)
                std::cerr << buckets[i] << ' ';
            std::cout << '\n' << std::endl;
        }
    }

    size_t ngreen = 0;
    for (size_t i = 0; i < n; ++i) {
        if (buckets[i] == COLOR_GREEN)
            ++ngreen;
    }
    std::cout << ngreen << std::endl;

    return 0;
}