线段树上二分 别样的线段树
D. Points原题链接：https://codeforces.com/problemset/problem/19/D
开始思路：
看到题目后有一个想法，先将所有坐标进行离散化，在横坐标方向上建立线段树，每个节点维护一个 \(set\) 即对应区间 \(l\) ~ \(r\) 上 \(y\) 轴上的坐标，然后每次增删都可以在 \(O(log^2(n))\) 内完成，然后查询时，对区间进行直接二分，然后每次将对应区间的集合合并后取出，每次有效性检验检查是否存在大于当前查询的 \(y\)，直接二分时间复杂度为 \(O(log(n))\)，每次取出时间复杂度最坏情况下可 \(O(n)\)，每次 \(upper\) _ \(bound\) 查询为 \(O(log(n))\)，三者相乘，不出意外直接 \(tle\)了
\(tle\)代码：
#includeusing namespace std; typedef long long ll;typedef pair PII;const int N=2e5+10,mod=998244353;int n,m;vector all,query;vector points;struct Node{ int l,r; set ys;}tr;void build(int u,int l,int r){ if(l==r) tr={l,r}; else{ tr={l,r}; int mid=l+r>>1; build(u
页:
[1]