NC202498 货物种类

题目

题目描述

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

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

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

输入描述:

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

输出描述

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

示例1

输入

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

输出

3

题解

思路

知识点：前缀和。

先将区间按种类从小到大排序，左端点从小到大。再对同一类连通区间合并，并对端点进行差分处理表示这个区间种类数+1。之后做前缀和得到某个点的种类数，最后做判断得到最小下标即可。

时间复杂度 \(O(mlogm+n)\)

空间复杂度 \(O(m+n)\)

代码

#include 

using namespace std;

int vis[100007];

struct pack{
    int l,r,d;
}p[100007];

bool cmp(pack a,pack b){
    return a.d == b.d?a.l>n>>m;
    for(int i = 0;i>p[i].l>>p[i].r>>p[i].d;
    }
    sort(p,p+m,cmp);
    int l = p[0].l,r = p[0].r;
    for(int i = 1;i