K-D树
看到BZOJ上有道新数据结构题，A的人挺多的，但感觉不太会做，于是发现了这个数据结构
基本操作：
1.建树：在当前方向上取中心点当做根节点，左边的为左儿子，右边的为右儿子
2.插入：和平衡树差不多，不过插完后不用旋转
3.找K邻近点：从根节点开始，不断更新答案，可以剪枝达到O(sqrt(n))复杂度
BZOJ2648 操作1、2、3（最近点）
#include<cstdio>
#include<algorithm>
#define M 1111111
#define inf 1e9
using namespace std;
struct T{int d[2],min[2],max[2],l,r;}t[M];
int n,m,root,D,ans,p,i,I[2];
bool cmp(T a,T b){return a.d[D]<b.d[D]||(a.d[D]==b.d[D]&&a.d[D^1]<b.d[D^1]);}
void pushup(int k){
int l=t[k].l,r=t[k].r;
for(int i=0;i<2;i++){
if(l)t[k].min[i]=min(t[k].min[i],t[l].min[i]),t[k].max[i]=max(t[k].max[i],t[l].max[i]);
if(r)t[k].min[i]=min(t[k].min[i],t[r].min[i]),t[k].max[i]=max(t[k].max[i],t[r].max[i]);
}
}
int dis(T k){return max(k.min[0]-I[0],0)+max(I[0]-k.max[0],0)+max(k.min[1]-I[1],0)+max(I[1]-k.max[1],0);}
int build(int l,int r,int now){//建立K-D树
D=now;//方向
int mid=(l+r)>>1;
nth_element(t+l+1,t+mid+1,t+r+1,cmp);//找第mid大值
for(int i=0;i<2;i++)t[mid].min[i]=t[mid].max[i]=t[mid].d[i];
if(l<mid)t[mid].l=build(l,mid-1,now^1);
if(r>mid)t[mid].r=build(mid+1,r,now^1);
pushup(mid);
return mid;
}
void insert(int k,int now){//插入一个点
if(I[now]<t[k].d[now]){
if(t[k].l)insert(t[k].l,now^1);else{
t[k].l=++n;
for(int i=0;i<2;i++)t[n].max[i]=t[n].min[i]=t[n].d[i]=I[i];
}
}else{
if(t[k].r)insert(t[k].r,now^1);else{
t[k].r=++n;
for(int i=0;i<2;i++)t[n].max[i]=t[n].min[i]=t[n].d[i]=I[i];
}
}
pushup(k);
}
void query(int k,int now){//求离当前点最近点
int d=abs(t[k].d[0]-I[0])+abs(t[k].d[1]-I[1]),dl=inf,dr=inf;
ans=min(ans,d);//更新答案
if(t[k].l)dl=dis(t[t[k].l]);
if(t[k].r)dr=dis(t[t[k].r]);
if(dl<dr){//向子树找答案
if(dl<ans)query(t[k].l,now^1);
if(dr<ans)query(t[k].r,now^1);
}else{
if(dr<ans)query(t[k].r,now^1);
if(dl<ans)query(t[k].l,now^1);
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
while(m--){
scanf("%d%d%d",&p,&I[0],&I[1]);
if(p==1)insert(root,0);else{
ans=inf;query(root,0);
printf("%d\n",ans);
}
}
}
BZOJ1941 只有操作1、3（极值）的裸题
#include<cstdio>
#include<algorithm>
#define M 1111111
#define inf 1e9
using namespace std;
struct T{int d[2],min[2],max[2],l,r;}t[M];
int n,m,root,D,ans,ans1,ans2,i,I[2];
bool cmp(T a,T b){return a.d[D]<b.d[D]||(a.d[D]==b.d[D]&&a.d[D^1]<b.d[D^1]);}
void pushup(int k){
int l=t[k].l,r=t[k].r;
for(int i=0;i<2;i++){
if(l)t[k].min[i]=min(t[k].min[i],t[l].min[i]),t[k].max[i]=max(t[k].max[i],t[l].max[i]);
if(r)t[k].min[i]=min(t[k].min[i],t[r].min[i]),t[k].max[i]=max(t[k].max[i],t[r].max[i]);
}
}
int mindis(T k){return max(k.min[0]-I[0],0)+max(I[0]-k.max[0],0)+max(k.min[1]-I[1],0)+max(I[1]-k.max[1],0);}
int maxdis(T k){return max(abs(I[0]-k.min[0]),abs(I[0]-k.max[0]))+max(abs(I[1]-k.min[1]),abs(I[1]-k.max[1]));}
int build(int l,int r,int now){
D=now;int mid=(l+r)>>1;
nth_element(t+l+1,t+mid+1,t+r+1,cmp);
for(int i=0;i<2;i++)t[mid].max[i]=t[mid].min[i]=t[mid].d[i];
if(l<mid)t[mid].l=build(l,mid-1,now^1);
if(r>mid)t[mid].r=build(mid+1,r,now^1);
pushup(mid);
return mid;
}
void querymin(int k,int now){
int d=abs(t[k].d[0]-I[0])+abs(t[k].d[1]-I[1]),dl=inf,dr=inf;
if(d)ans1=min(ans1,d);
if(t[k].l)dl=mindis(t[t[k].l]);
if(t[k].r)dr=mindis(t[t[k].r]);
if(dl<dr){
if(dl<ans1)querymin(t[k].l,now^1);
if(dr<ans1)querymin(t[k].r,now^1);
}else{
if(dr<ans1)querymin(t[k].r,now^1);
if(dl<ans1)querymin(t[k].l,now^1);
}
}
void querymax(int k,int now){
int d=abs(t[k].d[0]-I[0])+abs(t[k].d[1]-I[1]),dl=-inf,dr=-inf;
if(d)ans2=max(ans2,d);
if(t[k].l)dl=maxdis(t[t[k].l]);
if(t[k].r)dr=maxdis(t[t[k].r]);
if(dl>dr){
if(dl>ans2)querymax(t[k].l,now^1);
if(dr>ans2)querymax(t[k].r,now^1);
}else{
if(dr>ans2)querymax(t[k].r,now^1);
if(dl>ans2)querymax(t[k].l,now^1);
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
ans=inf;
for(i=1;i<=n;i++){
I[0]=t[i].d[0],I[1]=t[i].d[1];
ans1=inf;querymin(root,0);
ans2=-inf;querymax(root,0);
if(ans2-ans1<ans)ans=ans2-ans1;
}
printf("%d",ans);
}
BZOJ4066 KD树的重建，树的重建大概就是偏移到一定程度时暴力重新建树
#include<cstdio>
#include<algorithm>
#define inf 1e9
#define N 222222
using namespace std;
struct Tree{int d[2],mn[2],mx[2],l,r,D,size,sum,v;}t[N],now;
int m,n,x1,x2,y1,y2,D,w,cnt,tot,ans,root,p[N];char ch;
#define L t[x].l
#define R t[x].r
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline bool cmp(int x,int y){return t[x].d[D]<t[y].d[D];}
inline void pushup(int x){
for(int i=0;i<=1;i++)t[x].mn[i]=min(t[x].mn[i],min(t[L].mn[i],t[R].mn[i])),t[x].mx[i]=max(t[x].mx[i],max(t[L].mx[i],t[R].mx[i]));
t[x].sum=t[L].sum+t[R].sum+t[x].v;
t[x].size=t[L].size+t[R].size+1;
}
inline int build(int l,int r,int fx){
D=fx;
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1,cmp);
int x=p[mid];
t[x].D=fx;
for(int i=0;i<2;i++)t[x].mn[i]=t[x].mx[i]=t[x].d[i];
t[x].sum=t[x].v;
if(l<mid)L=build(l,mid-1,fx^1);else L=0;
if(r>mid)R=build(mid+1,r,fx^1);else R=0;
pushup(x);
return x;
}
inline void dfs(int x){
if(!x)return;
dfs(L);
p[++cnt]=x;
dfs(R);
}
inline void rebuild(int &x){//重建
cnt=0;dfs(x);
x=build(1,cnt,t[x].D);
}
inline void insert(int &x,int fx){
if(!x){//新建节点
x=++tot;t[x]=now;
for(int i=0;i<2;i++)t[x].mn[i]=t[x].mx[i]=t[x].d[i];
t[x].D=fx;t[x].size=1;t[x].sum=t[x].v;
return;
}
if(now.d[fx]<t[x].d[fx]){
insert(L,fx^1);
pushup(x);
if((double)t[L].size>(double)t[x].size*0.7)rebuild(x);
}else{
insert(R,fx^1);
pushup(x);
if((double)t[R].size>(double)t[x].size*0.7)rebuild(x);
}
}
int query(int x,int x1,int y1,int x2,int y2){
if(!x)return 0;
if(t[x].mn[0]>=x1&&t[x].mn[1]>=y1&&t[x].mx[0]<=x2&&t[x].mx[1]<=y2)return t[x].sum;else{//包含整个区间
int ans=0;
if(t[x].d[0]>=x1&&t[x].d[0]<=x2&&t[x].d[1]>=y1&t[x].d[1]<=y2)ans+=t[x].v;//包含这个点
if(t[L].mn[0]>x2||t[L].mx[0]<x1||t[L].mn[1]>y2||t[L].mx[1]<y1);else ans+=query(L,x1,y1,x2,y2);
if(t[R].mn[0]>x2||t[R].mx[0]<x1||t[R].mn[1]>y2||t[R].mx[1]<y1);else ans+=query(R,x1,y1,x2,y2);
return ans;
}
}
int main(){
for(int i=0;i<=1;i++)t[0].mn[i]=inf,t[0].mx[i]=-inf;
t[0].size=t[0].sum=t[0].v=0;
n=read();
while(scanf("%d",&w)!=EOF&&w<3)
if(w==1){
now.d[0]=read()^ans;now.d[1]=read()^ans;now.v=read()^ans;
insert(root,1);
}else{
x1=read()^ans;y1=read()^ans;x2=read()^ans;y2=read()^ans;
printf("%d\n",ans=query(root,x1,y1,x2,y2));
}
}
BZOJ3489 K-D树解决传统区间问题
建立三维K-D树{i,l[i],r[i]}，l[i]表示左边第一个数，r[i]表示右边第一个数，查询的时候三维空间查询范围分别是[l,r][0.l-1][r+1,n+1]，查询最大值即可，时间复杂度n^(5/3)
#include<cstdio>
#include<algorithm>
#define N 100010
struct T{int d[3],mi[3],ma[3],s[2],mv,v;}t[N];
int n,m,x,l,r,ans,i,D,rt,la[N],I[3][2];
#define L t[k].s[0]
#define R t[k].s[1]
#define MAX(a,b)(a<b?a=b:a)
#define MIN(a,b)(a>b?a=b:a)
#define rep(i,b)for(int i=0;i<b;i++)
bool cmp(T a,T b){return a.d[D]<b.d[D];}
void ps(int k,int s){rep(i,3)MIN(t[k].mi[i],t[s].mi[i]),MAX(t[k].ma[i],t[s].ma[i]),MAX(t[k].mv,t[s].mv);}
int bd(int l,int r,int d){
D=d;int k=l+r>>1;
std::nth_element(t+l+1,t+k,t+r+1,cmp);
rep(i,3)t[k].mi[i]=t[k].ma[i]=t[k].d[i];
if(l<k)L=bd(l,k-1,(d+1)%3),ps(k,L);
if(r>k)R=bd(k+1,r,(d+1)%3),ps(k,R);
return k;
}
bool ok(int k){rep(i,3)if(I[i][0]>t[k].ma[i]||I[i][1]<t[k].mi[i])return 0;return 1;}
void qr(int k){
if(ans>t[k].mv)return;bool ff=1;
rep(i,3)if(I[i][0]>t[k].mi[i]||t[k].ma[i]>I[i][1])ff=0;
if(ff){MAX(ans,t[k].mv);return;}ff=1;
rep(i,3)if(I[i][0]>t[k].d[i]||t[k].d[i]>I[i][1])ff=0;
if(ff)MAX(ans,t[k].v);
if(L&&ok(L))qr(L);if(R&&ok(R))qr(R);
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;la[x]=i,i++){
scanf("%d",&x);t[i].d[0]=i;t[i].d[2]=n+1;t[i].mv=t[i].v=x;
if(la[x])t[i].d[1]=la[x],t[la[x]].d[2]=i;
}
for(rt=bd(1,n,0);m--;qr(rt),printf("%d\n",ans)){
scanf("%d%d",&l,&r);l=(l+ans)%n+1;r=(r+ans)%n+1;if(l>r)l^=r^=l^=r;
ans=0;I[0][0]=l;I[0][1]=r;I[1][0]=0;I[1][1]=l-1;I[2][0]=r+1;I[2][1]=n+1;
}
}
BZOJ4154 树上问题转化为K-D树，X一维表示DFS序，Y一维表示深度，那么修改就是在[st[x],ed[x]][d[x],d[x]+l]上区间覆盖，K-D树标记下传即可，时间复杂度O(nlgn+qn^0.5)
#include<bits/stdc++.h>
#define N 100100
using namespace std;int W,n,c,q,i,x,y,z,rt,x1,Y1,x2,y2,D,mt,tp,tot,ans,st[N],ed[N],h[N],la[N],ne[N],fir[N],ts[N],to[N];
struct T{int d[2],mi[2],ma[2],l,r,f,co,lz;}t[N];bool cmp(T a,T b){return a.d[D]<b.d[D]||(a.d[D]==b.d[D]&&a.d[D^1]<b.d[D^1]);}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
t[x].lz=x;t[x].d[0]=st[x]=++mt;t[x].d[1]=h[x];
for(int i=fir[x];i;i=ne[i])h[la[i]]=h[x]+1,dfs(la[i]);ed[x]=mt;
}
void ad(int x,int z){if(!x)return;t[x].co=t[x].lz=z;}
void ps(int k,int x){for(int i=0;i<2;i++)t[k].mi[i]=min(t[k].mi[i],t[x].mi[i]),t[k].ma[i]=max(t[k].ma[i],t[x].ma[i]);}
void pd(int k){if(t[k].lz)ad(t[k].l,t[k].lz),ad(t[k].r,t[k].lz),t[k].lz=0;}
int bt(int l,int r,int o,int fa){
D=o;int i,k=l+r>>1;nth_element(t+l+1,t+k+1,t+r+1,cmp);t[k].f=fa;
for(i=0;i<2;i++)t[k].mi[i]=t[k].ma[i]=t[k].d[i];
if(l<k)t[k].l=bt(l,k-1,o^1,k),ps(k,t[k].l);
if(r>k)t[k].r=bt(k+1,r,o^1,k),ps(k,t[k].r);
to[t[k].lz]=k;t[k].lz=0;t[k].co=1;return k;
}
void add(int k){
if(t[k].ma[0]<x1||t[k].mi[0]>x2||t[k].ma[1]<Y1||t[k].mi[1]>y2)return;
if(t[k].mi[0]>=x1&&t[k].mi[1]>=Y1&&t[k].ma[0]<=x2&&t[k].ma[1]<=y2){ad(k,z);return;}
pd(k);if(t[k].d[0]>=x1&&t[k].d[0]<=x2&&t[k].d[1]>=Y1&&t[k].d[1]<=y2)t[k].co=z;
if(t[k].l)add(t[k].l);if(t[k].r)add(t[k].r);
}
int get(int x){
for(int y=ts[tp=1]=x;t[y].f;ts[++tp]=y=t[y].f);
for(;tp;pd(ts[tp--]));
return t[x].co;
}
int main(){
for(scanf("%d",&W);W--;tot=mt=ans=0){
for(scanf("%d%d%d",&n,&c,&q),i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
for(h[1]=1,dfs(1),rt=bt(1,n,0,0),i=1;i<=q;i++)
if(scanf("%d%d%d",&x,&y,&z),!z)ans=(1ll*i*get(to[x])+ans)%1000000007;else x1=st[x],x2=ed[x],Y1=h[x],y2=min(h[x]+y,n),add(rt);
for(printf("%d\n",ans),i=1;i<=n;i++)fir[i]=t[i].l=t[i].r=0;
}
}
BZOJ4303 K-D树往下打标记就可以了，可是这题卡时间，要卡几发才能过
#include<bits/stdc++.h>
#define M 536870912
using namespace std;int n,m,i,rt,w,l,r,x,y,O,X0,Y0,X1,Y1;
struct P{int d[2],mi[2],mx[2],l,r,s,v,x,y,sz;}t[50050];bool cmp(P a,P b){return a.d[O]<b.d[O];}
char ch;inline void rd(int&x){for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
inline void Max(int&x,int y){x=max(x,y);}
inline void Min(int&x,int y){x=min(x,y);}
inline void cha(int k,int x,int y){
if(!k)return;t[k].v=(1ll*x*t[k].v+y)%M;t[k].s=(1ll*x*t[k].s+1ll*y*t[k].sz)%M;
int X=t[k].x,Y=t[k].y;t[k].x=1ll*x*X%M;t[k].y=(1ll*Y*x+y)%M;
}
inline void pd(int k){
if(t[k].x==1&&t[k].y==0)return;
cha(t[k].l,t[k].x,t[k].y);cha(t[k].r,t[k].x,t[k].y);t[k].x=1,t[k].y=0;
}
inline int bt(int l,int r,int o){
O=o;int k=l+r>>1,i;nth_element(t+l+1,t+k+1,t+r+1,cmp);
for(i=0;i<2;i++)t[k].mi[i]=t[k].mx[i]=t[k].d[i];t[k].x=1;
if(l<k)for(O=t[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Min(t[k].mi[i],t[O].mi[i]),Max(t[k].mx[i],t[O].mx[i]);
if(k<r)for(O=t[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Min(t[k].mi[i],t[O].mi[i]),Max(t[k].mx[i],t[O].mx[i]);
t[k].sz=t[t[k].l].sz+t[t[k].r].sz+1;return k;
}
inline void add(int k,int x,int y){
if(X0>t[k].mx[0]||Y0<t[k].mi[0]||X1>t[k].mx[1]||Y1<t[k].mi[1])return;
if(X0<=t[k].mi[0]&&Y0>=t[k].mx[0]&&X1<=t[k].mi[1]&&Y1>=t[k].mx[1]){cha(k,x,y);return;}
if(X0<=t[k].d[0]&&t[k].d[0]<=Y0&&X1<=t[k].d[1]&&t[k].d[1]<=Y1)t[k].v=(1ll*t[k].v*x+y)%M;
pd(k);add(t[k].l,x,y);add(t[k].r,x,y);t[k].s=(t[k].v+t[t[k].l].s+t[t[k].r].s)%M;
}
inline int qu(int k){
if(X0>t[k].mx[0]||Y0<t[k].mi[0]||X1>t[k].mx[1]||Y1<t[k].mi[1])return 0;
if(X0<=t[k].mi[0]&&Y0>=t[k].mx[0]&&X1<=t[k].mi[1]&&Y1>=t[k].mx[1])return t[k].s;
int w=0;if(X0<=t[k].d[0]&&t[k].d[0]<=Y0&&X1<=t[k].d[1]&&t[k].d[1]<=Y1)w=t[k].v;
pd(k);w=(w+qu(t[k].l))%M;w=(w+qu(t[k].r))%M;return w;
}
int main(){
for(rd(n),rd(m),i=1;i<=n;i++)rd(t[i].d[1]),t[i].d[0]=i;
for(rt=bt(1,n,0);m--;){
rd(w);rd(l);rd(r);
if(!w)rd(x),rd(y),x%=M,y%=M,X0=l,Y0=r,X1=1,Y1=n,add(rt,x,y);
if(w==1)rd(x),rd(y),x%=M,y%=M,X0=1,Y0=n,X1=l,Y1=r,add(rt,x,y);
if(w==2)X0=l,Y0=r,X1=1,Y1=n,printf("%d\n",qu(rt));
if(w==3)X0=1,Y0=n,X1=l,Y1=r,printf("%d\n",qu(rt));
}
}
BZOJ3616 先K-D树求出每个点会被哪些点打到，存到bitset中，加完后传标记。然后对同类点再一遍bitset统计，时间复杂度O(n^1.5+n^2/32)
#include<bits/stdc++.h>
#define N 35555
#define Max(a,b)(a<b?a=b:a)
#define Min(a,b)(a>b?a=b:a)
#define sqr(x)(x*x)
using namespace std;int n,m,k,i,j,O,u,x,rt,X,Y,to[N],R[N],W[N];double ans;vector<int>v[N],H[N];bitset<N>G[N],o;
struct P{int id,l,r,d[2],mi[2],mx[2];}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
double pw(double x,int y){double v=1.0;for(;y;x*=x,y>>=1)if(y&1)v*=x;return v;}
int bt(int l,int r,int o){
O=o;int k=l+r>>1,i;nth_element(T+l+1,T+k+1,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mx[i]=T[k].d[i];to[T[k].id]=k;
if(l<k)for(u=T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Min(T[k].mi[i],T[u].mi[i]),Max(T[k].mx[i],T[u].mx[i]);
if(k<r)for(u=T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Min(T[k].mi[i],T[u].mi[i]),Max(T[k].mx[i],T[u].mx[i]);
return k;
}
int ck1(P a){return(sqr(max(max(X-a.mx[0],a.mi[0]-X),0))+sqr(max(max(Y-a.mx[1],a.mi[1]-Y),0))<=R[i]*R[i])?((max(sqr(X-a.mx[0]),sqr(a.mi[0]-X))+max(sqr(Y-a.mx[1]),sqr(a.mi[1]-Y)))<=R[i]*R[i])?1:2:0;}
int ck2(P a){return(max(max(X-a.mx[0],a.mi[0]-X),0)+max(max(Y-a.mx[1],a.mi[1]-Y),0)<=W[i])?(max(abs(X-a.mx[0]),abs(a.mi[0]-X))+max(abs(Y-a.mx[1]),abs(a.mi[1]-Y))<=W[i])?1:2:0;}
void add(int k){
if(!k)return;int A=ck1(T[k]),B=ck2(T[k]);if(A==1||B==1){G[k][i]=1;return;}if(!A&&!B)return;
if(sqr(X-T[k].d[0])+sqr(Y-T[k].d[1])<=R[i]*R[i])H[k].push_back(i);else if(abs(X-T[k].d[0])+abs(Y-T[k].d[1])<=W[i])H[k].push_back(i);
add(T[k].l);add(T[k].r);
}
void down(int k){
int i;if(i=T[k].l)G[i]|=G[k],down(i);if(i=T[k].r)G[i]|=G[k],down(i);
for(i=0;i<H[k].size();i++)G[k][H[k][i]]=1;
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d%d%d%d%d",&T[i].d[0],&T[i].d[1],&R[i],&W[i],&x),T[i].id=i,v[x].push_back(i);
for(rt=bt(1,n,0),i=1;i<=n;i++)X=T[to[i]].d[0],Y=T[to[i]].d[1],add(rt);down(rt);
for(i=1;i<=k;ans+=pw(1.0-1.0*o.count()/n,m),i++){
for(o.reset(),j=0;j<v[i].size();j++)o|=G[v[i][j]];
for(j=0;j<v[i].size();j++)o[v[i][j]]=0;
}
printf("%.8lf",ans);
}
BZOJ1199 直接上K-D树
#include<bits/stdc++.h>
#define Max(a,b)(a<b?a=b:a)
#define Min(a,b)(a>b?a=b:a)
#define N 200200
using namespace std;char s[9];int n,m,i,o,w,O,rt,ans[N];double X,Y,R,X1,Y1,X2,Y2,A[N],B[N],r[N],A1[N],A2[N],B1[N],B2[N];
struct P{int v,id,lz,l,r;double d[2],mi[2],mx[2];}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
double sqr(double x){return x*x;}
int bt(int l,int r,int o){
O=o;int k=l+r>>1,i,u;nth_element(T+l+1,T+k+1,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mx[i]=T[k].d[i];
if(l<k)for(u=T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Min(T[k].mi[i],T[u].mi[i]),Max(T[k].mx[i],T[u].mx[i]);
if(k<r)for(u=T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Min(T[k].mi[i],T[u].mi[i]),Max(T[k].mx[i],T[u].mx[i]);
return k;
}
void add(int k){
if(X1>=T[k].mx[0]||X2<=T[k].mi[0]||Y1>=T[k].mx[1]||Y2<=T[k].mi[1]||!k)return;
if(X1<T[k].mi[0]&&T[k].mx[0]<X2&&Y1<T[k].mi[1]&&T[k].mx[1]<Y2){T[k].v++,T[k].lz++;return;}
if(X1<T[k].d[0]&&T[k].d[0]<X2&&Y1<T[k].d[1]&&T[k].d[1]<Y2)T[k].v++;add(T[k].l);add(T[k].r);
}
void cha(int k){
if(R*R<=sqr(max(max(X-T[k].mx[0],T[k].mi[0]-X),0.0))+sqr(max(max(Y-T[k].mx[1],T[k].mi[1]-Y),0.0))||!k)return;
if(R*R>=max(sqr(X-T[k].mx[0]),sqr(T[k].mi[0]-X))+max(sqr(Y-T[k].mx[1]),sqr(T[k].mi[1]-Y))){T[k].v++,T[k].lz++;return;}
if(sqr(X-T[k].d[0])+sqr(Y-T[k].d[1])<=R*R)T[k].v++;cha(T[k].l);cha(T[k].r);
}
void down(int k){
int o;
if(o=T[k].l)T[o].v+=T[k].lz,T[o].lz+=T[k].lz,down(o);
if(o=T[k].r)T[o].v+=T[k].lz,T[o].lz+=T[k].lz,down(o);
}
int main(){
for(scanf("%d%d",&m,&n);m--;)if(scanf("%s",s),s[0]=='r')o++,scanf("%lf%lf%lf%lf",&A1[o],&B1[o],&A2[o],&B2[o]);else w++,scanf("%lf%lf%lf",&A[w],&B[w],&r[w]);
for(i=1;i<=n;i++)scanf("%lf%lf",&T[i].d[0],&T[i].d[1]),T[i].id=i;
for(rt=bt(1,n,0),i=1;i<=o;i++)X1=min(A1[i],A2[i]),X2=max(A1[i],A2[i]),Y1=min(B1[i],B2[i]),Y2=max(B1[i],B2[i]),add(rt);
for(i=1;i<=w;i++)X=A[i],Y=B[i],R=r[i],cha(rt);
for(down(rt),i=1;i<=n;i++)ans[T[i].id]=T[i].v;
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}
BZOJ4533 K-D树插入、找最近和最远点
#include<bits/stdc++.h>
#define M 222222
#define inf 1e9
using namespace std;struct T{int d[2],mi[2],mv[2],l,r;}t[M];int n,m,rt,O,A,p,i,I[2];
bool cmp(T a,T b){return a.d[O]<b.d[O]||(a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1]);}
void ps(int k){
int l=t[k].l,r=t[k].r;
for(int i=0;i<2;i++){
if(l)t[k].mi[i]=min(t[k].mi[i],t[l].mi[i]),t[k].mv[i]=max(t[k].mv[i],t[l].mv[i]);
if(r)t[k].mi[i]=min(t[k].mi[i],t[r].mi[i]),t[k].mv[i]=max(t[k].mv[i],t[r].mv[i]);
}
}
int Di(T k){return max(k.mi[0]-I[0],0)+max(I[0]-k.mv[0],0)+max(k.mi[1]-I[1],0)+max(I[1]-k.mv[1],0);}
int Dv(T k){return max(I[0]-k.mi[0],k.mv[0]-I[0])+max(I[1]-k.mi[1],k.mv[1]-I[1]);}
int B(int l,int r,int o){
O=o;int md=(l+r)>>1;nth_element(t+l+1,t+md+1,t+r+1,cmp);
for(int i=0;i<2;i++)t[md].mi[i]=t[md].mv[i]=t[md].d[i];
if(l<md)t[md].l=B(l,md-1,o^1);if(r>md)t[md].r=B(md+1,r,o^1);return ps(md),md;
}
void In(int k,int o){
int i;if(I[o]<t[k].d[o])if(t[k].l)In(t[k].l,o^1);else for(t[k].l=++n,i=0;i<2;i++)t[n].mv[i]=t[n].mi[i]=t[n].d[i]=I[i];
else if(t[k].r)In(t[k].r,o^1);else for(t[k].r=++n,i=0;i<2;i++)t[n].mv[i]=t[n].mi[i]=t[n].d[i]=I[i];
ps(k);
}
void Qi(int k){
if(!k)return;
int d=abs(t[k].d[0]-I[0])+abs(t[k].d[1]-I[1]),dl=inf,dr=inf;
A=min(A,d);if(t[k].l)dl=Di(t[t[k].l]);if(t[k].r)dr=Di(t[t[k].r]);
if(dl<dr){if(dl<A)Qi(t[k].l);if(dr<A)Qi(t[k].r);
}else{if(dr<A)Qi(t[k].r);if(dl<A)Qi(t[k].l);}
}
void Qv(int k){
if(!k)return;
int d=abs(t[k].d[0]-I[0])+abs(t[k].d[1]-I[1]),dl=-inf,dr=-inf;
A=max(A,d);if(t[k].l)dl=Dv(t[t[k].l]);if(t[k].r)dr=Dv(t[t[k].r]);
if(dl>dr){if(dl>A)Qv(t[k].l);if(dr>A)Qv(t[k].r);
}else{if(dr>A)Qv(t[k].r);if(dl>A)Qv(t[k].l);}
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&t[i].d[0],&t[i].d[1]);
for(rt=B(1,n,0),scanf("%d",&m);m--;){
scanf("%d%d%d",&p,&I[0],&I[1]);if(!p)In(rt,0);
if(p==1)A=inf,Qi(rt),printf("%d\n",A);if(p==2)A=-inf,Qv(rt),printf("%d\n",A);
}
}
BZOJ4520 使用K-D树找到距离每个点最远的点，选取其中最大的k对点，对它们两两进行枚举。在没有精心构造的数据下，时间复杂度O(n^1.5+k^2lgk)
#include<bits/stdc++.h>
#define N 100010
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define inf 2147483647ll*2147483647
using namespace std;typedef long long LL;LL A,E[N];int n,k,i,j,t,e,o,O,rt,q[N];
struct W{int x,y;LL z;}p[N];bool cp(W a,W b){return a.z>b.z;}
struct P{int l,r,d[2],mi[2],mx[2];}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
LL S(int x){return 1ll*x*x;}LL D(int a,int b){return S(T[a].d[0]-T[b].d[0])+S(T[a].d[1]-T[b].d[1]);}
LL md(P k){return S(max(max(T[i].d[0]-k.mi[0],k.mx[0]-T[i].d[0]),0))+S(max(max(T[i].d[1]-k.mi[1],k.mx[1]-T[i].d[1]),0));}
int bt(int l,int r,int o){
O=o;int k=l+r>>1,i,u;nth_element(T+l+1,T+k+1,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mx[i]=T[k].d[i];
if(l<k)for(u=T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
if(k<r)for(u=T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
return k;
}
void qu(int k){
LL d=D(k,i),dl=-inf,dr=-inf;
if(d>A)A=d,o=k;if(T[k].l)dl=md(T[T[k].l]);if(T[k].r)dr=md(T[T[k].r]);
if(dl>dr){if(dl>A)qu(T[k].l);if(dr>A)qu(T[k].r);}else{if(dr>A)qu(T[k].r);if(dl>A)qu(T[k].l);}
}
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d%d",&T[i].d[0],&T[i].d[1]);
for(rt=bt(1,n,0),i=1;i<=n;i++)A=o=0,qu(rt),p[i]=W{i,o,A};
for(sort(p+1,p+n+1,cp),i=1;i<=min(k*2,n);i++)q[++t]=p[i].x,q[++t]=p[i].y;
for(sort(q+1,q+t+1),o=unique(q+1,q+t+1)-q-1,i=1;i<=o;i++)for(j=i+1;j<=o;j++)E[++e]=D(q[i],q[j]);
sort(E+1,E+e+1);printf("%lld",E[e-k+1]);
}
BZOJ2674 K-D树套权值线段树，在权值线段树上二分求K大，时间复杂度O(nlgn+mn^0.5lgn)。
#include<bits/stdc++.h>
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define N 60600
#define M 23333333
using namespace std;char s[9];
int n,m,i,l,r,O,k,x,y,z,V,id,md,rt,W,X,Y,X1,Y1,X2,Y2,t1,t2,Z[N],T[N],to[N],q1[N],q2[N],L[M],R[M],sz[M];
struct P{int l,r,z,fa,id,d[2],mi[2],mx[2];}p[N];
bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
void ins(int&k,int l,int r,int x,int z){
if(!k)k=++id;sz[k]+=z;if(l==r)return;int md=l+r>>1;
if(x<=md)ins(L[k],l,md,x,z);else ins(R[k],md+1,r,x,z);
}
void tou(int k,int rt){
ins(T[rt],1,W,p[k].z,1);
if(p[k].l)tou(p[k].l,rt);if(p[k].r)tou(p[k].r,rt);
}
int bt(int l,int r,int o,int fa){
O=o;int k=l+r>>1,i;nth_element(p+l,p+k,p+r+1,cmp);
for(i=0;i<2;i++)p[k].mi[i]=p[k].mx[i]=p[k].d[i];to[p[k].id]=k;p[k].fa=fa;
if(l<k)for(p[k].l=bt(l,k-1,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].l].mi[i]),Mx(p[k].mx[i],p[p[k].l].mx[i]);
if(k<r)for(p[k].r=bt(k+1,r,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].r].mi[i]),Mx(p[k].mx[i],p[p[k].r].mx[i]);
return tou(k,k),k;
}
void qu(int k){
if(X1>p[k].mx[0]||X2<p[k].mi[0]||Y1>p[k].mx[1]||Y2<p[k].mi[1])return;
if(X1<=p[k].mi[0]&&p[k].mx[0]<=X2&&Y1<=p[k].mi[1]&&p[k].mx[1]<=Y2){q1[++t1]=T[k];return;}
if(X1<=p[k].d[0]&&p[k].d[0]<=X2&&Y1<=p[k].d[1]&&p[k].d[1]<=Y2)q2[++t2]=k;
if(p[k].l)qu(p[k].l);if(p[k].r)qu(p[k].r);
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d%d",&p[i].d[0],&p[i].d[1],&p[i].z),p[i].id=i,Z[i]=p[i].z;
for(sort(Z+1,Z+n+1),W=unique(Z+1,Z+n+1)-Z-1,i=1;i<=n;i++)p[i].z=lower_bound(Z+1,Z+W+1,p[i].z)-Z;
for(rt=bt(1,n,0,0);m--;)
if(scanf("%s",s),s[0]=='S'){
scanf("%d%d",&x,&y);x++;y++;
for(X=to[x],z=p[X].z;X;X=p[X].fa)ins(T[X],1,W,z,-1);
for(Y=to[y];Y;Y=p[Y].fa)ins(T[Y],1,W,z,1);
for(Y=to[y],z=p[Y].z;Y;Y=p[Y].fa)ins(T[Y],1,W,z,-1);
for(X=to[x];X;X=p[X].fa)ins(T[X],1,W,z,1);
swap(p[to[x]].z,p[to[y]].z);
}else{
scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&k);t1=t2=0;
if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);qu(rt);
for(V=0,i=1;i<=t1;i++)V+=sz[q1[i]];if(V+t2<k){puts("It doesn't exist.");continue;}
for(l=1,r=W;l<r;){
md=l+r>>1;V=0;
for(i=1;i<=t1;i++)V+=sz[L[q1[i]]];
for(i=1;i<=t2;i++)if(p[q2[i]].z<=md&&p[q2[i]].z>=l)V++;
if(k<=V)for(r=md,i=1;i<=t1;i++)q1[i]=L[q1[i]];
else for(l=md+1,k-=V,i=1;i<=t1;i++)q1[i]=R[q1[i]];
}
printf("%d\n",Z[l]);
}
}
2016年4月27日 19:58
bzoj1199的程序是不是有问题啊
边界上的点不被统计进去啊
3 1
c 0.0 0.0 1.5
c 3.0 0.0 1.5
r 0.0 -1.5 3.0 1.5
1.5 0.0
您的程序输出是2