自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 22:59:46，当前版本为作者最后更新于2024-06-19 18:49:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题实际上就是维护一个平面直角坐标系，每次加一个点，求与一个点曼哈顿距离 $\le k$ 的点数。

trick：$(x,y)$ 转化为 $(x+y,-x+y)$，转化为一个点为中心，边长为 $2k$ 的正方形包含的点数。

二维线段树即可，即外层区间线段树，内层动态开点权值线段树。

int n,m,a[N],rt[V<<2];
#define mid (l+r>>1)
struct SGT1 {
	int num,ls[V<<7],rs[V<<7],val[V<<7],cnt;
	void upd(int &id,int l,int r,int x) {if(!id) id=++num; val[id]++; if(l==r) return; x<=mid?upd(ls[id],l,mid,x):upd(rs[id],mid+1,r,x);}
	int qry(int id,int l,int r,int L,int R) {return !id?0:L<=l&&r<=R?val[id]:(L<=mid?qry(ls[id],l,mid,L,R):0)+(R>mid?qry(rs[id],mid+1,r,L,R):0);}
}S;
struct SGT2 {
	#define ls (id<<1)
	#define rs (id<<1|1)
	void upd(int id,int l,int r,int x,int y) {S.upd(rt[id],-V,V,y); if(l==r) return; x<=mid?upd(ls,l,mid,x,y):upd(rs,mid+1,r,x,y);}
	int qry(int id,int l,int r,int L,int R,int _L,int _R) {return L<=l&&r<=R?S.qry(rt[id],-V,V,_L,_R):(L<=mid?qry(ls,l,mid,L,R,_L,_R):0)+(R>mid?qry(rs,mid+1,r,L,R,_L,_R):0);}
}T;
void QwQ() {
	n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd(),T.upd(1,1,V,a[i]+i,a[i]-i);
	for(int x,y;m--;) {
		string s; cin>>s,x=rd(),y=rd();
		if(s=="Modify") a[x]=y,T.upd(1,1,V,y+x,y-x);
		else wr(T.qry(1,1,V,a[x]+x-y,a[x]+x+y,a[x]-x-y,a[x]-x+y),"\n"); 
	}
}