【10.11 D组 T4】cat 题解
题意
给定长为 \(n\) 的序列 \(a_i,c_i\) 和长为 \(m\) 的序列 \(b_j,d_j\)。
对于每个 \(i\in[1,n]\)，求
\[\mathop{\operatorname{max}}\limits_{j=1}^{m} [b_j\ge c_i \wedge a_i\ge d_j] \times b_j
\]
若没有符合 \(b_j\ge c_i \operatorname{and} a_i\ge d_j\) 的 \(j\in[1,m]\)，输出 \(-1\)。
题解
将每一个询问看作：
- 给定 \(a\) 和 \(c\)，求
\[\mathop{\operatorname{max}}\limits_{j=1}^{m} [d_j\le a] \times b_j
\]
- 若答案小于 \(c\)，输出 \(-1\)。
为了满足 \(a\ge d_j\)，可以考虑对 \(d_i\) 维护权值树状数组，再将问题转化为前缀 \(\operatorname{max}\)。
由于值域很大，离散化即可，注意离散化后值域是 \(4N\)。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8e5 + 10;
int n, m, range;
int a[N], b[N], c[N], d[N];
int rep[N];
int tmp[N << 2];
struct BIT {
int t[N << 2];
void update(int x, int val) {
for(; x <= range; x += x & -x) {
t[x] = max(t[x], val);
}
}
int query(int x) {
int res = 0;
for(; x; x -= x & -x) {
res = max(res, t[x]);
}
return res;
}
} T;
int main() {
freopen("cat.in", "r", stdin);
freopen("cat.out", "w", stdout);
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
tmp[++cnt] = a[i];
}
for(int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
tmp[++cnt] = c[i];
}
for(int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
tmp[++cnt] = b[i];
}
for(int i = 1; i <= m; i++) {
scanf("%d", &d[i]);
tmp[++cnt] = d[i];
}
sort(tmp + 1, tmp + cnt + 1);
range = unique(tmp + 1, tmp + cnt + 1) - tmp - 1;
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(tmp + 1, tmp + range + 1, a[i]) - tmp;
c[i] = lower_bound(tmp + 1, tmp + range + 1, c[i]) - tmp;
}
for(int i = 1; i <= m; i++) {
int kkk = lower_bound(tmp + 1, tmp + range + 1, b[i]) - tmp;
rep[kkk] = b[i];
b[i] = kkk;
d[i] = lower_bound(tmp + 1, tmp + range + 1, d[i]) - tmp;
}
for(int i = 1; i <= m; i++) {
T.update(d[i], b[i]);
}
for(int i = 1; i <= n; i++) {
int flg = T.query(a[i]);
if(flg < c[i]) printf("%d ", -1);
else printf("%d ", rep[flg]);
}
return 0;
}