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

You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·10⁵) — the number of segments on a line.

Each of the next n lines contains two integers l_i and r_i ( - 10⁹ ≤ l_i < r_i ≤ 10⁹) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.

Output

Print n lines. The j-th of them should contain the only integer a_j — the number of segments contained in the j-th segment.

Example

Input

Output

Input

Output

0
1
1

题意：
n个线段
告诉每条线段左右端点坐标
要求输出每条线段下面有多少条线段

做法：

对右端点进行离散化
对左端点进行排序
然后从左端点靠后的向前遍历
也就是保证后遍历到的元素所包含的线段一定在之前就有遍历过
然后就是有几个的问题
看在该线段右端点之前有几个线段的右端点比它小，就是有几个线段被它包含，就是答案
可以维护一个树状数组去写。

代码：

  1 #include<iostream>
  2 using namespace std;
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<map>
  6 #include<algorithm>
  7 const int MAXN=502000;
  8 int pn ,m,i,t[500201],l,r;//num:原数组；t：树状数组 
  9 map<int,int> maps;
 10 typedef int LL;
 11 int maxn;//最大离散数
 12 inline int read()
 13 {
 14     int k=0;
 15     char f=1;
 16     char c=getchar();
 17     for(;!isdigit(c);c=getchar() )
 18         if(c=='-')
 19             f=-1;
 20     for(;isdigit(c);c=getchar() )
 21         k=k*10+c-'0';
 22     return k*f;
 23 }
 24 void ls(int a[],int n){//离散化
 25     maxn=0;
 26     maps.clear();
 27     for(int i=0;i<n;i++){
 28         if(i!=0&&a[i]==a[i-1])
 29             continue;
 30         if(i==0||a[i]-a[i-1]==1)
 31             maxn+=1;
 32         else
 33             maxn+=2;
 34         maps[a[i]]=maxn;
 35     }
 36     pn=maxn+1;
 37 }
 38 struct data{
 39     int l,r,b;
 40     bool operator<(const struct data&pt)const{
 41         if(l==pt.l)
 42             return r<pt.r;
 43         return l<pt.l;
 44     }
 45 };
 46 
 47 int ans[250000];
 48 data ss[250000];
 49 int lowbit(int x)
 50 {
 51     return x&(-x);
 52 }
 53 void change(int x,int p)//将第x个数加p 
 54 {
 55     while(x<=pn)
 56     {
 57         t[x]+=p;
 58         x+=lowbit(x);
 59     }
 60     return;
 61 }
 62 int sum(int k)//前k个数的和 
 63 {
 64     int ans=0;
 65     while(k>0)
 66     {
 67         ans+=t[k];
 68         k-=lowbit(k);
 69     }
 70     return ans;
 71 }
 72 int ask(int l,int r)//求l-r区间和 
 73 {
 74     return sum(r)-sum(l-1); 
 75 }
 76 
 77 int a[MAXN*3];
 78 int b[MAXN*3];
 79 
 80 void deal(){
 81     int n;
 82     n=read();
 83     int l,r;
 84     for(int i=0;i<n;i++){
 85         ss[i].b=i;
 86         ss[i].l=read();
 87         ss[i].r=read();
 88         b[i]=ss[i].r;
 89     }
 90     sort(b,b+n);
 91     ls(b,n);
 92     for(int i=0;i<n;i++){
 93         ss[i].r=maps[ss[i].r];
 94     }
 95     sort(ss,ss+n);
 96     memset(t,0,sizeof(t));    
 97     for(int i=n-1;i>=0;i--){
 98         change(ss[i].r,1);
 99         //cout<<" "<<ss[i].b<<" "<<ss[i].r+1<<" "<<maxn+1<<endl;
100     //    cout<<ss[i].b<<" "<<ss[i].r<<" "<<ss[i].r-1<<endl;
101         int pans=ask(1,ss[i].r-1);
102         ans[ss[i].b]=pans;
103     }
104     for(int i=0;i<n;i++){
105         printf("%d\n",ans[i]);
106     }
107 }
108 int main(){
109     deal();
110     return 0;
111 }

秒客网

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

相关文章