- 二维 \(KD-Tree\) 模板题.
- \(KD-Tree\) 虽然在更新和查询的方式上类似于线段树,但其本身定义是类似于用 \(splay/fhq\ treap\) 维护区间的二叉搜索树,没有加点删点,建树时将它建成平衡的就好了.
- 这使得一个 \(node\) 的左子树管辖 \([l,mid-1]\) ,右子树管辖 \([mid+1,r]\) , \(mid\) 处的信息存在自己处,不要写混.
- 对于 \(k\) 维的 \(KD-Tree\) ,它每次更新/查询的时间复杂度是 \(O(n^{1-\frac 1 k})\) .所以本题总时间复杂度为 \(O(m\sqrt n)\).
- 在常数优化上有一个小技巧:若答案 \(ans\) 对 \(2^k\) 取模,可以直接输出 $ans&(P-1) $.本题 \(536870912=2^{29}\).
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define inf 0x7f7f7f7f
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=5e4+10;
const int P=536870912;
inline int add(int a,int b)
{
return (a + b) ;
}
inline int mul(int a,int b)
{
return a * b ;
}
int n,m,Tp;
struct node{
int tp;//维护的维度
int mi[2],ma[2];//[x/y]的最小,最大值
int v[2];//坐标
int ls,rs;
int tagadd,tagmul;
int val,len,sum;
bool operator < (const node& rhs) const
{
return v[Tp]<rhs.v[Tp];//当前比较的维度,全局变量储存.
}
node()
{
ls=rs=0;
tagadd=0;
tagmul=1;
sum=0;
}
}Tree[MAXN];
#define root Tree[o]
#define lson Tree[Tree[o].ls]
#define rson Tree[Tree[o].rs]
void pushup(int o)
{
root.mi[0]=min(root.v[0],min(lson.mi[0],rson.mi[0]));
root.mi[1]=min(root.v[1],min(lson.mi[1],rson.mi[1]));
root.ma[0]=max(root.v[0],max(lson.ma[0],rson.ma[0]));
root.ma[1]=max(root.v[1],max(lson.ma[1],rson.ma[1]));
}
int BuildTree(int l,int r,int tp)
{
Tp=tp;
int mid=(l+r)>>1;
int o=mid;
nth_element(Tree+l,Tree+mid,Tree+r+1);
root.tp=tp;
root.len=r-l+1;
if(l<mid)
root.ls=BuildTree(l,mid-1,(tp+1)%2);
if(r>mid)
root.rs=BuildTree(mid+1,r,(tp+1)%2);
pushup(o);
return o;
}
void Modifiy_mul(int o,int mulv)
{
root.val=mul(root.val,mulv);
root.tagmul=mul(root.tagmul,mulv);
root.tagadd=mul(root.tagadd,mulv);
root.sum=mul(root.sum,mulv);
}
void Modifiy_add(int o,int addv)
{
root.val=add(root.val,addv);
root.tagadd=add(root.tagadd,addv);
root.sum=add(root.sum,mul(root.len,addv));
}
void pushdown(int o)
{
if(root.tagmul!=1)
{
Modifiy_mul(root.ls,root.tagmul);
Modifiy_mul(root.rs,root.tagmul);
root.tagmul=1;
}
if(root.tagadd!=0)
{
Modifiy_add(root.ls,root.tagadd);
Modifiy_add(root.rs,root.tagadd);
root.tagadd=0;
}
}
void update(int o,int L,int R,int mulv,int addv)//修改第Tp维
{
if(L>root.ma[Tp] || R<root.mi[Tp])
return;
if(L<=root.mi[Tp] && root.ma[Tp]<=R)
{
Modifiy_mul(o,mulv);
Modifiy_add(o,addv);
return;
}
pushdown(o);
if(L<=root.v[Tp] && root.v[Tp]<=R)
{
root.val=mul(root.val,mulv);
root.val=add(root.val,addv);
}
pushdown(o);
update(root.ls,L,R,mulv,addv);
update(root.rs,L,R,mulv,addv);
root.sum=add(lson.sum,rson.sum);
root.sum=add(root.sum,root.val);
}
int query(int o,int L,int R)
{
if(L>root.ma[Tp] || R<root.mi[Tp])
return 0;
if(L<=root.mi[Tp] && root.ma[Tp]<=R)
return root.sum;
pushdown(o);
int res=0;
if(root.ls)
res=add(res,query(root.ls,L,R));
if(root.rs)
res=add(res,query(root.rs,L,R));
if(L<=root.v[Tp] && root.v[Tp]<=R)
res=add(res,root.val);
return res;
}
int rt;
void init()
{
Tree[0].ma[0]=Tree[0].ma[1]=-inf;
Tree[0].mi[0]=Tree[0].mi[1]=inf;
for(int i=1;i<=n;++i)
{
Tree[i].v[0]=i;
Tree[i].v[1]=read();
}
rt=BuildTree(1,n,0);
}
int main()
{
n=read(),m=read();
init();
while(m--)
{
int op=read();
int l,r,x,y;
if(op==0)
{
l=read(),r=read(),x=read(),y=read();
Tp=0;
update(rt,l,r,x,y);
}
else if(op==1)
{
l=read(),r=read(),x=read(),y=read();
Tp=1;
update(rt,l,r,x,y);
}
else if(op==2)
{
l=read(),r=read();
Tp=0;
printf("%d\n",query(rt,l,r)&(P-1));
}
else
{
l=read(),r=read();
Tp=1;
printf("%d\n",query(rt,l,r)&(P-1));
}
}
return 0;
}
