NC19776. 数组合并
描述
输入描述
第一行三个整数 N, M, K.
接下来 N 行描述 N 个数组，每行以一个整数 n 开始，表示这个数组的元素个数，后面接 n 个整数 a1, ..., an. 注意，这里 a1, ..., an 以大写16进制表示，每个数字长度不超过4。
接下来 M 行描述 M 个操作，满足下面两种形式之一：
* "U x y"（不含引号）。表示一次修改操作。x, y 以大写16进制的形式给出，长度不超过4.
* "Q x"（不含引号）。表示一次查询操作。x 以大写16进制的形式给出，长度不超过4.
输出描述
对于每个询问操作，输出合并后的数组从第 x 项开始的最多 K 个元素，以空格隔开，用大写16进制表示，注意不要有前导零。
示例1
输入:
2 5 3 2 4 2 3 6 A 1 Q 3 U 1 F Q 4 U F 1 Q 1
输出:
6 A 1 A F 4 2 6
C++14(g++5.4) 解法, 执行用时: 202ms, 内存消耗: 44512K, 提交时间: 2019-02-28 11:06:52
# include <bits/stdc++.h>
using namespace std;
int s[1<<20][8], mx[1<<20];
const int M = 1 << 19;
const int G = 1 << 20;
bool debug;
int K, Q, step;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define arr_sum(arr) accumulate(arr, arr + 8, 0)
int len[8];
int lim, key, cur[8];
void query() {
static int tmp[8];
rep(i, K) cur[i] = tmp[i] = len[i];
int l = 0, r = M, mid, u = 1;
key = 0;
while(r - l > 1) {
mid = (l + r) >> 1;
rep(i, K) tmp[i] = min(cur[i], s[u<<1|1][i]);
if(arr_sum(tmp) >= lim) {
u = u << 1, r = mid;
rep(i, K) cur[i] = tmp[i];
} else {
key = max(key, mx[u<<1]);
u = u << 1 | 1, l = mid;
}
}
key = max(key, mx[u]);
}
void update(int x,int i,int j) {
if(j == G) {
mx[M + x] = -1;
s[M + x][i] = len[i];
} else {
mx[M + x] = x;
s[M + x][i] = j;
}
for(int u = (M + x) >> 1; u; u = u >> 1) {
s[u][i] = min(s[u << 1][i], s[u << 1 | 1][i]);
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}
}
int vid[1<<19], vpo[1<<19], _val[1<<19], *val[8];
void simulate() {
int k = vid[key], p = vpo[key];
p += lim - 1 - (arr_sum(cur) - cur[k] + p);
printf("%X", val[k][p]);
cur[k] = p + 1;
for(int _ = 1; _ < step; ++_) {
k = -1;
rep(i, K) if(cur[i] < len[i] && (k == -1 || val[i][cur[i]] < val[k][cur[k]])) k = i;
if(k == -1) break;
printf(" %X", val[k][cur[k]]);
cur[k]++;
}
puts("");
}
int main() {
scanf("%d%d%d", &K, &Q, &step);
int *cur = _val;
rep(i, K) {
int cnt; scanf("%d", &cnt);
len[i] = cnt; val[i] = cur;
cur += cnt + (16 - cnt % 16);
rep(j, cnt) {
int x; scanf("%X", &x);
assert(x < (1<<19));
vid[x] = i;
vpo[x] = j;
val[i][j] = x;
}
}
// init for segment tree
rep(i, M) mx[i+M] = -1;
rep(i, M) rep(j, K) s[i+M][j] = len[j];
rep(i, K) rep(j, len[i]) {
int x = val[i][j];
mx[M + x] = x;
s[M + x][i] = j;
}
for(int i = M - 1; i; --i) {
mx[i] = max(mx[i<<1], mx[i<<1|1]);
rep(j, K) s[i][j] = min(s[i<<1][j], s[i<<1|1][j]);
}
// operations
int qid = 0;
while(Q--) {
char op[8];
scanf("%s", op);
if(op[0] == 'Q') {
scanf("%d", &lim);
qid += 1;
debug = (qid == 317);
query();
simulate();
} else {
int x, y; scanf("%X%X", &x, &y);
assert(x < (1<<19));
assert(y < (1<<19));
int i = vid[x], j = vpo[x];
update(x, i, G);
update(y, i, j);
vid[y] = i;
vpo[y] = j;
val[i][j] = y;
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 282ms, 内存消耗: 48608K, 提交时间: 2019-01-07 19:01:12
# include <bits/stdc++.h>
using namespace std;
int s[1<<20][8], mx[1<<20];
const int M = 1 << 19;
const int G = 1 << 20;
bool debug;
int K, Q, step;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define arr_sum(arr) accumulate(arr, arr + 8, 0)
int len[8];
int lim, key, cur[8];
void query() {
static int tmp[8];
rep(i, K) cur[i] = tmp[i] = len[i];
int l = 0, r = M, mid, u = 1;
key = 0;
while(r - l > 1) {
mid = (l + r) >> 1;
rep(i, K) tmp[i] = min(cur[i], s[u<<1|1][i]);
if(arr_sum(tmp) >= lim) {
u = u << 1, r = mid;
rep(i, K) cur[i] = tmp[i];
} else {
key = max(key, mx[u<<1]);
u = u << 1 | 1, l = mid;
}
}
key = max(key, mx[u]);
}
void update(int x,int i,int j) {
if(j == G) {
mx[M + x] = -1;
s[M + x][i] = len[i];
} else {
mx[M + x] = x;
s[M + x][i] = j;
}
for(int u = (M + x) >> 1; u; u = u >> 1) {
s[u][i] = min(s[u << 1][i], s[u << 1 | 1][i]);
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}
}
int vid[1<<19], vpo[1<<19], _val[1<<19], *val[8];
void simulate() {
int k = vid[key], p = vpo[key];
p += lim - 1 - (arr_sum(cur) - cur[k] + p);
printf("%X", val[k][p]);
cur[k] = p + 1;
for(int _ = 1; _ < step; ++_) {
k = -1;
rep(i, K) if(cur[i] < len[i] && (k == -1 || val[i][cur[i]] < val[k][cur[k]])) k = i;
if(k == -1) break;
printf(" %X", val[k][cur[k]]);
cur[k]++;
}
puts("");
}
int main() {
scanf("%d%d%d", &K, &Q, &step);
int *cur = _val;
rep(i, K) {
int cnt; scanf("%d", &cnt);
len[i] = cnt; val[i] = cur;
cur += cnt + (16 - cnt % 16);
rep(j, cnt) {
int x; scanf("%X", &x);
assert(x < (1<<19));
vid[x] = i;
vpo[x] = j;
val[i][j] = x;
}
}
// init for segment tree
rep(i, M) mx[i+M] = -1;
rep(i, M) rep(j, K) s[i+M][j] = len[j];
rep(i, K) rep(j, len[i]) {
int x = val[i][j];
mx[M + x] = x;
s[M + x][i] = j;
}
for(int i = M - 1; i; --i) {
mx[i] = max(mx[i<<1], mx[i<<1|1]);
rep(j, K) s[i][j] = min(s[i<<1][j], s[i<<1|1][j]);
}
// operations
int qid = 0;
while(Q--) {
char op[8];
scanf("%s", op);
if(op[0] == 'Q') {
scanf("%d", &lim);
qid += 1;
debug = (qid == 317);
query();
simulate();
} else {
int x, y; scanf("%X%X", &x, &y);
assert(x < (1<<19));
assert(y < (1<<19));
int i = vid[x], j = vpo[x];
update(x, i, G);
update(y, i, j);
vid[y] = i;
vpo[y] = j;
val[i][j] = y;
}
}
}