cdq 分治

CF12D Ball

额,自己找出 bug 来了。 算是提醒一下后人吧。 错误: cdq 分治首先按照第一维度排序是没错,但是本题要求严格大于,不带等号。分治时保证了左区间第一维度**大于等于**右区间。发现问题了吗?对于等于号特殊处理即可。 我的处理方法:首先找出左区间第一维度最小值,这个最小值一定大于等于右区间最大值。所以对于左区间内等于最小值的额外开一个树状数组,当右区间出现等于最小值的数字时,减去这部分即可。 ```cpp int i = l, j = mid, minn = 2e9; for (int k = l; k <= mid; k++) minn = min(minn, s[k].x); while (++j <= r) { while (i <= mid && s[j].y < s[i].y) { T.add(s[i].z, s[i].cnt); if (s[i].x == minn) G.add(s[i].z, s[i].cnt); ++i; } if (s[j].x == minn) s[j].ans -= G.query(limit) - G.query(s[j].z); s[j].ans += T.query(limit) - T.query(s[j].z); } ```
by MarchKid_Joe @ 2023-02-10 15:44:27


|