CSP-S 2022 策略游戏
Skyzhou666 · · 题解
考场上花了快一个小时敲了贪心，没想到真拿到了60，回过头来用线段树又敲了一个多小时。。。
考场代码（60PTS）
#include <iostream>
#include <cstdio>
#define MAXN 100001
#define INF 100000000000000000
using namespace std;
long long a[MAXN], b[MAXN]; //L max, Q min
long long findAns(long long l1, long long r1, long long l2, long long r2)
{
bool z1, f1, z2, f2;
z1 = f1 = z2 = f2 = false;
long long maxz1, minz1, maxz2, minz2, maxf1, minf1, maxf2, minf2;
minz1 = minz2 = minf1 = minf2 = INF;
maxz1 = maxz2 = maxf1 = maxf2 = -INF;
for(long long x = l1; x <= r1; x++)
{
if(a[x] <= 0)
{
f1 = true;
minf1 = min(minf1, a[x]);
maxf1 = max(maxf1, a[x]);
}
if(a[x] >= 0)
{
z1 = true;
minz1 = min(minz1, a[x]);
maxz1 = max(maxz1, a[x]);
}
}
for(long long x = l2; x <= r2; x++)
{
if(b[x] <= 0)
{
f2 = true;
minf2 = min(minf2, b[x]);
maxf2 = max(maxf2, b[x]);
}
if(b[x] >= 0)
{
z2 = true;
minz2 = min(minz2, b[x]);
maxz2 = max(maxz2, b[x]);
}
}
if(z1 && f1 && z2 && f2)
{
return max(minz1 * minf2, maxf1 * maxz2);
}
if(z1 && f1 && z2 && !f2) return maxz1 * minz2;
if(z1 && f1 && !z2 && f2) return minf1 * maxf2;
if(z1 && !f1 && z2 && f2) return minz1 * minf2;
if(z1 && !f1 && z2 && !f2) return maxz1 * minz2;
if(z1 && !f1 && !z2 && f2) return minz1 * minf2;
if(!z1 && f1 && z2 && f2) return maxf1 * maxz2;
if(!z1 && f1 && z2 && !f2) return maxf1 * maxz2;
if(!z1 && f1 && !z2 && f2) return minf1 * maxf2;
}
int main()
{
//freopen("game.in", "r", stdin);
//freopen("game.out", "w", stdout);
long long n, m, q;
cin >> n >> m >> q;
for(long long x = 1; x <= n; x++) cin >> a[x];
for(long long x = 1; x <= m; x++) cin >> b[x];
while(q--)
{
long long l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
cout << findAns(l1, r1, l2, r2) << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}线段树维护正解（AC）
极度优美300行线段树（
#include <iostream>
#include <cstdio>
#define MAXN 400001
#define INF 2147483647
using namespace std;
long long n, m, a[MAXN], b[MAXN]; //L max, Q min
long long taz[MAXN], taf[MAXN], tbz[MAXN], tbf[MAXN];
long long tazm[MAXN], tafm[MAXN], tbzm[MAXN], tbfm[MAXN];
void buildAzMax(long long l, long long r, long long k)
{
if(l == r)
{
if(a[l] >= 0) taz[k] = a[l];
else taz[k] = -INF;
}
else
{
long long mid = (l + r) >> 1;
buildAzMax(l, mid, k<<1);
buildAzMax(mid+1, r, k<<1|1);
taz[k] = max(taz[k<<1], taz[k<<1|1]);
}
}
long long queryAzMax(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return taz[k];
else
{
long long re = -INF, mid = (l + r) >> 1;
if(L <= mid) re = max(re, queryAzMax(L, R, l, mid, k<<1));
if(R > mid) re = max(re, queryAzMax(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildAzMin(long long l, long long r, long long k)
{
if(l == r)
{
if(a[l] >= 0) tazm[k] = a[l];
else tazm[k] = INF;
}
else
{
long long mid = (l + r) >> 1;
buildAzMin(l, mid, k<<1);
buildAzMin(mid+1, r, k<<1|1);
tazm[k] = min(tazm[k<<1], tazm[k<<1|1]);
}
}
long long queryAzMin(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tazm[k];
else
{
long long re = INF, mid = (l + r) >> 1;
if(L <= mid) re = min(re, queryAzMin(L, R, l, mid, k<<1));
if(R > mid) re = min(re, queryAzMin(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildAfMax(long long l, long long r, long long k)
{
if(l == r)
{
if(a[l] <= 0) taf[k] = a[l];
else taf[k] = -INF;
}
else
{
long long mid = (l + r) >> 1;
buildAfMax(l, mid, k<<1);
buildAfMax(mid+1, r, k<<1|1);
taf[k] = max(taf[k<<1], taf[k<<1|1]);
}
}
long long queryAfMax(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return taf[k];
else
{
long long re = -INF, mid = (l + r) >> 1;
if(L <= mid) re = max(re, queryAfMax(L, R, l, mid, k<<1));
if(R > mid) re = max(re, queryAfMax(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildAfMin(long long l, long long r, long long k)
{
if(l == r)
{
if(a[l] <= 0) tafm[k] = a[l];
else tafm[k] = INF;
}
else
{
long long mid = (l + r) >> 1;
buildAfMin(l, mid, k<<1);
buildAfMin(mid+1, r, k<<1|1);
tafm[k] = min(tafm[k<<1], tafm[k<<1|1]);
}
}
long long queryAfMin(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tafm[k];
else
{
long long re = INF, mid = (l + r) >> 1;
if(L <= mid) re = min(re, queryAfMin(L, R, l, mid, k<<1));
if(R > mid) re = min(re, queryAfMin(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildBzMax(long long l, long long r, long long k)
{
if(l == r)
{
if(b[l] >= 0) tbz[k] = b[l];
else tbz[k] = -INF;
}
else
{
long long mid = (l + r) >> 1;
buildBzMax(l, mid, k<<1);
buildBzMax(mid+1, r, k<<1|1);
tbz[k] = max(tbz[k<<1], tbz[k<<1|1]);
}
}
long long queryBzMax(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tbz[k];
else
{
long long re = -INF, mid = (l + r) >> 1;
if(L <= mid) re = max(re, queryBzMax(L, R, l, mid, k<<1));
if(R > mid) re = max(re, queryBzMax(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildBzMin(long long l, long long r, long long k)
{
if(l == r)
{
if(b[l] >= 0) tbzm[k] = b[l];
else tbzm[k] = INF;
}
else
{
long long mid = (l + r) >> 1;
buildBzMin(l, mid, k<<1);
buildBzMin(mid+1, r, k<<1|1);
tbzm[k] = min(tbzm[k<<1], tbzm[k<<1|1]);
}
}
long long queryBzMin(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tbzm[k];
else
{
long long re = INF, mid = (l + r) >> 1;
if(L <= mid) re = min(re, queryBzMin(L, R, l, mid, k<<1));
if(R > mid) re = min(re, queryBzMin(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildBfMax(long long l, long long r, long long k)
{
if(l == r)
{
if(b[l] <= 0) tbf[k] = b[l];
else tbf[k] = -INF;
}
else
{
long long mid = (l + r) >> 1;
buildBfMax(l, mid, k<<1);
buildBfMax(mid+1, r, k<<1|1);
tbf[k] = max(tbf[k<<1], tbf[k<<1|1]);
}
}
long long queryBfMax(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tbf[k];
else
{
long long re = -INF, mid = (l + r) >> 1;
if(L <= mid) re = max(re, queryBfMax(L, R, l, mid, k<<1));
if(R > mid) re = max(re, queryBfMax(L, R, mid+1, r, k<<1|1));
return re;
}
}
void buildBfMin(long long l, long long r, long long k)
{
if(l == r)
{
if(b[l] <= 0) tbfm[k] = b[l];
else tbfm[k] = INF;
}
else
{
long long mid = (l + r) >> 1;
buildBfMin(l, mid, k<<1);
buildBfMin(mid+1, r, k<<1|1);
tbfm[k] = min(tbfm[k<<1], tbfm[k<<1|1]);
}
}
long long queryBfMin(long long L, long long R, long long l, long long r, long long k)
{
if(L <= l && r <= R) return tbfm[k];
else
{
long long re = INF, mid = (l + r) >> 1;
if(L <= mid) re = min(re, queryBfMin(L, R, l, mid, k<<1));
if(R > mid) re = min(re, queryBfMin(L, R, mid+1, r, k<<1|1));
return re;
}
}
long long findAns(long long l1, long long r1, long long l2, long long r2)
{
bool z1, f1, z2, f2;
z1 = f1 = z2 = f2 = false;
long long maxz1, minz1, maxz2, minz2, maxf1, minf1, maxf2, minf2;
minz1 = minz2 = minf1 = minf2 = INF;
maxz1 = maxz2 = maxf1 = maxf2 = -INF;
maxz1 = queryAzMax(l1, r1, 1, n, 1);
//cout << "maxz1: " << maxz1 << endl;
if(maxz1 != -INF) z1 = true;
minz1 = queryAzMin(l1, r1, 1, n, 1);
//cout << "minz1: " << minz1 << endl;
maxf1 = queryAfMax(l1, r1, 1, n, 1);
//cout << "maxf1: " << maxf1 << endl;
if(maxf1 != -INF) f1 = true;
minf1 = queryAfMin(l1, r1, 1, n, 1);
//cout << "minf1: " << minf1 << endl;
maxz2 = queryBzMax(l2, r2, 1, m, 1);
//cout << "maxz1: " << maxz1 << endl;
if(maxz2 != -INF) z2 = true;
minz2 = queryBzMin(l2, r2, 1, m, 1);
//cout << "minz1: " << minz1 << endl;
maxf2 = queryBfMax(l2, r2, 1, m, 1);
//cout << "maxf1: " << maxf1 << endl;
if(maxf2 != -INF) f2 = true;
minf2 = queryBfMin(l2, r2, 1, m, 1);
//cout << "minf1: " << minf1 << endl;
if(z1 && f1 && z2 && f2)
{
return max(minz1 * minf2, maxf1 * maxz2);
}
if(z1 && f1 && z2 && !f2) return maxz1 * minz2;
if(z1 && f1 && !z2 && f2) return minf1 * maxf2;
if(z1 && !f1 && z2 && f2) return minz1 * minf2;
if(z1 && !f1 && z2 && !f2) return maxz1 * minz2;
if(z1 && !f1 && !z2 && f2) return minz1 * minf2;
if(!z1 && f1 && z2 && f2) return maxf1 * maxz2;
if(!z1 && f1 && z2 && !f2) return maxf1 * maxz2;
if(!z1 && f1 && !z2 && f2) return minf1 * maxf2;
}
int main()
{
long long q;
cin >> n >> m >> q;
for(long long x = 1; x <= n; x++) cin >> a[x];
buildAzMax(1, n, 1);
buildAfMax(1, n, 1);
buildAzMin(1, n, 1);
buildAfMin(1, n, 1);
for(long long x = 1; x <= m; x++) cin >> b[x];
buildBzMax(1, m, 1);
buildBfMax(1, m, 1);
buildBzMin(1, m, 1);
buildBfMin(1, m, 1);
while(q--)
{
long long l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
cout << findAns(l1, r1, l2, r2) << endl;
}
return 0;
}