P5816 [CQOI2010]内部白点
// 结论: 最多进行一次变色过程
// 推论: 不会输出 -1 证明: 反证
// 本题做法: 扫描线
// 只计算 横坐标相同, 纵坐标相邻
// 与 纵坐标相同, 横坐标相邻
// 的贡献
// 横坐标相同, 纵坐标相邻的: ++[y]
// 纵坐标相同, 横坐标响铃的: res += y[x1,x2]
// 证明: 之后被操作的十字架一定在最初的点之间
// 使用树状数组维护:将操作处理出来,按(y,z)排序（其中z表示操作),逐个操作
点击查看代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 1e5 + 5;
struct Data {
int x1, x2, y, z; // z=0表示询问, z=+-1表示操作(可以保证顺序)
bool operator < (const Data &a) const {
return y < a.y || (y == a.y && z < a.z);
}
} a[N * 3];
struct Pt { int x, y; } p[N];
int n, tota, totn, num[N]; // num为x离散化的结果
int find(int x) {
return std::lower_bound(num, num + totn, x) - num;
}
int tr[N];
void add(int x, int y) {
for(++ x; x <= totn; x += x & -x) tr[x] += y;
}
int query(int x) {
int res = 0;
for(++ x; x; x -= x & -x) res += tr[x];
return res;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d%d", &p[i].x, &p[i].y), num[i] = p[i].x;
std::sort(num, num + n), totn = std::unique(num, num + n) - num;
std::sort(p, p + n, [](const Pt &x, const Pt &y) { return x.y < y.y || (x.y == y.y && x.x < y.x); });
for(int i = 1; i < n; i ++)
if(p[i].y == p[i-1].y) a[tota ++] = {find(p[i-1].x), find(p[i].x), p[i].y, 0};
std::sort(p, p + n, [](const Pt &x, const Pt &y) { return x.x < y.x || (x.x == y.x && x.y < y.y); });
for(int i = 1; i < n; i ++)
if(p[i].x == p[i-1].x)
a[tota ++] = {find(p[i].x), 0, p[i-1].y, 1}, a[tota ++] = {find(p[i].x), 0, p[i].y, -1};
std::sort(a, a + tota);
int res = n;
for(int i = 0; i < tota; i ++) {
if(a[i].z) add(a[i].x1, a[i].z);
else res += query(a[i].x2 - 1) - query(a[i].x1); // 不算端点
}
printf("%d\n", res);
return 0;
}
P2154 [SDOI2009] 虔诚的墓主人
// 类似“内部白点”
// 竖着扫描线
// 树状数组维护C(左边,k)C(右边,k)
// C(上边,k)C(下边,k)可直接计算
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <array>
#include <queue>
using namespace std;
const int N = 100005;
int n, k;
struct point_t { int x, y; } points[N];
inline bool cmp(const point_t &a, const point_t &b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }
int tr[N], lisanhua[N * 2], tot;
int c[N][15]; // 组合数
int col[N]; // 有多少个点在 i 列上(x=i)
int line[N]; // 有多少个点在 i 行上(y=i)
int now[N]; // 现在有多少个在 i 行上
// 计算组合数
void init() {
c[0][0] = 1;
for(int i = 1; i <= n; i ++) {
c[i][0] = 1;
for(int j = 1; j <= min(k, i); j ++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
}
#define C(a, b) (c[a][b])
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int y) {
for(; x <= tot; x += lowbit(x)) tr[x] += y;
}
inline int query(int x) {
int res = 0;
for(; x; x -= lowbit(x)) res += tr[x];
return res;
}
inline int find(int x) {
return lower_bound(lisanhua + 1, lisanhua + tot + 1, x) - lisanhua;
}
int main() {
scanf("%*d%*d%d", &n);
for(int i = 0; i < n; i ++) scanf("%d%d", &points[i].x, &points[i].y);
scanf("%d", &k), init();
for(int i = 0; i < n; i ++) lisanhua[++ tot] = points[i].x, lisanhua[++ tot] = points[i].y;
sort(lisanhua + 1, lisanhua + tot + 1); // x 和 y 一起离散化
tot = unique(lisanhua + 1, lisanhua + tot + 1) - lisanhua - 1;
sort(points, points + n, cmp);
for(int i = 0; i < n; i ++) {
col[find(points[i].x)] ++;
line[find(points[i].y)] ++;
}
int l; // 左边有多少个
int res = 0;
for(int i = 0; i < n; i ++) {
if(i && points[i].y == points[i - 1].y) { // 在一行
l ++; // 左边多一个
int t1 = query(find(points[i].x) - 1) - query(find(points[i - 1].x)); // 左右之和
int t2 = C(l, k) * C(line[find(points[i].y)] - l, k); // 上下
res += t1 * t2;
} else l = 0;
int d = find(points[i].x); // 下标
now[d] ++; // 新加入一个数
int down = col[find(points[i].x)] - now[d];
add(d, C(now[d], k) * C(down, k) - C(now[d] - 1, k) * C(down + 1, k)); // 更新
}
printf("%d\n", res & 2147483647); // 注意负数
return 0;
}
P1856 [IOI1998] [USACO5.5] 矩形周长Picture
P1502 窗口的星星
// 每个星星(x,y,c)
// 窗口的右上角只能在(x,y,x+w-1,y+h-1)中
// max{每个点所在矩形中值的的最大值}记为答案
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <array>
#include <queue>
using namespace std;
const int N = 2e4 + 5;
int n, w, h;
struct rect_t { int x1, y1, x2, y2, c; } rect[N];
struct operation_t {
int x, y1, y2, c;
bool operator < (const operation_t &op) const {
return x < op.x || (x == op.x && c < op.c);
}
};
vector<operation_t> oper;
vector<int> y;
int maxx[N * 8], add[N * 8];
inline int ls(int u) { return u << 1; }
inline int rs(int u) { return u << 1 | 1; }
inline void init() {
memset(maxx, 0, sizeof(maxx)), memset(add, 0, sizeof(add));
}
inline void push_down(int u) {
maxx[ls(u)] += add[u], add[ls(u)] += add[u];
maxx[rs(u)] += add[u], add[rs(u)] += add[u];
add[u] = 0;
}
inline void push_up(int u) {
maxx[u] = max(maxx[ls(u)], maxx[rs(u)]);
}
void modify(int u, int l, int r, int x, int y, int c) {
if(x <= l && r <= y) maxx[u] += c, add[u] += c;
else {
int mid = (l + r) >> 1;
push_down(u);
if(x <= mid) modify(ls(u), l, mid, x, y, c);
if(y > mid) modify(rs(u), mid + 1, r, x, y, c);
push_up(u);
}
}
inline int find(int x) {
return lower_bound(y.begin(), y.end(), x) - y.begin();
}
int main() {
int T;
scanf("%d", &T);
while(T --) {
scanf("%d%d%d", &n, &w, &h);
for(int i = 0, x, y, c; i < n; i ++) {
scanf("%d%d%d", &x, &y, &c);
rect[i] = {x, y, x + w, y + h - 1, c};
}
oper.resize(n << 1), y.resize(n << 1);
for(int i = 0; i < n; i ++) {
auto &[x1, y1, x2, y2, c] = rect[i];
oper[ls(i)] = {x1, y1, y2, c};
oper[rs(i)] = {x2, y1, y2, -c};
y[ls(i)] = y1, y[rs(i)] = y2;
}
sort(y.begin(), y.end()), y.erase(unique(y.begin(), y.end()), y.end());
sort(oper.begin(), oper.end());
init();
int res = 0;
for(int i = 0; i < (n << 1); i ++) {
modify(1, 0, int(y.size()) - 1, find(oper[i].y1), find(oper[i].y2), oper[i].c);
res = max(res, maxx[1]);
}
printf("%d\n", res);
}
return 0;
}
Q5.2.2.1. 矩形并的面积和周长
// 扫描线
// 每次只需统计个数>0的个数
// 使用cnt记录个数(对应区间的值),len记录>0的长度
// 周长: 算两边就可以了
点击查看代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 1e5 + 5;
typedef long long LL;
struct Rec { int x1, y1, x2, y2; } rec[N];
struct Data {
int y, x1, x2, z;
bool operator < (const Data &a) const {
return y < a.y || (y == a.y && z > a.z);
}
} a[N << 1];
int cnt[N << 3], len[N << 3];
int n, num[N << 1], tot;
inline int ls(int u) { return u << 1; }
inline int rs(int u) { return u << 1 | 1; }
void modify(int u, int l, int r, int x, int y, int z) {
if(x <= l && r <= y) cnt[u] += z;
else {
int mid = (l + r) >> 1;
if(x <= mid) modify(ls(u), l, mid, x, y, z);
if(y > mid) modify(rs(u), mid + 1, r, x, y, z);
}
if(cnt[u]) len[u] = num[r + 1] - num[l];
else if(l != r) len[u] = len[ls(u)] + len[rs(u)];
else len[u] = 0;
}
int find(int x) {
return std::lower_bound(num, num + tot, x) - num;
}
LL calc() { // 返回单边的和
for(int i = 0; i < n; i ++) {
auto [x1, y1, x2, y2] = rec[i];
a[ls(i)] = {y1, x1, x2, 1}, a[rs(i)] = {y2, x1, x2, -1};
num[ls(i)] = x1, num[rs(i)] = x2;
}
std::sort(a, a + (n << 1));
std::sort(num, num + (n << 1)), tot = std::unique(num, num + (n << 1)) - num;
memset(len + 1, 0, tot << 4), memset(cnt + 1, 0, tot << 4);
LL res = 0;
for(int i = 0; i < (n << 1); i ++) {
res -= a[i].z * len[1];
modify(1, 0, tot-1, find(a[i].x1), find(a[i].x2)-1, a[i].z);
res += a[i].z * len[1];
}
return res;
}
LL area() {
for(int i = 0; i < n; i ++) {
auto [x1, y1, x2, y2] = rec[i];
a[ls(i)] = {y1, x1, x2, 1}, a[rs(i)] = {y2, x1, x2, -1};
num[ls(i)] = x1, num[rs(i)] = x2;
}
std::sort(a, a + (n << 1));
std::sort(num, num + (n << 1)), tot = std::unique(num, num + (n << 1)) - num;
memset(len + 1, 0, tot << 4), memset(cnt + 1, 0, tot << 4);
LL res = 0;
for(int i = 0; i < (n << 1); i ++) {
if(i) res += len[1] * LL(a[i].y - a[i - 1].y);
modify(1, 0, tot-1, find(a[i].x1), find(a[i].x2)-1, a[i].z);
}
return res;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d%d%d%d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
LL res = calc();
for(int i = 0; i < n; i ++) std::swap(rec[i].x1, rec[i].y1), std::swap(rec[i].x2, rec[i].y2);
printf("%lld %lld", res + calc(), area());
return 0;
}
Q5.2.2.4. 立方体覆盖
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <array>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 105;
int n;
struct cube_t { int x1, y1, z1, x2, y2, z2; } cube[N];
struct operation_t {
int x, y1, y2, k;
bool operator < (const operation_t &op) const {
return x < op.x || (x == op.x && k > op.k);
}
};
vector<operation_t> oper;
vector<int> y;
int cnt[N * 8], len[N * 8];
inline int ls(int u) { return u << 1; }
inline int rs(int u) { return u << 1 | 1; }
inline void init() {
memset(cnt, 0, sizeof(cnt)), memset(len, 0, sizeof(len));
}
inline void push_up(int u, int l, int r) {
if(cnt[u]) len[u] = y[r + 1] - y[l];
else if(l != r) len[u] = len[ls(u)] + len[rs(u)];
else len[u] = 0;
}
void modify(int u, int l, int r, int x, int y, int c) {
if(x <= l && r <= y) cnt[u] += c, push_up(u, l, r);
else {
int mid = (l + r) >> 1;
if(x <= mid) modify(ls(u), l, mid, x, y, c);
if(y > mid) modify(rs(u), mid + 1, r, x, y, c);
push_up(u, l, r);
}
}
inline int find(int x) {
return lower_bound(y.begin(), y.end(), x) - y.begin();
}
LL area(int a, int b) {
oper.clear(), y.clear();
for(int i = 0; i < n; i ++) {
auto &[x1, y1, z1, x2, y2, z2] = cube[i];
if(z1 <= a && b <= z2) {
oper.push_back({x1, y1, y2, 1});
oper.push_back({x2, y1, y2, -1});
y.push_back(y1), y.push_back(y2);
}
}
sort(y.begin(), y.end()), y.erase(unique(y.begin(), y.end()), y.end());
sort(oper.begin(), oper.end());
init();
LL res = 0;
for(int i = 0; i < int(oper.size()); i ++) {
if(i) res += (LL)len[1] * (oper[i].x - oper[i - 1].x);
modify(1, 0, int(y.size()) - 2, find(oper[i].y1), find(oper[i].y2) - 1, oper[i].k);
}
return res;
}
LL volume() {
vector<int> z; // 所有的 z
for(int i = 0; i < n; i ++) {
z.push_back(cube[i].z1);
z.push_back(cube[i].z2);
}
sort(z.begin(), z.end());
LL res = 0;
for(int i = 0; i + 1 < int(z.size()); i ++)
if(z[i] != z[i + 1])
res += area(z[i], z[i + 1]) * (z[i + 1] - z[i]);
return res;
}
int main() {
scanf("%d", &n);
for(int i = 0, x, y, z, r; i < n; i ++) {
scanf("%d%d%d%d", &x, &y, &z, &r);
cube[i] = {x - r, y - r, z - r, x + r, y + r, z + r};
}
printf("%lld\n", volume());
return 0;
}