题目地址：洛谷：【P3168】[CQOI2015]任务查询系统 – 洛谷、BZOJ：Problem 3932. — [CQOI2015]任务查询系统

题目描述

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

输入输出格式

输入格式：
输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，对于第一次查询，Pre=1。

输出格式：
输出共n行，每行一个整数，表示查询结果。

输入输出样例

输入样例#1：

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

输出样例#1：

2
8
11

说明

样例解释
K1 = (1*1+3)%2+1 = 1
K2 = (1*2+3)%4+1 = 2
K3 = (2*8+4)%3+1 = 3
对于100%的数据，1<=m,n,Si,Ei,Ci<=100000，0<=Ai,Bi<=100000，1<=Pi<=10000000，Xi为1到n的一个排列

题解

这个题强制在线了，在线做这种问题就需要主席树了。
我们先离散化优先度，在每个任务开始的时候向主席树中插入优先度，结束以后删除优先度。由于查询针对一个时间，直接用该时间的根来查就好了。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, m;
std::vector<LL> vec;

#define mid ((l + r) >> 1)

struct Node {
    int lch, rch, siz, id;
    LL sum;
} sgt[MAXN << 6];
int rt[MAXN], tot;

inline void insert(int &o, int l, int r, int x, int id) {
    if(sgt[o].id != id) {
        sgt[++tot] = sgt[o]; o = tot; sgt[o].id = id;
    }
    sgt[o].siz++;
    sgt[o].sum += vec[x];
    if(l == r) return;
    if(x <= mid) insert(sgt[o].lch, l, mid, x, id);
    else insert(sgt[o].rch, mid + 1, r, x, id);
}

inline void erase(int &o, int l, int r, int x, int id) {
    if(sgt[o].id != id) {
        sgt[++tot] = sgt[o]; o = tot; sgt[o].id = id;
    }
    sgt[o].siz--;
    sgt[o].sum -= vec[x];
    if(l == r) return;
    if(x <= mid) erase(sgt[o].lch, l, mid, x, id);
    else erase(sgt[o].rch, mid + 1, r, x, id);
}

inline LL query(int o, int l, int r, int rk) {
    if(sgt[o].siz <= rk) return sgt[o].sum;
    if(l == r) return sgt[o].sum / sgt[o].siz * rk;
    int siz = sgt[sgt[o].lch].siz;
    LL res = 0;
    res += query(sgt[o].lch, l, mid, rk);
    if(rk > siz) res += query(sgt[o].rch, mid + 1, r, rk - siz);
    return res;
}

struct Task {
    LL s, t, prio;
} t1[MAXN], t2[MAXN];

inline bool cmp1(Task a, Task b) {
    return a.s < b.s;
}

inline bool cmp2(Task a, Task b) {
    return a.t < b.t;
}

LL k, x, a, b, c, pre = 1;

int main() {
    m = readint(); n = readint();
    for(int i = 1; i <= m; i++) {
        t1[i].s = t2[i].s = readint();
        t1[i].t = t2[i].t = readint();
        vec.push_back(t1[i].prio = t2[i].prio = readint());
    }
    vec.push_back(0);
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    std::sort(t1 + 1, t1 + m + 1, cmp1);
    std::sort(t2 + 1, t2 + m + 1, cmp2);
    int i1 = 1, i2 = 1;
    for(int i = 1; i <= n; i++) {
        rt[i] = rt[i - 1];
        for(; t1[i1].s == i; i1++) {
            insert(rt[i], 1, vec.size() - 1, 
                std::lower_bound(vec.begin(), vec.end(), t1[i1].prio) - vec.begin(), i);
        }
        for(; t2[i2].t == i - 1; i2++) {
            erase(rt[i], 1, vec.size() - 1, 
                std::lower_bound(vec.begin(), vec.end(), t2[i2].prio) - vec.begin(), i);
        }
    }
    for(int i = 1; i <= n; i++) {
        x = readint(); a = readint(); b = readint(); c = readint();
        k = (a * pre + b) % c + 1;
        printf("%lld\n", pre = query(rt[x], 1, vec.size() - 1, k));
    }
    return 0;
}