codeforces 652D Nested Segments 离散化+树状数组

题意:给你若干个区间,询问每个区间包含几个其它区间

分析:区间范围比较大,然后离散化,按右端点排序,每次更新树状数组中的区间左端点,查询区间和

注:(都是套路)

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=2e5+;
const int INF=0x3f3f3f3f;
int a[N<<],n,d;
struct pair{
int l,r,id;
bool operator<(const pair &e)const{
return r<e.r;
}
}p[N];
int c[N<<];
void change(int x){
for(int i=x;i<=d;i+=i&(-i))
++c[i];
}
int query(int x){
int ans=;
for(int i=x;i>;i-=i&(-i))
ans+=c[i];
return ans;
}
int res[N];
int main(){
scanf("%d",&n);
int tot=;
for(int i=;i<=n;++i){
scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
a[++tot]=p[i].l;
a[++tot]=p[i].r;
}
sort(a+,a++tot);
d=;
for(int i=;i<=tot;++i)
if(a[i]!=a[i-])a[++d]=a[i];
sort(p+,p++n);
for(int i=;i<=n;++i){
int r=lower_bound(a+,a++d,p[i].r)-a;
int l=lower_bound(a+,a++d,p[i].l)-a;
res[p[i].id]=query(r)-query(l-);
change(l);
}
for(int i=;i<=n;++i)
printf("%d\n",res[i]);
return ;
}
上一篇:学习笔记49—matlab FDR校正


下一篇:HDU 1242 Rescue(BFS),ZOJ 1649