求助大佬,分块,WAall
查看原帖
求助大佬,分块,WAall
1234924
lsd110504lsd楼主2025/1/30 09:50
#include<bits/stdc++.h>
using namespace std;
int n,q;
const int N=1e6+10;
int a[N],tag[N],tl[N],tr[N],shit[N];
vector<int> v[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}inline void build()
{
	int B=sqrt(n);
	for(int k=1;k<=(n%B==0?n/B:n/B+1);k++)
	{
		for(int i=(k-1)*B+1;i<=min(k*B,n);i++)
		{
			tag[i]=k;
			tl[i]=(k-1)*B+1;
			tr[i]=min(k*B,n);
		}
	}
	return ;
}
inline void add_on(int x,int y,int k){
	int B=sqrt(n);
	if(tag[x]==tag[y]){
		for(int i=x;i<=y;i++)
		{
			a[i]+=k;
		}
		v[tag[x]].resize(0);
		for(int i=tl[x];i<=tr[x];i++)
		{
			v[tag[x]].push_back(a[i]);
		}
		sort(v[tag[x]].begin(),v[tag[x]].end());
		return ;
	}
	else{
		for(int i=tag[x]+1;i<=tag[y]-1;i++)
		{
			shit[i]+=k;
		}
		for(int i=x;i<=tr[x];i++ )
		{
			a[i]+=k;
		}
		v[tag[x]].resize(0);
		for(int i=tl[x];i<=tr[x];i++)
		{
			v[tag[x]].push_back(a[i]);
		}
		sort(v[tag[x]].begin(),v[tag[x]].end());		
		for(int i=tl[y];i<=y;i++)
		{
			a[i]+=k;
		}
		v[tag[y]].resize(0);
		for(int i=tl[y];i<=tr[y];i++)
		{
			v[tag[y]].push_back(a[i]);
		}
		sort(v[tag[y]].begin(),v[tag[y]].end());		
		
		return ;
	} 
	return ;
}
inline void find_out(int l,int r,int c)
{
	int ans=0;
	if(tag[l]==tag[r])
	{
		for(int i=l;i<=r;i++)
		{
			if(a[i]+shit[tag[i]]>=c)
					ans++;
		}
		cout<<ans<<endl;
		return ;
	}
	else{
		for(int i=l;i<=tr[l];i++){
			if(a[i]+shit[tag[l]]>=c)
					ans++;
		}
		for(int i=tl[r];i<=r;i++){
			if(a[i]+shit[tag[r]]>=c)
				ans++;
		}
		for(int i=tag[l]+1;i<=tag[r]-1;i++)
		{
			for(int j=0;j<v[i].size();j++)
			{
				if(v[i][j]+shit[i]>=c)
				{
					ans+=v[i].size()-j;
					goto qq;
				}
			}
			qq:
			;
		}
		cout<<ans<<endl;
		return ;
	}
	return ;
}
int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build();
	for(int i=1;i<=q;i++)
	{
		char c;
		c=getchar();
		if(c=='M')
		{
			int l=read(),r=read(),w=read();
			add_on(l,r,w);
		}
		else
		{
			int l=read(),r=read(),c=read();
			find_out(l,r,c);
		}
	}
	return 0;
}
2025/1/30 09:50
加载中...