POJ - 1201 Intervals（贪心+数据结构）

考虑把所有线段按照右端点 $b$ 从小到大排序，依次考虑每一条线段的要求：

• 如果已经满足要求则跳过
• 否则尽量选择靠后的数（因为之后的线段的右端点都在这条线段的右边，这样容错更高）

所以，我们可以建一个数组，$f[i]$ 表示 $i$ 数字是否选择（填$1$或$0$），扫一遍$[l,r]$ 区间求和，然后从后往前贪心放数即可。
对于每条线段需要 $O(r-l+1)$。所以最坏情况下 $O(n^2)$。

考虑用数据结构优化。

• 询问 $[l,r]$ 区间的数字个数
• 将值为 $x$ 的位置 $+1$
• 从后往前，找到比当前位置靠前的下一个 $0$ 的位置。

这就是 “区间求和，单调修改”，典型的树状数组。$O(nlo{g}_{2}50000)$

#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
const int N = 50010;
PIII g[N];
int f[N],c[N];
inline bool cmp(const PIII &X,const PIII &Y)
{
	return X.first.second<Y.first.second;
}
inline int ask(int x)
{
	int res=0;
	for(;x>0;x-=(x&-x)) res+=c[x];
	return res; 
}
inline void add(int x,int y)
{
	for(;x<N;x+=(x&-x)) c[x]+=y;
}
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		g[i]=(PIII){(PII){a,b},c};
	}
	sort(g+1,g+n+1,cmp);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int l=g[i].first.first,r=g[i].first.second,cnt=g[i].second;
		cnt-=ask(r)-ask(l-1);
		if(cnt>0)
		{
			for(int j=r;j>=l&&cnt;j--)
			if(!f[j])
			{
				f[j]=1;
				ans++;cnt--;
				add(j,1);
			}
		}
	}
	printf("%d\n",ans);
}