1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
const int P = 1e9 + 7;
const LL BASE = 5782344;
const int MAXN = 1e5+10;
int Plus(LL a, LL b) {
return a + b >= P ? (a + b) % P : a + b;
}
int Mult(LL a, LL b) {
return a * b >= P ? a * b % P : a * b;
}
struct Seg {
LL l, r, id;
bool operator < (const Seg &S) const {
return r == S.r ? l == S.l ? id < S.id : l < S.l : r < S.r;
}
} segs[MAXN];
int n, q;
LL p = 0;
Seg calc_seg(LL x, LL y, int id) {
LL l = 2 * y - x, r = 2 * y + x;
if (l > r)
swap(l, r);
return Seg{l, r, id};
}
struct SegTree {
struct Node {
int l, r, mid;
vector<PLI> v;
};
vector<Node> tree;
SegTree(int _n, Seg data[]) {
tree.resize(_n << 2);
build(data, 1, _n);
}
void push_up(int u) {
vector<PLI> &lv = tree[LCH(u)].v, &rv = tree[RCH(u)].v, &v = tree[u].v;
int i = 0, j = 0, len_l = lv.size(), len_r = rv.size();
while (i < len_l && j < len_r) {
if (lv[i] < rv[j])
v.push_back(lv[i++]);
else
v.push_back(rv[j++]);
}
while (i < len_l)
v.push_back(lv[i++]);
while (j < len_r)
v.push_back(rv[j++]);
}
void build(Seg data[], int l, int r, int u = 1) {
tree[u] = Node{l, r, (l + r) >> 1};
tree[u].v.clear();
if (l == r)
tree[u].v.push_back(make_pair(data[l].l, data[l].id));
else {
build(data, l, tree[u].mid, LCH(u));
build(data, tree[u].mid + 1, r, RCH(u));
push_up(u);
}
}
void add_ans(set<LL> &res, LL r, int u) {
for (auto x : tree[u].v) {
if (x.first > r)
break;
else
res.insert(x.second);
}
}
void query(set<LL> &res, LL rr, int l, int r, int u = 1) {
if (l == tree[u].l && r == tree[u].r)
add_ans(res, rr, u);
else {
if (l > tree[u].mid)
query(res, rr, l, r, RCH(u));
else if (r <= tree[u].mid)
query(res, rr, l, r, LCH(u));
else {
query(res, rr, l, tree[u].mid, LCH(u));
query(res, rr, tree[u].mid + 1, r, RCH(u));
}
}
}
};
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
LL x, y;
scanf("%lld%lld", &x, &y);
segs[i] = calc_seg(x, y, i);
}
sort(segs + 1, segs + 1 + n);
SegTree T(n, segs);
while (q--) {
LL a, b;
scanf("%lld%lld", &a, &b);
LL x = - 1 - Plus(p, a), y = Plus(p, b);
Seg s = calc_seg(x, y, 0);
int pos = lower_bound(segs + 1, segs + 1 + n, Seg{-INF, s.l, 0}) - segs;
p = 0;
if (pos <= n) {
set<LL> res;
res.clear();
T.query(res, s.r, pos, n);
LL power = 1;
for (auto x : res) {
p = Plus(p, Mult(power, x));
power = Mult(power, BASE);
}
}
printf("%lld\n", p);
}
return 0;
}
|
