恩，贪心+线段树维护。
CO
/*
PROG: balloc
LANG: C++
ID: boleyn.2
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-27
DESCRIPTION:
TITLE: Barn Allocation [Jaehyun Park/Jeffrey Wang, 2010]
CONTENT:
Farmer John recently opened up a new barn and is now accepting stall
allocation requests from the cows since some of the stalls have a
better view of the pastures.
The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered
1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i
may request a contiguous interval of stalls (A_i, B_i) in which to
roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to
wander among all the stalls in the range A_i..B_i (and the stalls
must always have the capacity for her to wander).
Given M (1 <= M <= 100,000) stall requests, determine the maximum
number of them that can be satisfied without exceeding stall
capacities.
Consider both a barn with 5 stalls that have the capacities shown
and a set cow requests:
Stall id: 1 2 3 4 5
+—+—+—+—+—+
Capacity: | 1 | 3 | 2 | 1 | 3 |
+—+—+—+—+—+
Cow 1 XXXXXXXXXXX (1, 3)
Cow 2 XXXXXXXXXXXXXXX (2, 5)
Cow 3 XXXXXXX (2, 3)
Cow 4 XXXXXXX (4, 5)
FJ can’t satisfy all four cows, since there are too many requests
for stalls 3 and 4.
Noting that Cow 2 requests an interval that includes stalls 3 and
4, we test the hypothesis that cows 1, 3, and 4 can have their
requested stalls. No capacity is exceeded, so the answer for this
set of da
satisfied.
MEMORY LIMIT: 32 MB
TIME LIMIT: 2 seconds
PROBLEM NAME: balloc
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+M+1: Line i+N+1 contains two integers: A_i and B_i
SAMPLE INPUT (file balloc.in):
5 4
1
3
2
1
3
1 3
2 5
2 3
4 5
OUTPUT FORMAT:
* Line 1: The maximum number of requests that can be satisfied
SAMPLE OUTPUT (file balloc.out):
3
*/
#include <stdio.h>
#define MAXN 100000
#define MAXM 100000
#define oo ~(1<<31)
int N,M;
int C[MAXN+1];
int A[MAXM],B[MAXM];
int answer;
int st_min[MAXN<<2],st_cnt[MAXN<<2];
void quick_sort(int L,int R)
{
int mid_A=A[(L+R)>>1];
int mid_B=B[(L+R)>>1];
int i=L,j=R;
while (i<=j)
{
while (A[i]<mid_A||(A[i]==mid_A&&B[i]>mid_B)) i++;
while (A[j]>mid_A||(A[j]==mid_A&&B[j]<mid_B)) j–;
if (i<=j)
{
int swap;
swap=A[i];
A[i]=A[j];
A[j]=swap;
swap=B[i];
B[i]=B[j];
B[j]=swap;
i++;
j–;
}
}
if (L<j) quick_sort(L,j);
if (i<R) quick_sort(i,R);
}
int min(int a,int b)
{
return a<b?a:b;
}
void build(int L,int R,int root=1)
{
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
if (L==R) st_min[root]=C[L];
else
{
build(LL,LR,Lroot);
build(RL,RR,Rroot);
st_min[root]=min(st_min[Lroot],st_min[Rroot]);
}
//printf(“[%d,%d] min:%d\n”,L,R,st_min[root]);
}
void update(int L,int R,int root)
{
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
st_cnt[Lroot]+=st_cnt[root];
st_min[Lroot]-=st_cnt[root];
st_cnt[Rroot]+=st_cnt[root];
st_min[Rroot]-=st_cnt[root];
st_cnt[root]=0;
}
int ask(int l,int r,int L,int R,int root=1)
{
if (l>R||r<L) return oo;
if (l<=L&&R<=r) return st_min[root];
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
update(L,R,root);
return min(ask(l,r,LL,LR,Lroot),ask(l,r,RL,RR,Rroot));
}
void insert(int l,int r,int L,int R,int inc=1,int root=1)
{
if (l>R||r<L) return;
if (l<=L&&R<=r)
{
st_cnt[root]+=inc;
st_min[root]-=inc;
return;
}
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
update(L,R,root);
insert(l,r,LL,LR,inc,Lroot);
insert(l,r,RL,RR,inc,Rroot);
st_min[root]=min(st_min[Lroot],st_min[Rroot]);
}
int main()
{
freopen(“balloc.in”,“r”,stdin);
freopen(“balloc.out”,“w”,stdout);
scanf(“%d %d\n”,&N,&M);
for (int i=1;i<=N;i++)
scanf(“%d\n”,&C[i]);
for (int i=0;i<M;i++)
scanf(“%d %d\n”,&A[i],&B[i]);
build(1,N);
quick_sort(0,M-1);
for (int i=M-1;i>=0;i–)
if (ask(A[i],B[i],1,N))
answer++,insert(A[i],B[i],1,N);
printf(“%d\n”,answer);
fclose(stdin);
fclose(stdout);
return 0;
}