线段树
[NOI2017]整数（https://www.luogu.org/problemnew/show/P3822）
思路：
线段树，每位存1/0，加法时将a中二进制表示下为1的位取出，分别加入序列，寻找x位左边最靠近x的0，对这个位置到x位进行区间反转，进行进位操作，线段树分别维护一段区间最右的0和1的位置，打懒标记，此时时间复杂度O(n*log(1e7)*log(a))
考虑优化，上述做法将a的二进制表示拆开，若想降低这个log(a)的复杂度，选择暴力将需要修改的这32位数取出，与a直接计算，将计算后的结果放回序列，进位只需在本次处理的最高位进一次。暴力取数的复杂度为log(a)+log(1e7),从而将复杂度变为一个log，可过。
KD-Tree
The Closest M Points (http://acm.hdu.edu.cn/showproblem.php?pid=4347)
题目大意：
给出 nn 个 KK 维的点，又给出 tt 个查询， 每个查询也给出一个 KK 维的点，要求查询 nn 个点中距离这个点最近的 MM 个点。
代码：
#include<bits/stdc++.h> using namespace std; int idx,k,n,m,q; struct node{ int x[5]; bool operator < (const node &u) const{ return x[idx]<u.x[idx]; } }P[50004]; int sz[100004]; typedef pair<int,node> PDN; priority_queue<PDN> que; node p[100004]; inline void build(int i,int l,int r,int dep){ if(l>r) return; int mid=l+r>>1; idx=dep%k; sz[i]=r-l; sz[i<<1]=sz[i<<1|1]=-1; nth_element(P+l,P+mid,P+r+1); p[i]=P[mid]; build(i<<1,l,mid-1,dep+1); build(i<<1|1,mid+1,r,dep+1); } inline void query(int i,int m,int dep,node a){ if(sz[i]==-1) return; PDN tmp=PDN(0,p[i]); for(int j=0;j<k;j++){ tmp.first+=(tmp.second.x[j]-a.x[j])*(tmp.second.x[j]-a.x[j]); } int lc=i<<1,rc=i<<1|1,dim=dep%k,flag=0; if(a.x[dim]>=p[i].x[dim]) swap(lc,rc); if(sz[lc]!=-1) query(lc,m,dep+1,a); if(que.size()<m) que.push(tmp),flag=1; else{ if(tmp.first<que.top().first) que.pop(),que.push(tmp); if((a.x[dim]-p[i].x[dim])*(a.x[dim]-p[i].x[dim])<que.top().first) flag=1; } if(sz[rc]!=-1&&flag) query(rc,m,dep+1,a); } int main(){ while(scanf("%d%d",&n,&k)!=EOF){ memset(p,0,sizeof(p)); memset(sz,0,sizeof(sz)); for(int i=0;i<n;i++){ for(int j=0;j<k;j++){ scanf("%d",&P[i].x[j]); } } build(1,0,n-1,0); scanf("%d",&q); while(q--){ node now; for(int i=0;i<k;i++) scanf("%d",&now.x[i]); scanf("%d",&m); int t=0; query(1,m,0,now); node pp[21]; while(!que.empty()){ pp[++t]=que.top().second; que.pop(); } printf("the closest %d points are: ",t); for(int i=m;i;i--){ for(int j=0;j<k-1;j++) printf("%d ",pp[i].x[j]); printf("%d",pp[i].x[k-1]); printf(" "); } } } }