Problem: Example

Input

3 2
3
1 2 1
2 3 2
3 3 1


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

constexpr int invalid = -2;

class square_root_decomposition {
public:
    square_root_decomposition(int N)
        : B(sqrt(N))
    {
        N = (N + B - 1) / B * B;
        before.assign(N / B, -1);
        after.assign(N / B, -1);
        donut.assign(N, 0);
    }

    void eval(int b) {
        if(before[b] == -1) {
            return;
        }

        for(int i = B * b; i < B * (b + 1); ++i) {
            if(donut[i] == before[b]) {
                donut[i] = after[b];
            } else {
                donut[i] = invalid;
            }
        }
        before[b] = after[b] = -1;
    }

    void update_block(int b, int x) {
        if(after[b] != -1) {
            if(after[b] == x - 1) {
                after[b] = x;
            } else {
                after[b] = invalid;
            }
        } else {
            before[b] = x - 1;
            after[b] = x;
        }
    }

    void update_naive(int l, int r, int x) {
        for(int i = l; i <= r; ++i) {
            if(donut[i] == x - 1) {
                donut[i] = x;
            } else {
                donut[i] = invalid;
            }
        }
    }

    void update(int l, int r, int x) {
        if(l / B == r / B) {
            eval(l / B);
            update_naive(l, r, x);
        } else {
            int bl = l / B;
            int br = r / B;
            if(l % B != 0) {
                eval(l / B);
                update_naive(l, (l + B - 1) / B * B - 1, x);
                bl++;
            }
            if(r % B != B - 1) {
                eval(r / B);
                update_naive(r - r % B, r, x);
                br--;
            }
            
            for(int i = bl; i <= br; ++i) {
                update_block(i, x);
            }
        }
    }

    int query(int k) {
        for(int i = 0; i < (int)before.size(); ++i) {
            eval(i);
        }
        return count(begin(donut), end(donut), k);
    }

    void dbg() {
        for(int i = 0; i < (int)donut.size(); ++i) {
            cout << "dbg donut: " << i << ' ' << donut[i] << endl;
        }
        for(int b = 0; b < (int)before.size(); ++b) {
            cout << "dbg block: " << b << ' ' << before[b] << ' ' << after[b] << endl;
        }
    }

private:
    const int B;
    vector<int> before, after;
    vector<int> donut;
};


int main() {
    int N, K, T;
    cin >> N >> K;
    cin >> T;

    square_root_decomposition sq(N);

    for(int i = 0; i < T; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        sq.update(l-1, r-1, x);
    }

    cout << sq.query(K) << endl;
}