[NC202498] 货物种类

题目描述

某电商平台有$n$个仓库，编号从$1$到$n$。

当购进某种货物的时候，商家会把货物分散的放在编号相邻的几个仓库中。

我们暂时不考虑售出，你是否能知道，当所有货物购买完毕，存放货物种类最多的仓库编号为多少？

输入描述:

在第一行中给出两个正整数 $n,m,1≤n,m≤10^5$，分别代表仓库的数目和进货的次数。
接下来 $m$ 行，每行三个正整数 $l,r,d,1 \le l,r \le n, 1 \le d \le 10^9$ 。编号在 $l$ 和 $r$ 之间的仓库收进编号为 $d$ 的货物。（包括 $l$ 和 $r$）

输出描述:

在一行中输出存放货物种类最多的仓库编号，若满足条件的仓库不止一个，则输出编号最小的那个。

示例1

输入

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

输出

1
3

AC代码：

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
#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 1e5+10;

struct mt{
    int l,r,d;
};

int cmp(mt m1,mt m2){
    if(m1.d != m2.d) return m1.d < m2.d;
    return m1.l < m2.l;
}

int main(){
    int n,m,p[MAX]{};
    mt mts[MAX];
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> mts[i].l >> mts[i].r >> mts[i].d;
    }
    sort(mts+1,mts+1+m,cmp);
    int l = mts[1].l,r = mts[1].r;
    for(int i=2;i<=m;i++){
        if(mts[i].l <= r && mts[i].d == mts[i-1].d){
            r = max(r,mts[i].r);
        }else{
            --p[l];++p[r+1];
            l = mts[i].l;
            r = mts[i].r;
        }
    }
    --p[l];++p[r+1];
    int maxn=0,pos=0,qian=0;
    for(int i=1;i<=n;i++){
        qian = qian - p[i];
        if(maxn < qian){
            pos = i;
            maxn = qian;
        }
    }
    cout << pos;
    return 0;
}

题解

把这个理解成前缀和问题，先对区间进行合并，然后进行差分，最后前缀和合并。