2020-2021Brazil-Subregional-Programming-Contest

 1const itn M = 1e9 + 7;
 2const int maxn = 1e5 + 10;
 3int n, q;
 4struct SEG{
 5    ll x, y;
 6    int id;
 7    bool operator < (const SEG &b) const{
 8        return y < b.y;
 9    }
10};
11SEG seg[maxn];
12 
13#define ls (p << 1)
14#define rs ((p << 1) | 1)
15#define mid ((l + r) >> 1)
16 
17struct NODE{
18    ll x; int id;
19    bool operator < (const NODE &b) const{
20        return x > b.x;
21    }
22};
23vector<NODE> st[maxn << 2];
24void build(int p, int l, int r){
25    if(l == r){
26        st[p].push_back({seg[l].x, seg[l].id});
27        return ;
28    }
29    if(l == r) return ;
30    build(ls, l, mid); build(rs, mid + 1, r);
31    st[p].resize(r - l + 1);
32    merge(st[ls].begin(), st[ls].end(), st[rs].begin(), st[rs].end(), st[p].begin());
33}
34 
35//在seg[l] - seg[r]中查询那些：序号至少为lim, 且有可能有交集的所有线段
36int cnt = 0;
37vector<int> res;
38void query(int p, int l, int r, int lim, ll y0){
39    if(r < lim) return ;
40    //如果这一段区间全部满足（意味着右端点一定 > y0)
41    if(l >= lim){
42        int top = (int)st[p].size();
43        for(int i = top - 1; i >= 0; i--){
44            if(st[p][i].x > y0) break;
45            res.push_back(st[p][i].id);
46            cnt++;
47            assert(cnt <= 2000000);
48        }
49        return ;
50    }
51    query(ls, l, mid, lim, y0);
52    query(rs, mid + 1, r, lim, y0);
53}
54 
55 
56int main(){
57//    Fastin;
58    scanf("%d %d", &n, &q);
59    for(int i = 1; i <= n; i++){
60        ll x, y; scanf("%lld %lld ", &x, &y); y *= 2;
61        seg[i].x = y - x; seg[i].y = y + x; seg[i].id = i;
62    }
63    sort(seg + 1, seg + n + 1);
64    build(1, 1, n);
65    
66    const int e = 5782344; ll ans = 0;
67    for(int i = 0; i < q; i++){
68        ll a, b; scanf("%lld %lld", &a, &b);
69        ll x, y;
70        x = -1 - ((ans + a) % M);
71        y = (ans + b) % M; y *= 2;
72        SEG temp; temp.x = 1ll << 60; temp.y = y +x; tmep.id = -1;
73        int lim = (int)(lower_bound(seg + 1, seg + n + 1, temp) - seg);
74        
75        res.clear();
76        query(1, 1, n, lim, y - x);
77        sort(res.begin(), res.end(), greater<int>());
78        ans = 0;
79        for(auto x: res) ans = (ans * e % M + x) % M;
80         
81        printf("%lld\n", ans);
82    }
83    return 0;
84}

1bool operator < (const SEG &b) const{
2  if(y != b.y) return y < b.y;
3  return x < b.x;
4}