The machine that lies in the 52nd monthly race of Niuke (the complexity of interval assignment operation from O (n^2) to o (n))

C- Lying machine _ Niuke Xiaobai moon race 52 (nowcoder.com)

Title Description

Niuniu is playing numbers with its machine , But the machine seems to be broken ……
say concretely , The machine will first generate a random 1…n1…n1…n The number of kkk, Then the machine will give Niuniu mmm Orders , There are three forms of instructions ：
1、opopop xxx yyy; here ,op=1op = 1op=1 On behalf of  x≤k≤yx \leq k \leq yx≤k≤y
2、opopop xxx; here ,op=2op = 2op=2 On behalf of  x≤k≤nx \leq k \leq nx≤k≤n
3、opopop xxx; here ,op=3op = 3op=3 On behalf of  1≤k≤x1 \leq k \leq x1≤k≤x
Niuniu knows that this machine has learned to lie , So the instructions it describes may all be wrong , Now Niuniu wants to know how bad the machine is so that he can work out a plan to repair it .

So Niuniu wants you to tell it , When kkk take 1…n1…n1…n Values in this range , How many instructions are wrong on the machine at most , and kkk And how many kinds of value taking methods make the machine have the most wrong instructions .

Input description :

 The two integers in the first line represent  n,mn,mn,m 

Next mmm One instruction per line , The instruction format is shown in the topic .

Guarantee ：
1≤n≤106;  1 \leq n \leq 10^6;\ \ 1≤n≤106;  1≤x≤y≤n;  1 \leq x \leq y \leq n;\ \ 1≤x≤y≤n;  1≤m≤2×105;  1 \leq m \leq 2\times10^5;\ \ 1≤m≤2×105;  1≤op≤3;  1\leq op \leq 3;\ \ 1≤op≤3;  

Output description :

 Output two integers in a row , Each represents the maximum number of wrong instructions on the machine , And how many  kkk  The value of will cause the maximum number of error instructions on the machine .

Example 1

Input

9 5
1 3 6
2 7
1 2 3
3 2
1 5 8

Output

4 3

explain

The maximum number of error instructions is 4.

The values that maximize the number of error instructions are 3 Kind of , Namely ：

  The value is 1, At this time 1、2、3、5 Instruction is wrong .

  The value is 4, At this time 2、3、4、5 Instruction is wrong .

  The value is 9, At this time 1、3、4、5 Instruction is wrong .

Ideas ：

After executing all the instructions ,1 To n Each number of has a corresponding number of occurrences in the instruction ,k The less it is used , The more wrong instructions , It's in n Find the smallest number among the number of instructions executed （ There may be more than one ）, Then the number of this number is the number of K The value of ,m - The smallest value is the most erroneous instruction .

Tips ：

To assign a value to an interval n^2 The continuous assignment operation of the complexity of is converted to n Endpoint assignment of the complexity of , then v[i] += v[i - 1] The complexity of is n The operation of

Code ：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
int n, m, res = 1;

int main() {
    scanf("%d %d", &n, &m);
    vector<int> v(n + 2, 0);

    int x, y, z;
    for(int i = 0; i < m; i ++) {
        scanf("%d", &x);
        if(x == 1) {
           scanf("%d %d", &y, &z);
            // for(int i = y; i <= z; i ++) {
            //     v[i] ++;
            // }
            v[y] ++;
            v[z + 1] --;
        } else if(x == 2) {
             scanf("%d", &y);
            // for(int i = y; i <= n; i ++) {
            //     v[i] ++;
            // }
            v[y] ++;
            v[n + 1] --;
        } else {
             scanf("%d", &y);
            // for(int i = 1; i <= y; i ++) {
            //     v[1] ++;
            // }
            v[1] ++;
            v[y + 1] --;
        }
    }
    
   //  take  O(n^2) Operation conversion of O(n) The operation of 
    for(int i = 1; i <= n; i ++) {
        v[i] += v[i - 1];
    }

    sort(v.begin(), v.end());

    for(int i = 2; i < v.size(); i ++) {
        if(v[i] == v[i + 1]) {
            res ++;     // the number of k 
        } else 
        break;
    }

    printf("%d %d\n", m - v[2], res);

    return 0;
}