对每个点 P，把它对 m 个半平面的判定看成一个 01 串：第 j 位为 1 表示 P 不满足第 j 个半平面。那么询问 [l,r] 就是求在 [l,r] 内全为 0 的点的权值和。
考虑如何求出每个点是否属于半平面，把每 w = 64 个半平面分成一块，由于 B_j > 0，对于一个固定的 x，属于半平面的一定是一个前缀，即 y \le k。考虑求出 w 条直线在 x 时 y 的大小，排序后求出每个前缀对应的二进制状态。由于交点只有 O(w^2) 个，顺序只会变化 O(w^2) 次，每次交换两个数的位置，可以做到 O(w)。查询就二分。一个块的复杂度是 O(n \log w +w^3)。总复杂度是 O(\frac{nm\log w}{w}+mw^2)。
接下来考虑查询操作。把 B 个半平面分一块，记当前块为 [L,R]，处理所有 l \in [L, R], r > R 的询问。对每个点记：
$v$：块右边第一个 $1$ 的位置。
这个点对询问 $[l, r]$ 有贡献等价于 $l > u$ 且 $r < v$。
于是按 $r$ 从右往左扫，求 $l > u$ 的点的和。那么有 $O(\frac{nm}{B})$ 次加法，$O(q)$ 次查询。对值域分块，值域只有 $O(B)$，容易做到 $O(1)-O(\sqrt{B})$。跨块的总操作次数是 $O(\frac{nm}{B}+q\sqrt{B})$。
接下来考虑在一个块内的所有询问。
对块内分治，设中点为 $mid$。对一个点权值为 $w$，找出覆盖 $mid,mid+1$ 的最长连续零段 $[a,b]$。若这两位中有 $1$，这个点就没有贡献。
询问 $[l,r]$ 的答案就是
$$
\sum_{[a,b]\supseteq[l,r]} w
$$
这个就做一遍二维前缀和即可求出。
但是还有一个问题，就是每层有 $n$ 个点要求 $a,b$，注意到属于半平面情况相同的点是本质相同的，可以合并。$k$ 个半平面最多有 $O(k^2)$ 个不同的点。记一个长度为 $B$ 块的操作次数是 $F(B)$。
有
$$
F(n)=2F(n/2)+O(n^2)
$$
所以一个块的操作次数是 $O(B^2+n)$ 的。块内总的操作次数是 $O(mB+\frac{nm}{B})$ 的。
总的操作次数是 $O(mB + \frac{nm}{B} + q\sqrt{B})$ 的，方便实现 $B = 256$。时间复杂度瓶颈就是处理出每个点属于哪些半平面。时间复杂度是 $O(\frac{nm\log w}{w}+mw^2)$。
## 代码
::::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
class Data {
friend int main();
private:
unsigned short x1,x2,x3,x4;
public:
void add(const Data &a,const Data &b);
void sub(const Data &a,const Data &b);
void clr();
};
namespace chesed {
using ll = long long;
using ull = unsigned long long;
const int B = 256;
struct Point {
int x, y, id;
bool operator < (const Point &p) const { return x < p.x; }
};
struct Line { int a, b, c; };
struct Query {
int l, r, id;
bool operator < (const Query &p) const { return r > p.r; }
};
using Mask = array<ull, 4>;
struct Hash {
size_t operator () (const Mask &a) const {
ull h = 0;
for (ull x : a) h = (h ^ x) * 11995408973635179863ull, h ^= h >> 31;
return h;
}
};
using Table = unordered_map<Mask, Data, Hash>;
inline void add(Data &a, const Data &b) {
Data t;
t.add(a, b);
a = t;
}
inline void put(Table &f, const Mask &s, const Data &w) {
auto [it, ok] = f.try_emplace(s);
if (ok) it->second = w;
else add(it->second, w);
}
inline int first(const Mask &s, int def) {
for (int j = 0; j < 4; j ++)
if (s[j]) return j * 64 + __builtin_ctzll(s[j]);
return def;
}
inline int last(const Mask &s, int def) {
for (int j = 3; j >= 0; j --)
if (s[j]) return j * 64 + 63 - __builtin_clzll(s[j]);
return def;
}
inline bool lower_line(const Line &u, const Line &v, int x) {
ll h = (u.c - 1ll * u.a * x) * v.b;
ll k = (v.c - 1ll * v.a * x) * u.b;
if (h != k) return h < k;
return 1ll * u.a * v.b > 1ll * v.a * u.b;
}
void build(const vector<Point> &p, const Line *a, int k, int id, vector<Mask> &s) {
vector<int> ev;
int ord[64];
ull pre[65], all = k == 64 ? ~0ull : (1ull << k) - 1;
iota(ord, ord + k, 0);
ev.push_back(p.front().x);
for (int i = 0; i < k; i ++)
for (int j = 0; j < i; j ++) {
ll den = 1ll * a[i].a * a[j].b - 1ll * a[j].a * a[i].b;
ll num = 1ll * a[i].c * a[j].b - 1ll * a[j].c * a[i].b;
if (!den) continue;
if (den < 0) den = -den, num = -num;
ll x = num / den + (num % den > 0);
if (x > p.front().x && x <= p.back().x) ev.push_back(x);
}
sort(ev.begin(), ev.end());
size_t pos = 0;
for (int i = 0; i < (int)p.size(); i ++) {
int x = p[i].x, y = p[i].y;
if (pos < ev.size() && ev[pos] <= x) {
while (pos < ev.size() && ev[pos] <= x) pos ++;
for (int j = 1; j < k; j ++) {
int v = ord[j], t = j;
while (t && lower_line(a[v], a[ord[t - 1]], x))
ord[t] = ord[t - 1], t --;
ord[t] = v;
}
pre[0] = 0;
for (int j = 0; j < k; j ++) pre[j + 1] = pre[j] | (1ull << ord[j]);
}
int l = 0, r = k;
while (l < r) {
int mid = (l + r) >> 1;
const Line &v = a[ord[mid]];
if (1ll * v.a * x + 1ll * v.b * y >= v.c) l = mid + 1;
else r = mid;
}
s[i][id] = all ^ pre[l];
}
}
Data res[B][B];
void dfs(int l, int r, const Table &f) {
if (l == r) {
auto it = f.find(Mask{});
res[l][r].clr();
if (it != f.end()) res[l][r] = it->second;
return;
}
int mid = (l + r) >> 1;
Mask cut{};
for (int j = l; j <= mid; j ++) cut[j >> 6] |= 1ull << (j & 63);
Table lf, rt;
for (int i = l; i <= mid; i ++)
for (int j = mid + 1; j <= r; j ++) res[i][j].clr();
for (const auto &e : f) {
Mask a, b;
for (int j = 0; j < 4; j ++) {
a[j] = e.first[j] & cut[j];
b[j] = e.first[j] ^ a[j];
}
put(lf, a, e.second);
put(rt, b, e.second);
int i = last(a, l - 1) + 1, j = first(b, r + 1) - 1;
if (i <= mid && j > mid) add(res[i][j], e.second);
}
for (int i = l + 1; i <= mid; i ++)
for (int j = mid + 1; j <= r; j ++) add(res[i][j], res[i - 1][j]);
for (int i = l; i <= mid; i ++)
for (int j = r - 1; j > mid; j --) add(res[i][j], res[i][j + 1]);
dfs(l, mid, lf);
dfs(mid + 1, r, rt);
}
}
void solve(int n, int xy[][2], Data d[], int m, int abc[][3],
int q, int lr[][2], Data ans[]) {
using namespace chesed;
vector<Point> p(n);
for (int i = 0; i < n; i ++) p[i] = {xy[i + 1][0], xy[i + 1][1], i + 1};
sort(p.begin(), p.end());
vector<Line> a(m + 1);
for (int i = 1; i <= m; i ++) a[i] = {abc[i][0], abc[i][1], abc[i][2]};
int nb = (m + B - 1) / B;
vector<vector<Query>> in(nb), cr(nb);
for (int i = 1; i <= q; i ++) {
int l = lr[i][0], r = lr[i][1], b = (l - 1) / B;
if ((r - 1) / B == b) in[b].push_back({l, r, i});
else cr[b].push_back({l, r, i});
}
vector<Mask> s(n);
vector<int> nxt(n, m + 1), lk(n), hd(m + 2);
for (int b = nb - 1; b >= 0; b --) {
int L = b * B + 1, len = min(B, m - L + 1);
fill(s.begin(), s.end(), Mask{});
for (int j = 0; j < len; j += 64)
build(p, &a[L + j], min(64, len - j), j >> 6, s);
if (!in[b].empty()) {
Table f;
f.reserve(min(n, 1 + len * (len + 1) / 2));
for (int i = 0; i < n; i ++) put(f, s[i], d[p[i].id]);
dfs(0, len - 1, f);
for (Query t : in[b]) ans[t.id] = res[t.l - L][t.r - L];
}
if (!cr[b].empty()) {
fill(hd.begin(), hd.end(), -1);
for (int i = 0; i < n; i ++) {
lk[i] = hd[nxt[i]];
hd[nxt[i]] = i;
}
Data cnt[B], sum[B / 16];
for (auto &w : cnt) w.clr();
for (auto &w : sum) w.clr();
sort(cr[b].begin(), cr[b].end());
int pos = m + 1;
for (Query t : cr[b]) {
while (pos > t.r) {
for (int i = hd[pos]; i != -1; i = lk[i]) {
int j = last(s[i], -1) + 1;
if (j == len) continue;
add(cnt[j], d[p[i].id]);
add(sum[j >> 4], d[p[i].id]);
}
pos --;
}
int k = t.l - L + 1, g = k >> 4;
Data w;
w.clr();
for (int j = 0; j < g; j ++) add(w, sum[j]);
for (int j = g * 16; j < k; j ++) add(w, cnt[j]);
ans[t.id] = w;
}
}
for (int i = 0; i < n; i ++) {
int j = first(s[i], len);
if (j < len) nxt[i] = L + j;
}
}
}
```
::::