#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
int a[63005];
int lowbit(int x)
{
    return x&(-x);
}
void upd(int x)
{
    while(x <= 60000){
        ++a[x];
        x += lowbit(x);
    }
}
int query(int x)
{
    int ret = 0;
    while(x){
        ret += a[x];
        x -= lowbit(x);
    }
    return ret;
}
struct OP
{
    int a, b, c;
} op[63005];
int fa[63005];
bool cmp(OP x,OP y)
{
    if(x.b == y.b) return x.a < y.a;
    return x.b < y.b;
}
int fd(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = fd(fa[x]);
}
int main()
{
	int i, j, n;
    while(~scanf("%d",&n)){
        for(i=0; i<n; ++i){
            scanf("%d%d%d",&op[i].a,&op[i].b,&op[i].c);
        }
        for(i=0; i<=60000; ++i) fa[i] = i;
        int ans = 0;
        sort(op, op+n, cmp);
        memset(a, 0, sizeof(a));
        for(i=0; i<n; ++i){
            ++op[i].a;
            ++op[i].b;
            int it;
            int cur = query(op[i].b) - query(op[i].a-1);
            if(cur < op[i].c){
                op[i].c -= cur;
                for(j=op[i].b; op[i].c; --op[i].c, ++ans){
                    it = fd(j);
                    upd(it);
                    fa[it] = it-1;
                    j = it-1;
                }
            }
        }
        printf("%d\n",ans);
    }
	return 0;
}

• Re:贪心AC，树状数组+并查集维护 (1550) gouyiba 2015-05-02 23:42:57
• Re:贪心AC，树状数组+并查集维护 (2) q847087628 2016-01-08 14:12:36