本文共 1412 字，大约阅读时间需要 4 分钟。

输入：
10 10
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10

输出：
1 2 2

思路： 核心：差分前缀和
上手看区间，差分一波，然后求前缀和，逐个看ac的题数，再根据金银牌数量分配，不过区间一多然后一长就tle了。
这里要对区间进行离散操作，假如有区间[1,10000]求前缀和需要从1加到10000，因为最后也不用求出具体哪个队伍的ac题数，其实只要统计区间长度即可，对每个区间编号，统计区间长度，优化算法。

//离散+差分+前缀和#include <bits/stdc++.h>using namespace std;typedef long long ll;int cnt[100010]; //做出i个题的人数struct ty{    int pos,num; //存区间下标和是加1还是减1}a[200010];bool cmp(ty a, ty b) //将点按照从左往右，先减后加排序{       if( a.pos!= b.pos)  return a.pos< b.pos;    else return a.num<b.num;}int main(){       int n,m;    cin>>n>>m;    for(int i=1 ;i<=m ;i++)    {           int l,r;//离散化        cin>>l>>r;        a[i].num=1; //左端点        a[i].pos=l;        a[i+m].num=-1; //右端点        a[i+m].pos=r+1; //差分，往后一位    }    //将2m个点排序    sort(a+1,a+1+m+m,cmp);        int sum=0;  //记录目前ac的题数    int maxn=1; //ac最多题的人数    for(int i=1 ;i<=m+m; i++)    {           //看区间两端        if( a[i].pos -a[i-1].pos!=0 )        cnt[sum]+=a[i].pos-a[i-1].pos; //记录ac sum道题的人数        sum+=a[i].num;        maxn=max(maxn,sum); //更新最大    }    int j=-1 ,y=-1 ,t=-1;    for(int i=maxn ;i>=0 ;i--)    {           cnt[i]+=cnt[i+1];  //前缀和,大于等于i题的人数        if( j==-1 && (cnt[i] >= (n+9)/10) )  j=i;        if( y==-1 && (cnt[i] >= (n+3)/4) )  y=i;        if( t==-1 && (cnt[i] >= (n+1)/2) )  t=i;    }    //因为获得奖牌的必要条件是ac一题    j=max(j,1);    y=max(y,1);    t=max(t,1);    cout<<cnt[j]<<" "<<cnt[y]-cnt[j]<<" "<<cnt[t]-cnt[y];}