牛客 52次月赛 C 说谎的机器 （区间赋值操作由O(n^2)转为O(n)的复杂度）

C-说谎的机器_牛客小白月赛52 (nowcoder.com)

题目描述

牛牛在和它的机器玩猜数字，可是机器好像坏了……
具体来说，机器首先会随机生成一个 1…n1…n1…n 的数字 kkk，紧接着机器会给牛牛 mmm 条指令，指令的格式有如下三种：
1、opopop xxx yyy；这里，op=1op = 1op=1 代表有 x≤k≤yx \leq k \leq yx≤k≤y
2、opopop xxx；这里，op=2op = 2op=2 代表有 x≤k≤nx \leq k \leq nx≤k≤n
3、opopop xxx；这里，op=3op = 3op=3 代表有 1≤k≤x1 \leq k \leq x1≤k≤x
牛牛知道这台机器已经学会了说谎，所以它所描述的指令可能都是错误的，现在牛牛想知道机器错误的程度以便来制定修理它的方案。

所以牛牛想请你告诉它，当 kkk 取 1…n1…n1…n 这个范围内的值时，机器最多有多少条指令是错误的，而 kkk 又有多少种取值方式使得机器的错误指令数最多。

输入描述:

第一行两个整数代表 n,mn,mn,m 

接下来 mmm 行每行一条指令，指令格式见题面。

保证：
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;  

输出描述:

输出共一行两个整数，分别代表机器最多的错误指令数，以及有多少种 kkk 的取值会使得机器的错误指令数最多。

示例1

输入

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

输出

4 3

说明

最多的错误指令数为 4。

使得错误指令数最多的取值有 3 种，分别是：

  取值为 1，此时第 1、2、3、5 条指令是错误的。

  取值为 4，此时第 2、3、4、5 条指令是错误的。

  取值为 9，此时第 1、3、4、5 条指令是错误的。

思路：

执行完所有的指令后，1到n的每个数都有相应的在指令中出现的次数，k被使用的次数越少，则错误的指令越多，则在n个执行完指令的数里面找到最小的那个数（可能有多个），则这个数的数量就是有多少种K的取值，m - 最小的那个数值即为最多的错误指令。

小技巧：

将区间赋值操作的n^2的复杂度的连续赋值操作转为n的复杂度的端点赋值，然后v[i] += v[i - 1]的复杂度为n的操作

代码：

#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] --;
        }
    }
    
   // 将 O(n^2)的操作转成O(n)的操作
    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;
}