题解 | #货物种类#

枚举，差分，离散化

题中给的数据范围太大，开个大数组暴力枚举不现实，考虑离散化处理，同时维护一个差分数组存储每个仓库的货物种类。

1、利用结构体把每次进货的信息存储好；

2、自定义升序排序规则，货物编号优先级第一，区间起点优先级第二；

3、定义两个临时变量存储临时起点和临时终点；

4、若第j个结构体货物编号与第j-1个结构体的货物编号不一致，说明此次货物编号为新编号，处理差分数组；否则，进行区间合并（如果区间不相交则直接处理差分数组），等到下一个新编号出现时再处理差分数组；

5、求差分数组的前缀和得到所有仓库的货物种类数组，遍历该数组并做判断即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define M 100010
int delta[M];    //维护一个差分数组存储各仓库货物种类数

struct tag{
    int l,r,d;
}a[M];

bool comp(tag x,tag y){    //若货物编号相等，则按左端点升序排列，否则按编号升序排列
    return x.d == y.d ? x.l < y.l : x.d < y.d;
}

int main(){
    int n,m,ans;
    cin>>n>>m;
    for(int i = 1;i <= m;i++){
        cin>>a[i].l>>a[i].r>>a[i].d;
    }
    
    sort(a+1,a+m+1,comp);
    int temp_o = a[1].l,temp_d = a[1].r;
    for(int j = 2;j <= m;j++){
        if(a[j].d != a[j-1].d){    //出现新类型，差分数组端点变化
            delta[temp_o]++;        //同时刷新起点和终点
            delta[temp_d+1]--;
            temp_o = a[j].l;
            temp_d = a[j].r;
        }
        else{
            if(a[j].l <= temp_d) temp_d = max(temp_d,a[j].r);
            else{                    //旧货物，进行区间合并或处理差分数组
                delta[temp_o]++;
                delta[temp_d+1]--;
                temp_o = a[j].l;
                temp_d = a[j].r;
            }
        }
    }
    delta[temp_o]++;        //最后一次没处理
    delta[temp_d+1]--;
    
    for(int k = 1;k <= n;k++)    //复原差分数组
        delta[k] += delta[k-1]; 
    
    ans = 0;
    int a_max = 0;
    for(int s = 1;s <= n;s++){
        if(delta[s] > a_max){    //也可以逆序遍历，把等号改成大于或等于
            ans = s;
            a_max = delta[ans];
        }
    }
    cout<<ans;
    return 0;
}