首页 > 其他分享 >P10633

P10633

时间:2024-10-02 19:45:19浏览次数:6  
标签:int mid 310000 P10633 add cdq

#include<bits/stdc++.h>
using namespace std;
int n,m,t,p,b[310000],tr[310000],d[310000],e[310000],g[310000],kk;
char ch[100];
struct sth {
	int x,y,z,w,ans;
} a[310000],c[310000];
void add(int x,int y,int op) {
	b[++p]=a[++t].x=x;
	a[t].y=y;
	a[t].z=t;
	a[t].w=op;
}
void add(int x,int k) {
	while(x<=p) {
		tr[x]+=k;
		x+=x&(-x);
	}
}
int qy(int x) {
	int s=0;
	while(x) {
		s+=tr[x];
		x-=x&(-x);
	}
	return s;
}
void cdq(int l,int r) {
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int i=l,j=mid+1,cnt=0,tt=0;
	for(; j<=r; j++) {
		while(i<=mid&&a[i].y<=a[j].y) {
			if(a[i].w==0)add(a[i].x,1),d[++cnt]=a[i].x;
			c[++tt]=a[i++];
		}
		if(a[j].w!=0)a[j].ans+=qy(a[j].x);
		c[++tt]=a[j];
	}
	for(int i=1; i<=cnt; i++)add(d[i],-1);
	while(i<=mid)c[++tt]=a[i++];
	tt=0;
	for(int i=l; i<=r; i++)a[i]=c[++tt];
}
bool cmp(sth a,sth b) {
	return a.z<b.z;
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		scanf("%d",&e[i]);
		add(i-e[i],i+e[i],0);
	}
	int cnt=0;
	for(int i=1; i<=m; i++) {
		int x,y;
		scanf("%s",ch+1);
		scanf("%d%d",&x,&y);
		if(ch[1]=='Q') {
			add(x-e[x]+y,e[x]+x+y,1);
			g[++cnt]=t;
			add(x-e[x]-y-1,e[x]+x-y-1,1);
			add(x-e[x]+y,e[x]+x-y-1,-1);
			add(x-e[x]-y-1,e[x]+x+y,-1);
		} else {
			e[x]=y;
			add(x-e[x],e[x]+x,0);
		}
	}
	sort(b+1,b+1+p);
	kk=unique(b+1,b+1+p)-b-1;
	for(int i=1; i<=t; i++)a[i].x=lower_bound(b+1,b+1+kk,a[i].x)-b;
	cdq(1,t);
	sort(a+1,a+1+t,cmp);
	for(int i=1; i<=cnt; i++)printf("%d\n",a[g[i]].ans+a[g[i]+1].ans-a[g[i]+2].ans-a[g[i]+3].ans);
	return 0;
}

标签:int,mid,310000,P10633,add,cdq
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18445020

相关文章

  • P10633 BZOJ2989 数列/BZOJ4170 极光 题解
    题目传送门前置知识CDQ分治|权值树状数组及应用|曼哈顿距离与切比雪夫距离的相互转化解法增加一维为时间戳,那么操作\(1\)等价于单点加。曼哈顿距离直接跑CDQ分治,貌似不太可做,考虑转化为切比雪夫距离。原曼哈顿坐标系中的点\((x_{1},y_{1}),(x_{2},y_{2})\)间的......