题目描述

UOI 王国正在被 lmx 手下的忍者攻击！忍者非常厉害，因为他们在进攻的时候可以躲在阴影里面使得其他人看不到他们。整个王国除了UOI居住的城堡以外都被占领了。

在城堡前，有 n 个灌木丛，从 1 到 n 编号，lmx 需要安排一些忍者躲在一些灌木丛后面，每个灌木丛里面最多只能容纳一个忍者。

为了保证忍者进攻强度，lmx 提出了 m 个要求。每个要求都有 3 个参数 a[i] b[i] c[i] ,表示从第 a[i] 到 b[i] 个灌木丛里至少需要有 c[i] 个忍者。满足这样要求方案的要求有很多种，lmx 只想知道满足此方案所需的最少忍者数。

输入

第 1 行包含 2 个正整数 n,m 。n 是灌木丛个数，m 是要求个数。 接下来 m 行，其中第 i 行包含 3 个整数 a[i] b[i] c[i] 。表示从第 a[i] 到 b[i] 个灌木丛里至少需要有 c[i] 个忍者。

输出

至少要安排几个忍者。

数据范围

n<=100000 , m<=100000 。

原题

这题用贪心+线段树优化。 main函数写好了：

void query(int o,int l,int r,int b,int c){
    if(b<=l&&r<=c){
        ret+=t[o].sum;
        return ;
    }
    int mid=l+r>>1;
    if(b<=mid)query(c<<1,l,mid,b,c);
    if(c>mid)query(c<<1|1,mid+1,r,b,c);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
        tmp=max(p[i].b,tmp);
    }
    n=tmp;
    build(1,0,n);
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=m;i++){
        int need=p[i].c;
        ret=0;
        query(1,0,n,p[i].a,p[i].b);
        need-=ret;
        if(need<=0){continue ;}
        ans+=need;
        for(int j=p[i].b;need;j--){
            if(!vis[j]){
                vis[j]=1;
                need--;
                update(1,0,n,j);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

剩下的线段树不会了，那位大佬能帮个忙。