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 3Sample Output
2
8
11Sample Explanation
K1=(1*1+3)% 2+1=1
K2=(1*2+3)% 4+1=2
K3=(2*8+4)% 3+1=3
Data Range
对于 100% 的数据, 1≤m, n, Si, Ei, Ci≤100000, 0≤Ai, Bi≤100000, 1≤Pi≤10000000, Xi 为 1 到 n 的一个排列
Solution
一道裸的可持久化线段树, 直接树状数组套一棵线段树 (内存 \(O(n \cdot log(n))\), 不用问了).
但是套树状数组需要多一个 log......
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 100005, maxm = 20000005;
#define lowest_digit(__x) ((__x)&(-__x))
int n, m;
class RetroactiveSegmentTree
{
public:
int cnt, mx;
// Vector-like random access container
int vec[maxn], top;
// Tree structure operations
int root[maxn], size[maxm], ch[maxm][2], value[maxn];
lli sum[maxm];
int insert(int x, int val, int combo)
{
// Creating new node at #x.
if (!x) x = ++cnt;
size[x] += combo;
sum[x] += combo * value[val];
int tmp = x;
// Creating subtrees
int l = 1, r = 2 * m;
while (l != r) {
int mid = (l + r) / 2, t = 0;
if (val > mid) t ^= 1, l = mid + 1;
else r = mid;
if (!ch[x][t]) ch[x][t] = ++cnt;
x = ch[x][t]; size[x] += combo;
sum[x] += combo * value[val];
}
return tmp;
}
void update(int l, int r, int pos)
{
for (int i = l; i <= n; i += lowest_digit(i))
root[i] = insert(root[i], pos, 1);
for (int i = r + 1; i <= n; i += lowest_digit(i))
root[i] = insert(root[i], pos, -1);
return ;
}
lli query(int x, int K)
{
lli res = 0, nd_cnt = 0; // Result and node count
top = 0;
for (int i = x; i != 0; i -= lowest_digit(i)) {
vec[++top] = root[i];
nd_cnt += size[root[i]];
res += sum[root[i]];
}
// That's a preliminary check if K....
if (K > nd_cnt)
return res;
else res = 0;
// Iterating through all possible / affected sub-segment-trees
int l = 1, r = 2 * m;
while (l != r) {
int mid = (l + r) / 2, t, tmp = 0;
// Actual children in possession
for (int i = 1; i <= top; i++)
tmp += size[ch[vec[i]][0]];
// Determine whether to traverse to left / right child
if (tmp < K) {
for (int i = 1; i <= top; i++)
res += sum[ch[vec[i]][0]];
t = 1;
K -= tmp; l = mid + 1;
} else {
t = 0;
r = mid;
}
// Batch manipulating children pointer locations
for (int i = 1; i <= top; i++)
vec[i] = ch[vec[i]][t];
}
res += 1 * K * value[l];
return res;
}
} st;
lli S[maxn], E[maxn], P[maxn];
int main(int argc, char** argv)
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &S[i], &E[i], &P[i]);
st.value[i] = P[i];
}
sort(st.value + 1, st.value + m + 1);
// Preprocessing data.
for (int i = 1; i <= m; i++) {
// Get the position of p...
P[i] = lower_bound(st.value + 1, st.value + m + 1, P[i]) - st.value;
st.update(S[i], E[i], P[i]);
}
lli pre = 1, X, A, B, C, K;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld%lld%lld", &X, &A, &B, &C);
K = 1 + (A * pre + B) % C;
pre = st.query(X, K);
printf("%lld\n", pre);
}
return 0;
}