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

不离散化的做法

把一段一段区间看成一个个线段,我们把线段拆分为左端点和右端点

端点按照从小到大排序(右端点+1的位置放进去,因为是差分)

从最左边往右边扫描

遇到左端点,答案加一,遇到右端点答案减一

这样可以在线性时间内统计获得$i$块奖牌的人数

然后就很简单了

离散化

如果觉得上面的不好模拟,可以把所有区间离散化

然后直接在数组里差分,还原即可

这里贴一下核心代码

rep(i, 1, m)   {
       cin >> l[i] >> r[i];    a[++cnt] = l[i], a[++cnt] = r[i],a[++cnt] = r[i] + 1;  }  sort(a + 1, a + 1 + cnt);  len = unique(a + 1, a + 1 + cnt) - (a + 1);  rep(i, 1, m) {
       sum[getID(l[i])]++;    sum[getID(r[i]) + 1]--;  }  rep(i, 1, len) sum[i] += sum[i - 1];  rep(i, 1, len)   {
       int now = a[i + 1] - a[i];    num[sum[i]] += now;  }

不离散化的。

#include 
   
    using namespace std;#define int long longconst int mod = 1e9+7;const int maxn = 1e7+10;struct p{
   	int x,lei;	bool operator < (const p&tmp )	const	{
   		if( x==tmp.x )	return lei
    
     > n >> m;	for(int i=1;i<=m;i++)	{
   		int l,r; scanf("%lld%lld",&l,&r);		a[++top].x = l, a[top].lei = 1;		a[++top].x = r+1, a[top].lei = -1;	}	sort( a+1,a+1+top );	int last = a[1].x, now = 1;	for(int i=2;i<=top;i++)//依次拿出每个点的区间端点来 	{
   		int num = a[i].x-last;//当前点在修改		last = a[i].x;		vec[now] += num;		now += a[i].lei;	}	int jin = n/10+(n%10!=0), yin = n/4+(n%4!=0), to = n/2+(n%2!=0);    now = 0;    int ans1 = 0,ans2 = 0,ans3 = 0;    for(int i=m;i>=1;i--)    {
           now += vec[i];        if( ans1==0&&now>=jin )  ans1 = now;        if( ans2==0&&now>=yin )  ans2 = now;        if( ans3==0&&now>=to )   ans3 = now;    }    if( ans1==0 )	ans1 = now;    else if( ans2==0 )	ans2 = now;    else if( ans3==0 )	ans3 = now;    cout << ans1 << " " << max(0ll,ans2-ans1) << " " << max(0ll,ans3-ans2);}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113616425 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！