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

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 4509  Solved: 1497

[Submit][Status][Discuss]

## Description

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

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

## 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

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

## Source

```#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
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
for(int i = 1; i <= N; i++) {
}
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 Ki = 1 + (Ai * PRE + Bi) % Ci;
PRE = Query(root[realrt[Xi]], 1, num, Ki);
printf("%lld\n", PRE);
}
}```

1811 篇文章120 人订阅

0 条评论

## 相关文章

### MySQL数据库中的5种数据类型简介

MySQL数据库中的5种数据类型是：字符型，文本型，数值型，逻辑型与日期型，以下就是文章的详细内容介绍，希望在你今后的学习中会有所帮助。

862

3357

5973

2149

### ABB机器人编程方式

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

3536

1103

### Python之数据聚合与分组运算

Python之数据聚合与分组运算 1. 关系型数据库方便对数据进行连接、过滤、转换和聚合。 2. Hadley Wickham创建了用于表示分组运算术语“spl...

2559

3898

38910

2455