[vijos]1066弱弱的战壕<线段树>

题目链接：https://www.vijos.org/p/1066

这道题没什么难度，只是要一个排序然后就是线段树的基本套路模版了

但是我还是讲一讲思路吧：

　　给出的是坐标x，y，当一个点的x，y都小于等于另外一个点，则这个点就是另外一个点的保护对象，然后我们就可以对x进行一个排序，然后用线段树依次加入纵坐标去更新

保护的数量，这就是这个简单套路

这题不难，就直接上代码吧

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 #include<cstdlib>
 8 #define maxn 15005
 9 using namespace std;
10 
11 struct edge{
12     int l,r,sum;
13 }e[maxn*4];
14 
15 int n,maxy,ans[32005]; 
16 
17 struct point{
18     int x,y;
19 }f[maxn*4];
20 
21 int comp(point a,point b)
22 {
23     return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
24 }
25 
26 void build(int l,int r,int pos)
27 {
28     e[pos].sum=0;e[pos].l=l;e[pos].r=r;
29     if(l!=r)
30     {
31         int mid=(l+r)/2;
32         build(l,mid,pos*2);
33         build(mid+1,r,pos*2+1);        
34     }
35 
36     
37 }
38 
39 void change(int l,int r,int pos)
40 {//将那些纵坐标大于等于l的处理 
41     if(e[pos].l==l&&e[pos].r==r)
42     {
43         e[pos].sum++;
44         return;
45     }
46     if(e[pos].l==e[pos].r)return;
47     int mid=(e[pos].l+e[pos].r)/2;
48     if(mid>=r)
49     {
50         change(l,r,pos*2);
51     }else{
52         if(mid<l)change(l,r,pos*2+1);
53         else{
54             change(l,mid,pos*2);
55             change(mid+1,r,pos*2+1);
56         }
57     }
58     
59 } 
60 
61 int query(int po,int pos)
62 {
63     if(e[pos].l==e[pos].r)return e[pos].sum;
64     int mid=(e[pos].l+e[pos].r)/2;
65     if(po<=mid){
66         return e[pos].sum+query(po,pos*2);
67     }else return e[pos].sum+query(po,pos*2+1);
68     
69 }
70 
71 int main()
72 {
73 
74     scanf("%d",&n);
75     for(int i=0;i<=n-1;i++)
76     {
77         int a,b;
78         scanf("%d%d",&a,&b);
79         f[i].x=a;f[i].y=b;
80         maxy=max(maxy,b);
81     }
82     sort(f,f+n,comp);//首先让x坐标排个序，接下来加点就只用在y坐标上进行处理 
83     build(0,32001,1);
84     for(int i=0;i<=n-1;i++)
85     {
86         ans[query(f[i].y,1)]++; //查看在哪一个答案区间 
87         change(f[i].y,32001,1);//i点加进来后，需要加1的点区间 
88     }
89     for(int i=0;i<n;i++)
90     {
91         printf("%d
",ans[i]);
92     }
93 
94 }