任务查询系统

Description

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组$(S_i,E_i,P_i)$描述,$(S_i,E_i,P_i)$表示任务从第Si秒开始,在第Ei秒后结束(第$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;
}