第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行： 第i+N+1行表示2个整数 A_i和B_i

* 第一行： 一个整数表示最多能够被满足的要求数

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

3

(题目翻译by hzwer)

这题要注意贪心顺序是从右到左（确定贪心顺序的方法是举反例），我在这点上wa了一下。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

struct seg{

    seg(){ind=0;}

    int lim,ind;

}tr[400100];

struct req{

    int l,r;

    bool operator<(const req h)const{return r<h.r;}//贪心顺序从右到左;

}d[100100];

void pushup(int k)

{

    tr[k].lim=min(tr[k<<1].lim,tr[k<<1|1].lim);

}

void pushdown(int k)

{

    if(tr[k].ind){

        tr[k<<1].lim-=tr[k].ind;

        tr[k<<1].ind+=tr[k].ind;

        tr[k<<1|1].lim-=tr[k].ind;

        tr[k<<1|1].ind+=tr[k].ind;

        tr[k].ind=0;

    }

}

void build(int s,int t,int k)

{

    if(!(s^t)){

        scanf("%d",&tr[k].lim);

        return;

    }int m=(s+t)>>1;

    build(s,m,k<<1);

    build(m+1,t,k<<1|1);

    pushup(k);

}

bool query(int s,int t,int k,int l,int r)

{

    if(l<=s&&t<=r)return tr[k].lim>0;

    pushdown(k);

    int m=(s+t)>>1;

    bool tp1=true,tp2=true;

    if(l<=m)tp1=query(s,m,k<<1,l,r);

    if(m<r)tp2=query(m+1,t,k<<1|1,l,r);

    return tp1&tp2;

}

void update(int s,int t,int k,int l,int r)

{

    if(l<=s&&t<=r){

        tr[k].ind++;

        tr[k].lim--;

        return;

    }pushdown(k);

    int m=(s+t)>>1;

    if(l<=m)update(s,m,k<<1,l,r);

    if(m<r)update(m+1,t,k<<1|1,l,r);

    pushup(k);

}

int main()

{

    int n,m,res=0;

    scanf("%d%d",&n,&m);

    build(1,n,1);

    for(int i=1;i<=m;i++)scanf("%d%d",&d[i].l,&d[i].r);

    sort(d+1,d+1+m);

    for(int i=1;i<=m;i++)

        if(query(1,n,1,d[i].l,d[i].r)){

            update(1,n,1,d[i].l,d[i].r);

            ++res;

        }printf("%d\n",res);

    return 0;

}