首页 > 代码库 > uva 1492 - Adding New Machine(线段树)
uva 1492 - Adding New Machine(线段树)
题目链接:uva 1492 - Adding New Machine
题目大意:在一个R?C矩阵上有N台旧的机器,给定每个机器的占地,现在要添加一台1?M的机器,问有多少种摆放方法。
解题思路:问题可以转化成矩形覆盖问题,对于每台旧的机器,假设考虑对应每个位置向右放,那么左边的M-1个位置是不能放的,以及右边界左边的M-1个位置。用线段树解决矩形覆盖,x,y坐标分别处理一次。注意M=1的情况。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
const int maxn = 50100;
ll N;
int M;
int x[2][maxn], y[2][maxn];
vector<int> bset, vec;
struct Segment {
int l, r, h, v;
void set(int l, int r, int h, int v) {
this->l = l;
this->r = r;
this->h = h;
this->v = v;
}
}seg[maxn*2], node[maxn*8];
inline bool cmp (const Segment& a, const Segment& b) {
return a.h < b.h;
}
inline int search (int x) {
return lower_bound(bset.begin(), bset.end(), x) - bset.begin();
}
inline void get_hashkey () {
sort(vec.begin(), vec.end());
bset.push_back(vec[0]);
for (int i = 1; i < vec.size(); i++) {
if (vec[i] != vec[i-1])
bset.push_back(vec[i]);
}
}
inline void add_segment (int i, int h, int l, int r, int v) {
seg[i].set(l, r, h, v);
vec.push_back(l);
vec.push_back(r);
}
inline void pushup (int u) {
if (node[u].h)
node[u].v = bset[node[u].r+1] - bset[node[u].l];
else if (node[u].l == node[u].r)
node[u].v = 0;
else
node[u].v = node[lson(u)].v + node[rson(u)].v;
}
void build_segTree (int u, int l, int r) {
node[u].set(l, r, 0, 0);
if (l == r) {
pushup(u);
return ;
}
int mid = (l + r) / 2;
build_segTree(lson(u), l, mid);
build_segTree(rson(u), mid + 1, r);
pushup(u);
}
ll query_segTree (int u, int l, int r) {
if (l <= node[u].l && node[u].r <= r)
return node[u].v;
int mid = (node[u].l + node[u].r) / 2;
ll ret = 0;
if (l <= mid)
ret += query_segTree(lson(u), l, r);
if (r > mid)
ret += query_segTree(rson(u), l, r);
return ret;
}
void add_segTree (int u, int l, int r, int v) {
if (l <= node[u].l && node[u].r <= r) {
node[u].h += v;
pushup(u);
return;
}
int mid = (node[u].l + node[u].r) / 2;
if (l <= mid)
add_segTree(lson(u), l, r, v);
if (r > mid)
add_segTree(rson(u), l, r, v);
pushup(u);
}
ll solve (int x[2][maxn], int y[2][maxn], ll R, ll C) {
if (N == 0)
return 1LL * C * (R - M + 1);
int n = 0;
vec.clear();
bset.clear();
for (int i = 0; i < N; i++) {
add_segment(n++, x[0][i] - 1, max(y[0][i] - M, 0), y[1][i], 1);
add_segment(n++, x[1][i], max(y[0][i] - M, 0), y[1][i], -1);
}
add_segment(n++, 0, max((int)R + 1 - M, 0), R, 1);
add_segment(n++, C, max((int)R + 1 - M, 0), R, -1);
get_hashkey();
sort(seg, seg + n, cmp);
int size = bset.size() - 2;
build_segTree (1, 0, size);
ll ret = 0;
for (int i = 0; i < n; i++) {
ll tmp = query_segTree(1, 0, size);
if (i)
ret += tmp * (seg[i].h - seg[i-1].h);
add_segTree(1, search(seg[i].l), search(seg[i].r) - 1, seg[i].v);
}
return R * C - ret;
}
int main () {
ll R, C;
while (scanf("%lld%lld%lld%d", &R, &C, &N, &M) == 4) {
for (int i = 0; i < N; i++)
scanf("%d%d%d%d", &x[0][i], &y[0][i], &x[1][i], &y[1][i]);
ll ans = solve(x, y, C, R) + solve(y, x, R, C);
if (M == 1)
ans /= 2;
printf("%lld\n", ans);
}
return 0;
}
uva 1492 - Adding New Machine(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。