分块 https://loj.ac/p/6278
  • 板块学术版
  • 楼主Molmin
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/3/16 20:39
  • 上次更新2023/11/5 01:59:05
查看原帖
分块 https://loj.ac/p/6278
478528
Molmin楼主2021/3/16 20:39

哪错?

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int maxn=5e4+5;
int lazy[maxn],a[maxn],n,op,l,r,c,B;
vector<int> ve[501];
inline int get(int x)
{
	return (x+B-1)/B;
}
inline void reset(int x)
{
	ve[x].clear();
	for(int i=(x-1)*B+1;i<=min(x*B,n);i++)
	{
		ve[x].push_back(a[i]);
	}
	sort(ve[x].begin(),ve[x].end());
}
inline void update(int l,int r,int c)
{
	for(int i=l;i<=min(get(l)*B,r);i++)
	{
		a[i]+=c;
	}
	reset(get(l));
	if(get(l)!=get(r))
	{
		for(int i=(get(r)-1)+1;i<=r;i++)
		{
			a[i]+=c;
		}
		reset(get(r));
	}
	for(int i=get(l)+1;i<=get(r)-1;i++)
	{
		lazy[i]+=c;
	}
}
inline int query(int l,int r,int c)
{
	int res=0;
	for(int i=l;i<=min(r,B*get(l));i++)
	{
		if(a[i]+lazy[get(l)]<c)
		{
			res++;
		}
	}
	if(get(l)!=get(r))
	{
		for(int i=(get(r)-1)*B+1;i<=r;i++)
		{
			if(a[i]+lazy[get(r)]<c)
			{
				res++;
			}
		}
	}
	for(int i=get(l)+1;i<=get(r)-1;i++)
	{
		int x=c-lazy[i];
		res+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();
	}
	return res;
}
int main()
{
	n=read();
	B=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	for(int i=1;i<=n;i++)
	{
		ve[get(i)].push_back(a[i]);
	}
	for(int i=1;i<=get(n);i++)
	{
		sort(ve[i].begin(),ve[i].end());
	}
	int T=n;
	while(T--)
	{
		op=read();
		l=read();
		r=read();
		c=read();
		if(op==0)//修改 
		{
			update(l,r,c);
		}
		else
		{
			write(query(l,r,c*c));
			puts("");
		}
	}
}
2021/3/16 20:39
加载中...