洛谷P4169 [Violet]天使玩偶/SJY摆棋子(CDQ分治)

秒速五厘米 2023-08-17 17:21 73阅读 0赞

# \[Violet\]天使玩偶/SJY摆棋子 #

[题目传送门][Link 1]

## 解题思路 ##

用CDQ分治开了氧气跑过。

将输入给的顺序作为第一维的时间，x为第二维，y为第三维。对于距离一个询问(ax,ay)，将询问分为四块，左上，右上，左下，右下，对于坐下，左下的dist即为ax+ay-max(bx+by)。所以只要查询时间小于自己的点里x+y最大的即可。对于其他四块，都可以转为左下，各自跑一遍CDQ。

## 代码如下 ##

#include <bits/stdc++.h> using namespace std; int n, m; const int N = 1e6+5; struct T{ int t, x, y; bool f; T(){} T(int t, int x, int y, bool f): t(t), x(x), y(y), f(f){} }v[N], t[N], a[N]; int c[N]; int lowbit(int x) { return x & (-x); } void update(int x, int v) { for(int i = x; i < N; i += lowbit(i)) c[i] = max(c[i], v); } int query(int x) { int ans = -1; for(int i = x; i > 0; i -= lowbit(i)){ ans = max(c[i], ans); } return ans; } void clear(int x) { for(int i = x; i < N; i += lowbit(i)) c[i] = 0; } int ans[N]; void CDQ(int l, int r) { if(l == r) return; int mid = (l + r) / 2; CDQ(l, mid); CDQ(mid + 1, r); for(int i = l; i <= r; i ++) t[i] = v[i]; int x = l, y = mid + 1; int cnt = l - 1; while(x <= mid || y <= r){ if(x <= mid && y <= r){ if(t[x].x <= t[y].x){ if(!t[x].f)update(t[x].y, t[x].x + t[x].y); v[++cnt] = t[x]; ++x; } else { int r = query(t[y].y); if(t[y].f && r) ans[t[y].t] = min(ans[t[y].t], t[y].x + t[y].y - r); v[++cnt] = t[y]; ++y; } } else if(x <= mid){ if(!t[x].f)update(t[x].y, t[x].x + t[x].y); v[++cnt] = t[x]; ++x; } else { int r = query(t[y].y); if(t[y].f && r) ans[t[y].t] = min(ans[t[y].t], t[y].x + t[y].y - r); v[++cnt] = t[y]; ++y; } } for(int i = l; i <= mid; i ++) if(!t[i].f)clear(t[i].y); } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++){ int x, y; scanf("%d%d", &x, &y); v[i] = T(0, x + 1, y + 1, 0); } for(int i = 1; i <= m; i ++){ int t, x, y; scanf("%d%d%d", &t, &x, &y); v[n+i] = T(i, x + 1, y + 1, t - 1); } int lx, ly; lx = ly = 0; for(int i = 1; i <= n + m; i ++){ a[i] = v[i]; lx = max(lx, v[i].x + 1); ly = max(ly, v[i].y + 1); } memset(ans, 0x3f, sizeof(ans)); CDQ(1, n + m); for(int i = 1; i <= n + m; i ++){ v[i] = a[i]; v[i].x = lx - v[i].x; } CDQ(1, n + m); for(int i = 1; i <= n + m; i ++){ v[i] = a[i]; v[i].y = ly - v[i].y; } CDQ(1, n + m); for(int i = 1; i <= n + m; i ++){ v[i] = a[i]; v[i].x = lx - v[i].x; v[i].y = ly - v[i].y; } CDQ(1, n + m); for(int i = 1; i <= m; i ++){ if(a[i + n].f) printf("%d\n", ans[i]); } return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11545428.html

[Link 1]: https://www.luogu.org/problem/P4169