codeforce 369E 树状数组+排序 一维下 求点集覆盖线段数量

题意：

在一维的x轴上

给定n个线段， m个询问

每个询问 cut个点， 问该点集覆盖的线段数量

思路：

ans[i] 表示 第 i 个询问的答案，设 ans[i] = n, 再减去 不在点集中的线段

对于所有线段[ l, r ] ，按线段左端点 l 递减排序，（相同时 r 大则大）

排序后：对于线段 i , j ( i

【1】 i.l >= j.l （排序的第一条件） if ( i.l == j.l ) => i.r < j.r

【2】 j 区间内包含的线段数 = 树状数组中 点l.r 的权值

证明：

若 i 区间包含在 j 区间内 => ( j.l <= i.l && i.r <= j.r )

排序已满足左条件 ， 判断右条件：

对于 i 线段， 把[1 , i. r ] 区间 +1，若 j. r <= i.r 则 j 包含i 。若不包含，则 树状数组求 j.r 的权值时 也不会计入 i.r

注意上述的j 指的是不符合的区间

bingo~

附第一个测试案例排序后的线段

p >0, 表示该线段是 属于 pth问题

p==0表示输入的n个线段

#include 
  
   
#include 
   
     #define maxn 1000005 struct st { int l,r,p; bool operator <(const st&B) const {return l>B.l||(l==B.l&&r
    
     1) a[++T].l = 1, a[T].r = p-1, a[T].p = i; for (;--s; p=x) { scanf("%d",&x); if (p