BZOJ 3932: [CQOI2015]任务查询系统(主席树)

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 4509  Solved: 1497

[Submit][Status][Discuss]

Description

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的

任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行

),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向

查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个

)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先

级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

Input

输入文件第一行包含两个空格分开的正整数m和n,分别表示任务总数和时间范围。接下来m行,每行包含三个空格

分开的正整数Si、Ei和Pi(Si≤Ei),描述一个任务。接下来n行,每行包含四个空格分开的整数Xi、Ai、Bi和Ci,

描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果,

对于第一次查询,Pre=1。

Output

输出共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

HINT

样例解释

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的一个排列

Source

很水但是很恶心

首先不难想到对两个端点进行差分

然后把主席树建出来就可以了

注意要开ll

另外,叶子节点的总权值可能大于查询的个数,需要特判

#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1; 
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, PRE = 1;
struct node {
    int ls, rs, sum, siz;
}T[MAXN * 6];
int root[MAXN], tot = 0, realrt[MAXN];
int S[MAXN], E[MAXN], tmp[MAXN], P[MAXN];
vector<int>v[MAXN];
#define rs(x) T[x].rs
#define ls(x) T[x].ls
int insert(int &now, int pre, int l, int r, int pos, int val) {
    now = ++tot;
    T[now] = T[pre]; T[now].sum += val;
    val > 0 ? T[now].siz++ : T[now].siz--;
    if(l == r) return now;
    int mid = l + r >> 1;
    if(pos <= mid) ls(now) = insert(ls(now), ls(pre), l, mid, pos, val);
    else            rs(now) = insert(rs(now), rs(pre), mid + 1, r, pos, val);
    return now;
}
int Query(int now, int l, int r, int val) {
    if(l == r)  return min(val * tmp[l], T[now].sum);
    int mid = l + r >> 1;
    if(val <= T[ls(now)].siz) return Query(ls(now), l, mid, val);
    else return Query(rs(now), mid + 1, r, val - T[ls(now)].siz) + T[ls(now)].sum;
}
main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif
    N = read(); M = read();
    for(int i = 1; i <= N; i++) {
        S[i] = read(), E[i] = read(), tmp[i] = P[i] = read();
    }
    sort(tmp + 1, tmp + N + 1);
    int num = unique(tmp + 1, tmp + N + 1) - tmp - 1;
    for(int i = 1; i <= N; i++) {
        P[i] = lower_bound(tmp + 1, tmp + num + 1, P[i]) - tmp;
        v[S[i]].push_back(P[i]); v[E[i] + 1].push_back(-P[i]);
    }
    int cur = 0;
    for(int i = 1; i <= 100000; i++) {
        for(int j = 0; j < v[i].size(); j++) 
            cur++, insert(root[cur], root[cur - 1], 1, num, abs(v[i][j]), v[i][j] < 0 ? -tmp[-v[i][j]] : tmp[v[i][j]]);
        realrt[i] = cur;
    }
    for(int i = 1; i <= M; i++) {
        int Xi = read(), Ai = read(), Bi = read(), Ci = read();
        int Ki = 1 + (Ai * PRE + Bi) % Ci;
        PRE = Query(root[realrt[Xi]], 1, num, Ki);
        printf("%lld\n", PRE);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏YG小书屋

ES中文分词器之精确短语匹配(自定义分词器)

6302
来自专栏顶级程序员

MySQL 全文索引应用简明教程

本文从以下几个方面介绍下MySQL全文索引的基础知识: MySQL全文索引的几个注意事项 全文索引的语法 几种搜索类型的简介 几种搜索类型的实例 全文索引的几个...

38310
来自专栏Python

Django——model基础

ORM 映射关系:     表名 <-------> 类名 字段 <-------> 属性     表记录 <------->类实例对象...

18110
来自专栏个人分享

Hive metastore源码阅读(三)

  上次写了hive metastore的partition的生命周期,但是简略概括了下alter_partition的操作,这里补一下alter_partit...

1952
来自专栏数据结构与算法

RMQ算法

一.概述 RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,...

2907
来自专栏灯塔大数据

每周学点大数据 | No.41 join 操作

No.41期 join 操作 Mr. 王:第一个话题就是 join 操作。 join 操作在数据库中还是非常常见的。 小可:这个 join 指的是笛卡儿积操...

3817
来自专栏木宛城主

SharePoint CAML In Action——Part I

在SharePoint中,我们经常要对List进行操作,比如要从List中取出相应的ListItem,利用CAML是个好办法。在没了解CAML之前,我是这样取...

2415
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——9,数字深入体验

先给大家介绍一个函数:range(),这个函数是用来干嘛的呢?很简单,数数的,怎么数呢,我先给大家演示一下: for num in range(1,5): ...

3828
来自专栏机器人网

ABB机器人编程方式

1、指令表IL   指令表(IL)由一系列指令组成。每条指令都由一个新行开始,包含一个操作符以及和操作符类型相关的一个或多个操作数,并用逗号分开。在指令前可以有...

3266
来自专栏SeanCheney的专栏

《Pandas Cookbook》第08章 数据清理1. 用stack清理变量值作为列名2. 用melt清理变量值作为列名3. 同时stack多组变量4. 反转stacked数据5. 分组聚合后uns

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

1442

扫码关注云+社区