首页 > 代码库 > CSU 1786 莫队+KDTree
CSU 1786 莫队+KDTree
题意 给出n个二维点(2e5) 和 q个询问(1e4) 每个询问给lr 问点l到r间有多少对点的曼哈顿距离<=d 点的坐标<=108
想出了莫队算法 复杂度n^1.5 看起来很科学 但是每次del和add点是直接进行暴力扫当前LR区间的点来算 ans将要增加/减少多少 实际这样的复杂度是V^2.5 会t掉
由于是在二维上找一定范围的点的数目 就可以想到KDTree V^1.5log(n)在15s下还是很科学的
做了一些曼哈顿距离的getdis函数 调完又t了。。
我使用了一下青岛的K的写法 开出三个维度 x y id 每次询问的是 和x1y1曼哈顿距离<=d 并且 L <= id <= R 的点 因为曼哈顿不是一个矩形 是一个正方形旋转了的图形 搜起来会比较麻烦
但是我感觉这个就是正解。。在网上也百度不到题解 于是出去问了一下别人对这个题的看法 然而也是莫队+KDT做的 就很迷茫
要来代码一看 有一个和我不同的是这样的 把输入进去的xy 都变成x+y 和 x-y 在查询的时候不围绕改变后的xy做一个曼哈顿的查询 而是直接查询矩形
xl = x - d xr = x + d yl = y - d yr = y + d 这样
查了查对这个优化的意义 这个优化的意思 是 把曼哈顿距离转化为切比雪夫距离
http://m.blog.csdn.net/article/details?id=47259831 这个里面讲的
旋转之前两个点的曼哈顿距离是d 那么旋转后两个点的切比雪夫距离也是d 所以由一个点就可以求出来一个矩阵出来 KDT跑矩阵很快
还有一个点 就是KDT的删除点
KDT的插入点是很简单的logn操作 但是删除点的话 由于这个点可能管辖一定的点 删除了它就需要从它的孩子中找出一个点来管辖这个区域 相当于每次删除都重构
其实不需要这样 我们可以先把这棵树建出来 一开始这个树只有形状 但是点都没有放进去 每次放进去一个点就相当于点亮一个点
可以做一个类似于离线的操作 我们现在已经知道哪些点会被插入进这个树了 只要它进去 我们就记录下来
然后用这些点的形状建树 虽然一开始没有点被插进去
我们在结构体里面定义val代表当前的管辖点存在与否/有多少个 sum代表这个区域有多少个 fa代表这个点的父亲节点是谁
所以每次删除或者插入一个点 只需要改掉这个点的val 然后把这个点及其先辈的sum改了就可以了 由于我们事先知道了所有的点 所以建出来的树深度还是logn的
这种KDT写法也是很优雅的。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define pb push_back
int n , d , q ;
int m , root , cmp_d ;
int xl , xr , yl , yr ;
int L , R ;
struct node {
int d[3] , Max[3] , Min[3] ;
int sum ;
int fa ;
int val ;
int l , r ;
int id ;
}tr[200050];
bool cmp(node a , node b) {
return a.d[cmp_d] < b.d[cmp_d] ;
}
int ix[200050] , iy[200050] ;
int pos[200050] ;
struct no {
int l , r ;
int id ;
}xw[10050];
bool cmp2(no a , no b) {
if(pos[a.l] == pos[b.l]) return a.r < b.r ;
return a.l < b.l ;
}
int an ;
int ans[10050] ;
void up(int p , int k) {
for(int i=0;i<2;i++) {
if(tr[p].Max[i] < tr[k].Max[i]) tr[p].Max[i] = tr[k].Max[i] ;
if(tr[p].Min[i] > tr[k].Min[i]) tr[p].Min[i] = tr[k].Min[i] ;
}
tr[p].sum += tr[k].sum ;
}
int w[200050] ;
int build(int l , int r , int D , int fa) {
int mid = (l + r) >> 1 ;
cmp_d = D ;
nth_element(tr+l+1,tr+mid+1,tr+r+1,cmp) ;
w[tr[mid].id] = mid ;
tr[mid].fa = fa ;
tr[mid].val = 0 ;
tr[mid].sum = 0 ;
for(int i = 0 ; i < 2 ; i ++ ) tr[mid].Max[i] = tr[mid].Min[i] = tr[mid].d[i] ;
if(l != mid) tr[mid].l = build(l , mid-1 , D^1 , mid) ; else tr[mid].l = 0 ;
if(r != mid) tr[mid].r = build(mid+1 , r , D^1 , mid) ; else tr[mid].r = 0 ;
if(tr[mid].l) up(mid , tr[mid].l) ;
if(tr[mid].r) up(mid , tr[mid].r) ;
return mid ;
}
void upda(int rt , int val) {
tr[rt].val += val ;
while(rt) {
tr[rt].sum += val ;
rt = tr[rt].fa ;
}
}
int query(int p) {
if(tr[p].sum == 0) return 0 ;
if(tr[p].Max[0] < xl || tr[p].Min[0] > xr || tr[p].Max[1] < yl || tr[p].Min[1] > yr) return 0 ;
if(tr[p].Max[0] <= xr && tr[p].Min[0] >= xl && tr[p].Max[1] <= yr && tr[p].Min[1] >= yl) return tr[p].sum ;
int ret = 0 ;
if(tr[p].d[0] <= xr && tr[p].d[0] >= xl && tr[p].d[1] <= yr && tr[p].d[1] >= yl) ret += tr[p].val ;
if(tr[p].l) ret += query(tr[p].l) ;
if(tr[p].r) ret += query(tr[p].r) ;
return ret ;
}
void cxh(int x , int y) {
xl = x - d ; xr = x + d ;
yl = y - d ; yr = y + d ;
}
int main () {
int cas = 1 ;
while(scanf("%d%d%d" , &n , &d , &q) != EOF) {
int sz = sqrt(n) ;
for(int i = 1 ; i <= n ; i ++ ) {
scanf("%d%d" , &ix[i] , &iy[i]) ;
pos[i] = i / sz ;
tr[i].l = tr[i].r = 0 ;
tr[i].d[0] = ix[i] + iy[i] ;
tr[i].d[1] = ix[i] - iy[i] ;
int z = ix[i] ;
ix[i] = ix[i] + iy[i] ;
iy[i] = z - iy[i] ;
tr[i].id = i ;
}
root = build(1 , n , 0 , 0) ;
an = 0 ;
for(int i = 1 ; i <= q ; i ++ ) {
scanf("%d%d" , &xw[i].l , &xw[i].r) ;
xw[i].id = i ;
}
L = 0 ;
R = 0 ;
sort(xw+1,xw+1+q,cmp2) ;
for(int i = 1 ; i <= q ; i ++ ) {
while(L < xw[i].l) {
cxh(ix[L] , iy[L]) ;
upda(w[L] , -1) ;
L ++ ;
an -= query(root) ;
}
while(L > xw[i].l) {
L -- ;
cxh(ix[L] , iy[L]) ;
an += query(root) ;
upda(w[L] , 1) ;
}
while(R < xw[i].r) {
R ++ ;
cxh(ix[R] , iy[R]) ;
an += query(root) ;
upda(w[R] , 1) ;
}
while(R > xw[i].r) {
cxh(ix[R] , iy[R]) ;
upda(w[R] , -1) ;
R -- ;
an -= query(root) ;
}
ans[xw[i].id] = an ;
}
printf("Case %d:\n" , cas ++ ) ;
for(int i = 1 ; i <= q ; i ++ ) printf("%d\n" , ans[i]) ;
}
}
CSU 1786 莫队+KDTree