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

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);
}