\(100+60+60+40=260\)，这种信心赛没 AK 我真的要退役了
喜欢写线段树和 ST 表的小朋友们你们好呀，我是前后缀 \(\min/\max\) 奥特曼
对于 \(n\) 个长方体的交，显然就是最靠右的左面、最靠左的右面、最靠上的下面……组成的长方体
枚举一个不存在的长方体
接下来考虑容斥，对于被且仅被 \(n-1\) 个长方体包含的点，一定为被这 \(n-1\) 个长方体包含的所有点，减去被所有 \(n\) 个长方体包含的点，证明显然
不要问为什么有结构体，因为最开始也写了线段树
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 1e5 + 5;
struct P {
LL x, y, z;
} a[kMaxN][2];
int n;
LL ans, u, d, f, b, l, r, cnt, cur;
struct PreSuf {
LL pu[kMaxN], pd[kMaxN], pf[kMaxN], pb[kMaxN], pl[kMaxN], pr[kMaxN], su[kMaxN], sd[kMaxN], sf[kMaxN], sb[kMaxN], sl[kMaxN], sr[kMaxN];
void Init(int n) { pu[0] = su[n + 1] = pb[0] = sb[n + 1] = pr[0] = sr[n + 1] = 1e18, pd[0] = sd[n + 1] = pf[0] = sf[n + 1] = pl[0] = sl[n + 1] = -1e18; }
void build(int n) {
for (int i = 1; i <= n; i++) {
pu[i] = min(pu[i - 1], a[i][1].z);
pb[i] = min(pb[i - 1], a[i][1].y);
pr[i] = min(pr[i - 1], a[i][1].x);
pd[i] = max(pd[i - 1], a[i][0].z);
pf[i] = max(pf[i - 1], a[i][0].y);
pl[i] = max(pl[i - 1], a[i][0].x);
}
for (int i = n; i; i--) {
su[i] = min(su[i + 1], a[i][1].z);
sb[i] = min(sb[i + 1], a[i][1].y);
sr[i] = min(sr[i + 1], a[i][1].x);
sd[i] = max(sd[i + 1], a[i][0].z);
sf[i] = max(sf[i + 1], a[i][0].y);
sl[i] = max(sl[i + 1], a[i][0].x);
}
}
LL queryu(int ql, int qr) {
if (ql > qr) {
return 1e18;
}
return ql == 1 ? pu[qr] : su[ql];
}
LL queryd(int ql, int qr) {
if (ql > qr) {
return -1e18;
}
return ql == 1 ? pd[qr] : sd[ql];
}
LL queryb(int ql, int qr) {
if (ql > qr) {
return 1e18;
}
return ql == 1 ? pb[qr] : sb[ql];
}
LL queryf(int ql, int qr) {
if (ql > qr) {
return -1e18;
}
return ql == 1 ? pf[qr] : sf[ql];
}
LL queryr(int ql, int qr) {
if (ql > qr) {
return 1e18;
}
return ql == 1 ? pr[qr] : sr[ql];
}
LL queryl(int ql, int qr) {
if (ql > qr) {
return -1e18;
}
return ql == 1 ? pl[qr] : sl[ql];
}
} tr;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
freopen("cube.in", "r", stdin), freopen("cube.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i][0].x >> a[i][0].y >> a[i][0].z >> a[i][1].x >> a[i][1].y >> a[i][1].z;
}
tr.Init(n), tr.build(n), u = tr.queryu(1, n), d = tr.queryd(1, n), f = tr.queryf(1, n), b = tr.queryb(1, n), l = tr.queryl(1, n), r = tr.queryr(1, n);
ans = cnt = max(u - d + 1, 0ll) * max(r - l + 1, 0ll) * max(b - f + 1, 0ll);
for (int i = 1; i <= n; i++) {
u = min(tr.queryu(1, i - 1), tr.queryu(i + 1, n));
d = max(tr.queryd(1, i - 1), tr.queryd(i + 1, n));
b = min(tr.queryb(1, i - 1), tr.queryb(i + 1, n));
f = max(tr.queryf(1, i - 1), tr.queryf(i + 1, n));
r = min(tr.queryr(1, i - 1), tr.queryr(i + 1, n));
l = max(tr.queryl(1, i - 1), tr.queryl(i + 1, n));
cur = max(u - d + 1, 0ll) * max(r - l + 1, 0ll) * max(b - f + 1, 0ll);
ans += cur - cnt;
}
cout << ans << '\n';
return 0;
}
这种见过的题没有一眼秒，我这是怎么了
考虑 No 的情况为：排序后，任意相邻两项的和都小于后面一项，于是可以想到斐波那契数列
一个不合法数列的极限即为 \(1,1,2,3,5,8,\dots\)，在 \(a_i\le 10^{18}\) 时，其长度大约为 \(100\)，于是可以在 \(r-l+1\ge 100\) 时可以直接输出 Yes，否则直接排序暴力判断
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 1e5 + 5;
int n, m, l, r;
bool ans;
LL a[kMaxN], f[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
freopen("triangle.in", "r", stdin), freopen("triangle.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (; m; m--, ans = 0) {
cin >> l >> r;
if (r - l + 1 >= 100) {
cout << "Yes\n";
continue;
}
for (int i = 1; i <= r - l + 1; i++) {
f[i] = a[i + l - 1];
}
sort(f + 1, f + r - l + 2);
for (int i = 1; i < r - l; i++) {
if (f[i] + f[i + 1] > f[i + 2]) {
ans = 1;
break;
}
}
cout << (ans ? "Yes" : "No") << '\n';
}
return 0;
}
发现 \(l\) 单调不减，可以理解为一个长度为 \(m\) 的窗口向右滑，于是可以开一个反转标记，在左右有数弹入弹出式根据反转标记更新即可
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e6 + 5;
int n, m, qtot, a[kMaxN], op, l, ans, cur = 1, q[kMaxN << 1], hd = 1e6 + 2;
bool f;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
freopen("section.in", "r", stdin), freopen("section.out", "w", stdout);
cin >> n >> m >> qtot;
for (int i = 1; i <= n; i++) {
cin >> a[i], i <= m && (q[hd + i - 1] = a[i]);
}
for (; qtot; qtot--) {
cin >> op >> l;
if (op == 2) {
if (l < cur || l >= cur + m) {
ans ^= a[l];
} else {
if (f) {
ans ^= q[hd + m - 1 - l + cur];
} else {
ans ^= q[hd + l - cur];
}
}
} else {
for (; cur < l; cur++) {
f ? (--hd, a[cur] = q[hd + m], q[hd] = a[cur + m]) : (a[cur] = q[hd], q[hd + m] = a[cur + m], hd++);
}
f ^= 1;
}
}
cout << ans << '\n';
return 0;
}
看到 \(n \le 1000\)，一眼暴力建图跑最大生成树，但是边权需要注意，将两点的边权设置成点权之和，然后将答案初始值设为所有点权和的相反数，这样在连边时，父亲的点权会算上，自己的负点权会被抵消
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 1e3 + 5;
int n, a[kMaxN], d[kMaxN], cnt;
bitset<kMaxN> vis;
LL ans;
int main() {
freopen("graph.in", "r", stdin), freopen("graph.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i], ans -= a[i], d[i] = a[i];
}
for (int i = 1; i <= n; i++, cnt = 0) {
for (int j = 1; j <= n; j++) {
!vis[j] && (!cnt || d[j] > d[cnt]) && (cnt = j);
}
vis[cnt] = 1, ans += d[cnt];
for (int j = 1; j <= n; j++) {
!vis[j] && ((a[cnt] & a[j]) == 0) && (d[j] = max(d[j], a[cnt] + a[j]));
}
}
cout << ans << '\n';
return 0;
}