CF Educational Codeforces Round 10 D. Nested Segments 离散化+树状数组

题目链接:http://codeforces.com/problemset/problem/652/D

大意:给若干个线段,保证线段端点不重合,问每个线段内部包含了多少个线段。

方法是对所有线段的端点值离散化,按照左端点从大到小排序,顺着这个顺序处理所有线段,那么满足在它内部的线段一定是之前已经扫到过的。用树状数组判断有多少是在右端点范围内。

 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <set>
using namespace std; const int N=4e5+;
int a[N];
int b[N];
int lowbit(int x) {
return x&(-x);
}
int get(int x) {
int ret=;
while (x) {
ret+=a[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int add) {
while (x<N) {
a[x]+=add;
x+=lowbit(x);
}
}
struct Seg{
int l,r;
int id; Seg() { } Seg(int l, int r, int id) : l(l), r(r), id(id) { }
bool operator < (const Seg & o) const {
return l>o.l;
}
}seg[N];
int ans[N];
int main () {
int n;
scanf("%d",&n);
int t=;
for (int i=;i<=n;i++) {
scanf("%d %d",&seg[i].l,&seg[i].r);
b[t++]=seg[i].l;
b[t++]=seg[i].r;
seg[i].id=i;
}
sort(b,b+t);
int k=unique(b,b+t)-b;
for (int i=;i<=n;i++) {
seg[i].l=lower_bound(b,b+t,seg[i].l)-b+;
seg[i].r=lower_bound(b,b + t,seg[i].r)-b+;
}
sort(seg+,seg++n);
for (int i=;i<=n;i++) {
int id=seg[i].id;
ans[id]=get(seg[i].r);
add(seg[i].r,);
}
for (int i=;i<=n;i++) {
printf("%d\n",ans[i]);
}
return ;
}
上一篇:计算机考研复试之英语口语面试


下一篇:vue的keep-alive内置组件缓存