BZOJ 3932 - [CQOI2015]任务查询系统

#主席树
Published on 2016-04-04

题目地址

描述

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

样例输入

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

样例输出

2
8
11

分析

本人主席树的第一道题，其实主席树根本没有想象中难，只不过网上的资料大多含糊不清，有的连主席树是权值线段树都没说，我是看的CLJ的论文才搞清楚个大概的。所以大家可以看我写的一篇主席树。
--> 主席树
如果你看过的我写的文章，那么这题就很好做了（大雾！！。建立主席树，权值是优先级（需离散化），每棵树 TiT_i 不再代表区间 [0,i)[0, i) 了，而是时间为 ii 的时候的一棵权值线段树（因为本题不是序列，是时间轴）。
那么对于每个事件，在开头加，结尾减，搞一搞就很容易求出和了！

代码

//  Created by Sengxian on 4/4/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3524 主席树
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <vector>
#define mid (((l) + (r)) / 2)
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 100000 + 3;
struct SegNode *null;
struct SegNode {
    SegNode *ls, *rs;
    ll s, sum;
    inline void maintain() {
        s = ls->s + rs->s;
        sum = ls->sum + rs->sum;
    }
    SegNode(): s(0), sum(0) {ls = null, rs = null;}
}*root[maxn];

int n, m, S[maxn], E[maxn], P[maxn]; //n 任务总数 m 时间范围

vector<int> ps;
void compress() {
    for (int i = 0; i < m; ++i)
        ps.push_back(P[i]);
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (int i = 0; i < m; ++i)
        P[i] = lower_bound(ps.begin(), ps.end(), P[i]) - ps.begin();
}

void init() {
    null = new SegNode();
    null->s = 0, null->sum = 0;
    null->ls = null, null->rs = null;
}

struct state {
    int t, p, op;
    state(int t, int p, int op): t(t), p(p), op(op) {}
    bool operator < (const state &s) const {
        return t < s.t;
    }
};

SegNode *modify(const SegNode *o, int l, int r, int v, int op) {
    if (l >= r) return null;
    SegNode *ne = new SegNode();
    *ne = *o;
    if (r - l == 1) {
        ne->s += op;
        ne->sum += ps[v] * op;
        return ne;
    }
    if (v < mid) ne->ls = modify(ne->ls, l, mid, v, op);
    else ne->rs = modify(ne->rs, mid, r, v, op);
    ne->maintain();
    return ne;
}

ll query(const SegNode *o, int l, int r, int k) {
    if (l >= r || k == 0) return 0;
    if (o->s <= k) return o->sum;
    if (r - l == 1) return (ll)ps[l] * k;
    if (k <= o->ls->s) return query(o->ls, l, mid, k);
    else return o->ls->sum + query(o->rs, mid, r, k - o->ls->s);
}

int main() {
    init();
    m = ReadInt(), n = ReadInt();
    for (int i = 0; i < m; ++i)
        S[i] = ReadInt() - 1, E[i] = ReadInt(), P[i] = ReadInt(); //[S, E)
    compress(); //离散
    vector<state> events;
    for (int i = 0; i < m; ++i)
        events.push_back(state(S[i], P[i], 1)), events.push_back(state(E[i], P[i], -1)); //时间结束的时候，需要减!
    sort(events.begin(), events.end());
    for (int i = 0, j = 0; i < n; ++i) {
        SegNode *now = null;
        if (i) now = root[i - 1];
        while (j < events.size() && events[j].t == i) {
            now = modify(now, 0, ps.size(), events[j].p, events[j].op);
            ++j;
        }
        root[i] = now;
    }
    ll pre = 1, k;
    while (n--) {
        int x = ReadInt() - 1, a = ReadInt(), b = ReadInt(), c = ReadInt();
        k = 1 + (a * pre + b) % c;
        printf("%lld\n", pre = query(root[x], 0, ps.size(), k));
    }
    return 0;
}
主席树