有n个仓库,m次操作,每次在l和r之间的仓库收进编号为d的货物。最后求存放货物种类最多的仓库编号。

在区间内实现加减,我们可以使用差分数组。还要注意的一点:不是存放货物数目最多,而是存放货物种类最多,为了防止重叠区间重复计算答案,我们可以先将区间读下来,排个序(先按编号从小到大,编号相同按起始位置从小到大),把同一种类的重叠区间合并起来,避免多算。

#include<cstdio>
#include<algorithm>
using namespace std;
struct node {
    int st,ed,num; //起始位置,终止位置,编号种类
} a[100010];
bool operator <(node x,node y) {//先按编号从小到大,编号相同按起始位置从小到大
    return x.num==y.num ? x.st<y.st:x.num<y.num;
}
int d[100010];
int main() {
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++) scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].num);
    sort(a+1,a+m+1);

    int s=a[1].st,t=a[1].ed;//把同一种类的重叠区间合并为[s,t]的区间
    for (int i=2; i<=m; i++){
        if (a[i].st<=t && a[i].num==a[i-1].num)
            t=max(a[i].ed,t);//区间重叠就合并
        else d[s]++,d[t+1]--,s=a[i].st,t=a[i].ed;//区间不重合的时候就将[s,t]加1(差分),再更新s,t
    }
    d[s]++,d[t+1]--;

    for (int i=1,sum=0,mx=0; i<=n; i++) {
        sum+=d[i];//将差分数组的值转为实际值
        if (sum>mx)
            mx=sum,ans=i;
    }
    printf("%d\n",ans);
}

这题也可以用线段树等数据结构解,在这里就留给dalao们探索啦qwq!