分块模拟的,为啥块长不同 WA 的点的个数不同???
块长取 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;
}