针对 nth_element 函数,如果用被注释掉的运算符重载就会 TLE 成 20pts,用结构体下面的比较函数就可以 AC
怎么会是呢,有没有大佬救一救 QAQ
int cur;
struct Node{
int x[K];
int val, sum, lc, rc;
int mn[K], mx[K];
}l, h, t[N];
bool cmp(int x, int y){return t[x].x[cur] < t[y].x[cur];}
build 部分参照的是 OI−Wiki:
int build(int l, int r, int d = 0){
cur = d;
int mid = (l + r) >> 1;
nth_element(id + l, id + mid, id + r + 1, cmp);
int now = id[mid];
if(l < mid) t[now].lc = build(l, mid - 1, d ^ 1);
if(mid < r) t[now].rc = build(mid + 1, r, d ^ 1);
pushup(now);
return now;
}