avatar

soj924

http://120.27.222.204:12243/problem/924

可恶,又赛后过题。


以下全部规定ai,li+1=a_{i,l_i+1}=\infin


先来讲一个easy的O(nqlog2(l+q))O(nqlog^2{(l+q)})的做法(其实也想了不少时间吧)。

1.1.二分最大的xx,找到ai,j=xa_{i,j}=x

2.2.y=mink=1jai,ky=\min\limits_{k=1}^ja_{i,k}

3.3.ze,eiz_e,e \not= i表示第ee个数组比yy大的最小位置,并令zi=0z_i=0

4.4.判断i+e=1n(ze1)i+\sum\limits_{e=1}^n{(z_e - 1)}是否小于等于kk

其中外层需要二分,并且对于每个xx都要在线段树上二分求zxz_x,所以总复杂度为O(nqlog2(l+q))O(nqlog^2(l+q))


现在我们希望能直接找到yy,也就是希望最初二分的数组是个单调递增的,是该数组前缀最大值形成的,可惜我不会维护单调递增序列。

不过事物的发展是前进性和曲折性的统一,我们有了个别的想法:直接线段树二分!


考虑转化上述easy的步骤,使得其更适合直接线段树二分。

1.1.二分最大的xx,找到ai,j=xa_{i,j}=x

2.2.zez_e表示第ee个数组大于等于xx的最小位置;

3.3.判断e=1n(ze1)+1\sum\limits_{e=1}^n(z_e-1)+1是否小于等于kk

我们不再设yy,也不再令zi=0z_i=0。我们会惊奇的发现,这时二分出来的xx一定是ii数组的某个前缀最大值,因为如果不是,xx一定能二分到那个前缀最大值。那么,我们相当于找到了easy步骤中的yy

反推正确答案,答案就是ai,j+k(e=1n(ze1)+1)a_{i,j+k-(\sum\limits_{e=1}^n(z_e-1)+1)}。(这个下标虽然看起来有点繁琐,但是自己写还是很显然的)。


但是上述方法还是要nn次线段树二分。我们可以只维护一棵权值线段树,这棵线段树的每个节点维护一个长度为nn的数组,表示权值在[L,R)[L,R)区间内的在每一个数组内的最小位置。只要找到一个最右的点,满足上述条件即可,具体可以看代码。

复杂度O(nqlog(l+q))O(nqlog{(l+q)})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
int x = 0, p = 1; char c = getchar();
while (c <= 32) c = getchar();
if (c == 45) p = -p, c = getchar();
while (c > 32) x = x * 10 + c - 48, c = getchar();
return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 7e5 + 5;
const int M = 5e5 + 5;
const int Q = 2e5 + 5;
int dat[N << 2][10], n, len[N], q, a[10][M];
pii pos[N];
int qx[Q], qy[Q], qz[Q], op[Q], tmp[10];
vector<int> id;
//
void up(int k) {
rep(i, n) {
dat[k][i] = min(dat[2 * k + 1][i], dat[2 * k + 2][i]);
}
}
void build(int l, int r, int k) {
if (r - l == 1) {
rep(i, n) dat[k][i] = len[i];
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2 * k + 1);
build(mid, r, 2 * k + 2);
up(k);
}
void modify(int l, int r, int p, int k, int x, int v) {
if (r - l == 1) {
dat[k][x] = v;
return;
}
int mid = (l + r) >> 1;
if (p < mid) modify(l, mid, p, 2 * k + 1, x, v);
else modify(mid, r, p, 2 * k + 2, x, v);
dat[k][x] = min(dat[2 * k + 1][x], dat[2 * k + 2][x]);
}
int qry(int l, int r, int k, int p) {
if (r - l == 1) {
rep(i, n) tmp[i] = min(tmp[i], dat[k][i]);
return l;
}
int mid = (l + r) >> 1, sum = 0;
rep(i, n) sum += min(tmp[i], dat[2 * k + 2][i]);
if (sum > p) {
rep(i, n) tmp[i] = min(tmp[i], dat[2 * k + 2][i]);
return qry(l, mid, 2 * k + 1, p);
}
else return qry(mid, r, 2 * k + 2, p);
}
int main() {
n = getint(); q = getint();
rep(i, n) {
len[i] = getint();
rep(j, len[i]) {
a[i][j] = getint();
id.emplace_back(a[i][j]);
}
}
rep(i, q) {
op[i] = getint(); qx[i] = getint() - 1;
if (op[i] == 1) {
qy[i] = getint() - 1; qz[i] = getint();
id.emplace_back(qz[i]);
}
}
sort(id.begin(), id.end());
id.resize(unique(id.begin(), id.end()) - id.begin());
rep(i, q) if (op[i] == 1) {
qz[i] = lower_bound(id.begin(), id.end(), qz[i]) - id.begin();
}
int m = id.size();
build(0, m, 0);
rep(i, m) pos[i] = mp(-1, -1);
rep(i, n) rep(j, len[i]) {
a[i][j] = lower_bound(id.begin(), id.end(), a[i][j]) - id.begin();
assert(pos[a[i][j]] == mp(-1, -1));
pos[a[i][j]] = mp(i, j);
modify(0, m, a[i][j], 0, i, j);
}
rep(i, q) {
if (op[i] == 1) {
modify(0, m, a[qx[i]][qy[i]], 0, qx[i], len[qx[i]]);
pos[a[qx[i]][qy[i]]] = mp(-1, -1);
assert(pos[qz[i]] == mp(-1, -1));
a[qx[i]][qy[i]] = qz[i]; pos[qz[i]] = mp(qx[i], qy[i]);
modify(0, m, a[qx[i]][qy[i]], 0, qx[i], qy[i]);
}
else {
rep(i, n) tmp[i] = len[i]; int k = qx[i], sum = 0, h;
pii res = pos[h = qry(0, m, 0, k)];
rep(i, n) sum += tmp[i];
assert(sum <= k);
printf("%d\n", id[a[res.first][k - sum + res.second]]);
}
}
return 0;
}
文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/04/15/soj924/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog

评论