题目链接：传送门

Description

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

Hint

1<=m,n,Si,Ei,Ci<=100000，0<=Ai,Bi<=100000，1<=Pi<=10000000，Xi为1到n的一个排列

Sample Input

4 3 1 2 6 2 3 3 1 3 2 3 3 4 3 1 3 2 1 1 3 4 2 2 4 3

Sample Output

2 8 11

Solution

不是在线的话可以直接差分扫描线+线段树 强制在线的话用可持久化数据结构搞一下就可以了 算是再加强一下代码能力把 有一个细节需要注意：查询的时候到最底层的时候要特判一下，因为第k个位置上的值有多个的话显然不能全都加上

Code

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
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 100000;

int N, M;
int Root[Maxn + 100], Cnt;

vector <int> vec[Maxn + 100];

struct tree
{
    int lson, rson;
    LL val, sum;
}Tree[Maxn * 64 + 100];

inline void build (int &root, int l, int r)
{
    root = ++ Cnt;
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    build (Tree[root].lson, l, mid);
    build (Tree[root].rson, mid + 1, r);
}

inline void push_up (int root)
{
    Tree[root].val = 1ll * (Tree[Tree[root].lson].val + Tree[Tree[root].rson].val);
    Tree[root].sum = 1ll * (Tree[Tree[root].lson].sum + Tree[Tree[root].rson].sum);
}

inline void Insert (int pre, int &now, int l, int r, int x, int d)
{
    now = ++Cnt;
    Tree[now].lson = Tree[pre].lson;
    Tree[now].rson = Tree[pre].rson;
    Tree[now].val = Tree[pre].val;
    Tree[now].sum = Tree[pre].sum;
    if (l == r)
    {
        Tree[now].val += (d > 0) ? 1ll : -1ll;
        Tree[now].sum += 1ll * d;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(Tree[pre].lson, Tree[now].lson, l, mid, x, d);
    else Insert(Tree[pre].rson, Tree[now].rson, mid + 1, r, x, d);
    push_up(now);
}

inline int Query (int root, int l, int r, LL k)
{
    //cout<<root<<" "<<l<<" "<<r<<" *"<<Tree[Tree[root].lson].val<<" "<<Tree[Tree[root].lson].sum<<endl;
    if (l == r)
        return !Tree[root].val ? Tree[root].sum : Tree[root].sum / Tree[root].val * 1ll * k;
    int mid = (l + r) >> 1;
    if (Tree[Tree[root].lson].val >= k)
        return Query(Tree[root].lson, l, mid, k);
    else return Tree[Tree[root].lson].sum + Query(Tree[root].rson, mid + 1, r, k - Tree[Tree[root].lson].val);
}

struct node
{
    int x, y, z, val;
}A[Maxn + 100];

int B[Maxn + 100];

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif

    scanf("%d%d", &M, &N);
    for (int i = 1; i <= M; ++i)
        scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].z), B[i] = A[i].z, A[i].val = A[i].z;

    sort(B + 1, B + M + 1);
    int sz = unique(B + 1, B + M + 1) - B - 1;
    for (int i = 1; i <= M; ++i)
    {
        A[i].z = lower_bound(B + 1, B + sz + 1, A[i].z) - B;
        //cout<<A[i].x<<" "<<A[i].y<<" "<<A[i].z<<endl;
        vec[A[i].x].push_back(i);
        vec[A[i].y + 1].push_back(-i);
    }

    build(Root[0], 1, Maxn);

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j < vec[i].size(); ++j)
        {
            //cout<<vec[i][j]<<" ";
            if (vec[i][j] > 0) Insert(!Root[i] ? Root[i - 1] : Root[i], Root[i], 1, Maxn, A[vec[i][j]].z, A[vec[i][j]].val);
            else Insert(!Root[i] ? Root[i - 1] : Root[i], Root[i], 1, Maxn, A[-vec[i][j]].z, -A[-vec[i][j]].val);
        }
        //cout<<endl;

        if (!vec[i].size()) Root[i] = Root[i - 1];
    }

    LL Ans = 1;
    int x, a, b, c;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d%d%d%d", &x, &a, &b, &c);
        Ans = Query(Root[x], 1, Maxn, 1 + ((a * Ans) + b) % c);
        printf("%lld\n", Ans);
    }

    return 0;
}