思路都已经讲得很清楚了,这里提供一个权值线段树优化版本,时间复杂度同样是$O(n\log n)$(不爱用STL的我手动滑稽)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
template <typename T> void in(T &x) {
x = 0; T f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = 10*x+ch-'0'; ch = getchar();}
x *= f;
}
template <typename T> void out(T x) {
if(x < 0) putchar('-'),x = -x;
if(x > 9) out(x/10);
putchar(x%10+'0');
}
//---------------------------------------------------------------
const int N = 2505,M = 1005;
int n,m,ans;
struct cow {
int l,r;
bool operator < (const cow &sed) const {
return l > sed.l;
}
}c[N];
int sum[M<<2],mx[M<<2];
void A(int u,int l,int r,int x,int k) {
if(l == r) {
sum[u] += k;
mx[u] = (sum[u] ? l : 0);
return;
}
int mid = (l+r)>>1;
if(x <= mid) A(u<<1,l,mid,x,k);
else A(u<<1|1,mid+1,r,x,k);
sum[u] = sum[u<<1]+sum[u<<1|1];
mx[u] = max(mx[u<<1],mx[u<<1|1]);
}
int Q(int u,int l,int r,int x,int y) {
if(x <= l && y >= r) return mx[u];
int mid = (l+r)>>1,res = 0;
if(x <= mid) res = max(res,Q(u<<1,l,mid,x,y));
if(y > mid) res = max(res,Q(u<<1|1,mid+1,r,x,y));
return res;
}
int main() {
int i,a,cnt; in(n); in(m);
for(i = 1;i <= n; ++i) {
in(c[i].l); in(c[i].r);
}
sort(c+1,c+n+1);
for(i = 1;i <= m; ++i) {
in(a); in(cnt);
A(1,1,1000,a,cnt);
}
for(i = 1;i <= n; ++i) {
int pos = Q(1,1,1000,c[i].l,c[i].r);
if(!pos) continue;
++ans; A(1,1,1000,pos,-1);
}
out(ans);
return 0;
}
orz
权值线段树NB!