首页 > 代码库 > 【BZOJ2989】数列 kd-tree

【BZOJ2989】数列 kd-tree

2024-10-17 12:31:39   212人阅读

【BZOJ2989】数列

Description

给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。
2种操作（k都是正整数）：
1.Modify x k：将第x个数的值修改为k。
2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要
考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为
同样的数值，按多次统计）

Input

第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数，代表初始数列。
第3--q+2行每行一个操作。

Output

对于每次询问操作，输出一个非负整数表示答案

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

HINT

N<=60000 修改操作数<=40000 询问<=50000 Max{a[i]}含修改<=100000

题解：新技能：旋转坐标系。就是将一个斜着的正方形变成横着的，只需要将所有点（x,y）变成（x+y，y-x）即可。

然后就变成了查询所有满足一下条件的点：l<=x<=r，l<=y<=r，加入时间<=询问时间。直接上三维kd-tree就好了。

本机实测一个点8s+然而提交上去5s就A了是什么鬼~

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define D1 ((D+1)%3)#define D2 ((D+2)%3)#define rep for(int i=0;i<=2;i++)using namespace std;const int maxn=100010;struct kd{	int v[3],sm[3],sn[3],siz,ls,rs;	kd (){}	int & operator [] (int x)	{return v[x];}	kd (int a,int b,int c)	{v[0]=sm[0]=sn[0]=a,v[1]=sm[1]=sn[1]=b,v[2]=sm[2]=sn[2]=c,siz=1,ls=rs=0;}};kd t[maxn];int n,m,D,tot,ans,root,cnt;int qx[maxn],qk[maxn],X[maxn],Y[maxn],Z[maxn],head[maxn],rm[3],rn[3];bool cmp(kd a,kd b){	return (a[D]==b[D])?((a[D1]==b[D1])?(a[D2]<b[D2]):(a[D1]<b[D1])):(a[D]<b[D]);}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}void pushup(int x,int y){	t[x].siz+=t[y].siz;	rep t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);}int build(int l,int r,int d){	if(l>r)	return 0;	D=d;	int mid=l+r>>1;	nth_element(t+l,t+mid,t+r+1,cmp);	t[mid].ls=build(l,mid-1,(d+1)%3),t[mid].rs=build(mid+1,r,(d+1)%3);	if(t[mid].ls)	pushup(mid,t[mid].ls);	if(t[mid].rs)	pushup(mid,t[mid].rs);	return mid;}int getmin(int x){	int ret=0;	rep	ret|=(t[x].sm[i]<rn[i]||t[x].sn[i]>rm[i]);	return !ret;}int getmax(int x){	int ret=1;	rep ret&=(t[x].sm[i]<=rm[i]&&t[x].sn[i]>=rn[i]);	return ret;}int check(int x){	int ret=1;	rep ret&=(t[x].v[i]<=rm[i]&&t[x].v[i]>=rn[i]);	return ret;}void query(int x){	if(!x||!getmin(x))	return ;	if(getmax(x))	{		ans+=t[x].siz;		return ;	}	if(check(x))	ans++;	query(t[x].ls),query(t[x].rs);}char str[10];int main(){	n=rd(),m=rd();	int i,a,b;	for(i=1;i<=n;i++)	a=i,b=rd(),X[i]=a+b,Y[i]=b-a,Z[i]=0,head[i]=i;	for(tot=n,i=1;i<=m;i++)	{		scanf("%s",str);		if(str[0]==‘M‘)	a=rd(),b=rd(),X[++tot]=a+b,Y[tot]=b-a,Z[tot]=i,head[a]=tot;		else	qx[i]=head[rd()],qk[i]=rd();	}	for(i=1;i<=tot;i++)	t[i]=kd(X[i],Y[i],Z[i]);	root=build(1,tot,0);	for(i=1;i<=m;i++)	{		if(qx[i])		{			rm[0]=X[qx[i]]+qk[i],rn[0]=X[qx[i]]-qk[i];			rm[1]=Y[qx[i]]+qk[i],rn[1]=Y[qx[i]]-qk[i];			rm[2]=i,rn[2]=0;			ans=0,query(root),printf("%d\n",ans);		}	}	return 0;}

【BZOJ2989】数列 kd-tree


联系
我们