Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Donut Decoration

Donut maker's morning is early. Mr. D, who is also called Mr. Donuts, is an awesome donut maker. Also today, he goes to his kitchen and prepares to make donuts before sunrise.

In a twinkling, Mr. D finishes frying $N$ donuts with a practiced hand. But these donuts as they are must not be displayed in a showcase. Filling cream, dipping in chocolate, topping somehow cute, colorful things, etc., several decoration tasks are needed. There are $K$ tasks numbered 1 through $K$, and each of them must be done exactly once in the order $1, 2, ..., K$ to finish the donuts as items on sale.

Instantly, Mr. D arranges the $N$ donuts in a row. He seems to intend to accomplish each decoration tasks sequentially at once. However, what in the world is he doing? Mr. D, who stayed up late at yesterday night, decorates only a part of the donuts in a consecutive interval for each task. It's clearly a mistake! Not only that, he does some tasks zero or several times, and the order of tasks is also disordered. The donuts which are not decorated by correct process cannot be provided as items on sale, so he should trash them.

Fortunately, there are data recording a sequence of tasks he did. The data contain the following information: for each task, the consecutive interval $[l, r]$ of the decorated donuts and the ID $x$ of the task. Please write a program enumerating the number of the donuts which can be displayed in a showcase as items on sale for given recorded data.

Input

The input consists of a single test case. The test case is formatted as follows.

$N$ $K$

$T$

$l_1$ $r_1$ $x_1$

...

$l_T$ $r_T$ $x_T$

The first line contains two integers $N$ and $K$, where $N$ ($1 \leq N \leq 200,000$) is the number of the donuts fried by Mr. D, and $K$ ($1 \leq K \leq 200,000$) is the number of decoration tasks should be applied to the donuts. The second line contains a single integer $T$ ($1 \leq T \leq 200,000$), which means the number of information about tasks Mr. D did. Each of next $T$ lines contains three
integers $l_i$, $r_i$, and $x_i$ representing the $i$-th task Mr. D did: the $i$-th task was applied to the interval $[l_i, r_i]$ ($1 \leq l_i \leq r_i \leq N$) of the donuts inclusive, and has ID $x_i$ ($1 \leq x_i \leq K$).

Output

Output the number of the donuts that can be provided as items on sale.

Sample Input 1

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

Output for the Sample Input 1

1

Sample Input 2

5 3
6
2 3 1
1 3 2
4 5 1
2 4 3
3 5 2
5 5 3

Output for the Sample Input 2

2

Sample Input 3

10 1
2
2 9 1
5 7 1

Output for the Sample Input 3

5



Sample input:
3 2
3
1 2 1
2 3 2
3 3 1


Sample output:
1

Submission status: Accepted

Solution code:
import sys

class Set:
    __slots__ = ["data", "one", "N", "N0", "size"]

    def __init__(self, N):
        self.data = [0]*(N+1)
        self.one = [0]*(N+1)
        self.N = N
        self.N0 = 2**(N.bit_length()-1)
        self.size = 0

    def __get(self, k):
        s = 0
        data = self.data
        while k:
            s += data[k]
            k -= k & -k
        return s

    def __add(self, k, x):
        N = self.N
        self.one[k] += x
        #assert 0 <= self.one[k]
        data = self.data
        while k <= N:
            data[k] += x
            k += k & -k
        self.size += x

    def __lower_bound(self, x):
        w = i = 0; k = self.N0
        N = self.N; data = self.data
        while k:
            if i+k <= N and w + data[i+k] <= x:
                w += data[i+k]
                i += k
            k >>= 1
        return i

    def add(self, x, y = 1):
        #assert 0 <= x < self.N
        self.__add(x+1, y)

    def remove(self, x, y = 1):
        #assert 0 <= x < self.N
        self.__add(x+1, -y)

    def find(self, x):
        if self.one[x+1] == 0:
            return -1
        return self.__get(x+1)

    def __contains__(self, x):
        return self.one[x+1] > 0

    def __iter__(self):
        x = self.next(0); N = self.N
        while x < N:
            for i in range(self.one[x+1]):
                yield x
            x = self.next(x+1)

    def count(self, x):
        #assert 0 <= x < self.N
        return self.one[x+1]

    def __len__(self):
        return self.size

    def prev(self, x):
        #assert 0 <= x <= self.N
        v = self.__get(x+1) - self.one[x+1] - 1
        if v == -1:
            return -1
        return self.__lower_bound(v)

    def next(self, x):
        #assert 0 <= x <= self.N
        if x == self.N or self.one[x+1]:
            return x
        v = self.__get(x+1)
        return self.__lower_bound(v)

    def at(self, k):
        v = self.__lower_bound(k)
        #assert 0 <= k and 0 <= v < self.N
        return v

    def __getitem__(self, k):
        return self.__lower_bound(k)

def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write

    N, K = map(int, readline().split())
    T = int(readline())
    A = [[] for i in range(N+1)]
    B = [[] for i in range(N+1)]
    X = [0]*T
    s = Set(T)
    for i in range(T):
        l, r, x = map(int, readline().split())
        A[l-1].append(i)
        B[r].append(i)
        X[i] = x
    c = 0
    ans = 0
    for i in range(N):
        for k in A[i]:
            s.add(k)
            p0 = s.prev(k)
            p1 = s.next(k+1)
            if p0 != -1 and p1 < T:
                if X[p0]+1 == X[p1]:
                    c -= 1
            if p0 != -1:
                if X[p0]+1 == X[k]:
                    c += 1
            if p1 < T:
                if X[k]+1 == X[p1]:
                    c += 1
        for k in B[i]:
            s.remove(k)
            p0 = s.prev(k)
            p1 = s.next(k+1)
            if p0 != -1:
                if X[p0]+1 == X[k]:
                    c -= 1
            if p1 < T:
                if X[k]+1 == X[p1]:
                    c -= 1
            if p0 != -1 and p1 < T:
                if X[p0]+1 == X[p1]:
                    c += 1
        if len(s) == K and c == K-1:
            ans += 1
    write("%d\n" % ans)
solve()