# 任务查询系统

# Description

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

# Input

输入文件第一行包含两个空格分开的正整数$m$和$n$，分别表示任务总数和时间范围。接下来 $m$行，每行包含三个空格 分开的正整数 $S_i$、$E_i$和 $P_i$($S_i \leq E_i$)，描述一个任务。接下来n行，每行包含四个空格分开的整数 $X_i$、$A_i$、$B_i$和 $C_i$， 描述一次查询。查询的参数 $K_i$需要由公式 $K_i=1+(A_i*Pre+B_i) mod C_i$计算得到。其中Pre表示上一次查询的结果， 对于第一次查询，$Pre=1$。

# Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

# 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小之和。

区间k小的查询由前缀和思想，在$s_i$秒处+1，在$e_i+1$秒处 - 1，维护区间和即可。

第$x$秒的状况会在第$x - 1$秒的状况基础上发生改变（第$x$秒有任务结束/开始），所以会有大量重复，考虑用主席树维护。

感觉离散化能力倒是见长orz

# Code

//=============================================================
// File Name: loj-2097.cpp
// Author: Wycer
// Created Time: 2018-05-07 22:36
//=============================================================
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
const int N = 1e5 + 10;
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m, s[N], e[N], p[N];
void readin()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
    {
        s[i] = read();
        e[i] = read();
        if (s[i] > e[i])
            swap(s[i], e[i]);
        p[i] = read();
    }
}

struct node
{
    int l, r, cnt;
    long long sum;
    node()
    {
        l = r = cnt = sum = 0;
    }
} tr[40 * N];
int cnt = 0;

void insert(int &k, int l, int r, int pos, int x)
{
    // tr[k = ++cnt] = tr[k];
    tr[++cnt] = tr[k];
    k = cnt;
    if (x > 0)
        ++tr[k].cnt;
    else
        --tr[k].cnt;
    tr[k].sum += x;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
        insert(tr[k].l, l, mid, pos, x);
    else
        insert(tr[k].r, mid + 1, r, pos, x);
}

long long query(int k, int l, int r, int x)
{
    if (l == r)
        return tr[k].sum;
    int mid = (l + r) >> 1;
    int tmp = tr[tr[k].l].cnt;
    if (x <= tmp)
        return query(tr[k].l, l, mid, x);
    else
        return tr[tr[k].l].sum + query(tr[k].r, mid + 1, r, x - tmp);
}

int tag[N], r[N], root[N];
bool cmp(int a, int b)
{
    return p[a] < p[b];
}
bool cmp2(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first < b.first;
}

vector<pair<int, int>> vec;
void prework()
{
    for (int i = 1; i <= n; ++i)
        tag[i] = i;
    sort(tag + 1, tag + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
        r[tag[i]] = i;

    for (int i = 1; i <= n; ++i)
    {
        vec.push_back(make_pair(s[i], r[i]));
        vec.push_back(make_pair(e[i] + 1, -r[i]));
    }
    sort(vec.begin(), vec.end(), cmp2);

    vector<pair<int, int>>::iterator it = vec.begin();
    for (int i = 1; i <= m; ++i)
    {
        root[i] = root[i - 1];
        while (it != vec.end() && i == it->first)
        {
            if (it->second > 0)
                insert(root[i], 1, m, it->second, p[tag[it->second]]);
            else
                insert(root[i], 1, m, -it->second, -p[tag[-it->second]]);
            ++it;
        }
    }
}

void solve()
{
    int k, x, a, b, c;
    long long pre = 1;
    for (int i = 1; i <= m; ++i)
    {
        x = read();
        a = read();
        b = read();
        c = read();
        k = 1 + (a * pre + b) % c;
        printf("%lld\n", pre = query(root[x], 1, m, k));
    }
}

int main()
{
    readin();
    prework();
    solve();
    return 0;
}