为啥块长除以2就过了
查看原帖
为啥块长除以2就过了
347664
菲斯斯夫斯基楼主2024/9/15 10:18

分块模拟的,为啥块长不同 WA 的点的个数不同???

块长取 n\sqrt n 会 WA 两个点

是因为一些细节问题吗?

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,ans;
int a[N],id[N],l[N],r[N],chk[N],s[N];
int ask(int k)
{
	return chk[id[k]]?a[l[id[k]]]+k-l[id[k]]:a[k];
}
int find(int x,int y)
{
	if(y<ask(x))
	{
		int num=x;
		while(id[x]==id[num-1]&&ask(num-1)>=y)
			num--;
		if(id[num-1]==id[x]&&ask(num-1)<y)
			return num;
		int now=id[x];
		while(now>1&&(a[l[now-1]]>=y||y-ask(l[now-1])+1<x-l[now-1]+1))now--;
		for(int i=r[now];i>=1;i--)
			if(ask(i)<y&&y-ask(i)+1>=x-i+1)return i+1;
		return 1;
	}
	else
	{
		int num=x;
		while(id[x]==id[num+1]&&ask(num+1)<=y)
			num--;
		if(id[num+1]==id[x]&&ask(num+1)>y)
			return num;
		int now=id[x];
		while(now<id[n]&&(a[l[now+1]]<=y||ask(l[now+1])-y+1<l[now+1]-x+1))now++;
		for(int i=l[now];i<=n;i++)
			if(ask(i)>y&&ask(i)-y+1>=i-x+1)return i-1;
		return n;
	}
}
void change(int L,int R,int x,int y)
{
	if(id[L]==id[R])
	{
		for(int i=l[id[L]];i<=r[id[L]];i++)
			a[i]=ask(i);
		chk[id[L]]=0;
		for(int i=L;i<=R;i++)
			ans+=abs(ask(i)-(x+i-L)),s[id[i]]+=-ask(i)+(x+i-L),a[i]=x+i-L;
		return ;
	}
	for(int i=id[L]+1;i<id[R];i++)
		ans+=abs(s[i]-(x+l[i]-L+x+r[i]-L)*(r[i]-l[i]+1)/2),chk[i]=1,s[i]=(x+l[i]-L+x+r[i]-L)*(r[i]-l[i]+1)/2,a[l[i]]=x+l[i]-L;
	for(int i=l[id[L]];i<=r[id[L]];i++)
		a[i]=ask(i);
	chk[id[L]]=0;
	for(int i=L;i<=r[id[L]];i++)
		ans+=abs(ask(i)-(x+i-L)),s[id[i]]+=-ask(i)+(x+i-L),a[i]=x+i-L;
	for(int i=l[id[R]];i<=r[id[R]];i++)
		a[i]=ask(i);
	chk[id[R]]=0;
	for(int i=l[id[R]];i<=R;i++)
		ans+=abs(ask(i)-(x+i-L)),s[id[i]]+=-ask(i)+(x+i-L),a[i]=x+i-L;
}
signed main()
{
	cin>>n;
	const int len=max(sqrt(n)/2,1.0);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		id[i]=(i-1)/len+1,s[id[i]]+=a[i];
		if(!l[id[i]])l[id[i]]=i;
		r[id[i]]=i;
	}
	cin>>m;
	while(m--)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		if(ask(x)==y)continue;
		int k=find(x,y);
		if(ask(x)>y)change(k,x,y-(x-k),y);
		else change(x,k,y,y+(k-x));
	}
	cout<<ans;
	return 0;
}
2024/9/15 10:18
加载中...