题意

给定一个 $n$ 个点的数轴和 $m$ 条线段，每个点最多覆盖 $a_i$ 次，求最多覆盖多少条线段。

$1\le n,m\le 10^5$。

题解

贪心：

把所有线段按右端点从左往右，左端点从右往左排序。

从前向后扫，能放就放，贪心正确性同线段覆盖（会议安排）。

实现上需要写一棵线段树，维护区间最小值和区间减 $1$。

代码

// Problem: [USACO10MAR]Barn Allocation G
// Made by: Acc_Robin
#include<bits/stdc++.h>
using namespace std;
enum{N=100009,M=N<<2};
int v[M],t[M],L[M],R[M];
void bd(int o,int l,int r){
 if((L[o]=l)==(R[o]=r))
  return cin>>v[o],void();
 int md=l+r>>1,lc=o<<1,rc=lc|1;
 bd(lc,l,md),bd(rc,md+1,r);
 v[o]=min(v[lc],v[rc]);
}
void mdf(int o,int l,int r){
 if(l<=L[o]&&R[o]<=r)
  return --v[o],++t[o],void();
 int md=L[o]+R[o]>>1,lc=o<<1,rc=lc|1;
 if(t[o]){
  v[lc]-=t[o],v[rc]-=t[o];
  t[lc]+=t[o],t[rc]+=t[o],t[o]=0;
 }
 if(l<=md)mdf(lc,l,r);
 if(r>md)mdf(rc,l,r);
 v[o]=min(v[lc],v[rc]);
}
int ask(int o,int l,int r){
 if(l<=L[o]&&R[o]<=r)return v[o];
 int md=L[o]+R[o]>>1,lc=o<<1,rc=lc|1,z=1e9;
 if(t[o]){
  v[lc]-=t[o],v[rc]-=t[o];
  t[lc]+=t[o],t[rc]+=t[o],t[o]=0;
 } 
 if(l<=md)z=ask(lc,l,r);
 if(r>md)z=min(z,ask(rc,l,r));
 return z;
}
struct T{int x,y;};
int main(){
 int n,m,z=0;
 cin>>n>>m,bd(1,1,n);
 vector<T>v(m);
 for(auto&[x,y]:v)cin>>x>>y;
 sort(begin(v),end(v),[](T a,T b){return a.y<b.y||a.y==b.y&&a.x>b.x;});
 for(auto[x,y]:v)if(ask(1,x,y)>0)mdf(1,x,y),++z;
 cout<<z<<'\n';
}