题面 kawa

容易发现 $n$ 行 $n$ 列的面包卷从最下面一行开始可以划分成一个 $n+(n-1)+(n-1)+(n-2)+(n-2)+...+1+1$ 的形式，一共有 $2n-1$ 个面包块。将这些面包块编号，每 $4$ 个一循环，第一和第三个分别是区间正着和倒着加等差数列，第二和第四个是单点加等差数列。

区间加等差数列的部分考虑做两次前缀和。用正着的情况举例。第一次将 $l$ 加一，$r+1$ 减一，然后做一次前缀和，完成区间加一。第二次前缀和将 $r+1$ 减去区间长度，消去其对后续位置的影响。正着加和倒着加分开做。

始末位置和实现细节见代码。

跑得没 spq 快

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int 
#define DU double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define rep(i,x,n) for(int i=(x);i<=(n);i++)
#define nep(i,x,n) for(int i=(x);i>=(n);i--)
using namespace std;
const int N=2e5+10;
ll n,k,a[N],s[N],ssl[N],ssr[N],ssl2[N],ssr2[N];
inline void getans(ll x,ll y,ll now){
	if(x>k) return ;
	if(y%4==1){
		ll l=y/4+1,r=min(l+k-x,n-l+1);
		s[l]+=x-1,s[r+1]-=x-1;
		ssl[l]++,ssl[r+1]--,ssl2[r+1]-=r-l+1;
	}
	if(y%4==2){
		ll l=x,r=min(k,x+now-1),pos=n-(y/4);
		a[pos]+=(l+r)*(r-l+1)/2;
	}
	if(y%4==3){
		ll r=n-y/4-1,l=max(r-(k-x),y/4+1);
		s[l]+=x-1,s[r+1]-=x-1;
		ssr[r]++,ssr[l-1]--,ssr2[l-1]-=r-l+1;
	}
	if(y%4==0){
		ll l=x,r=min(k,x+now-1),pos=y/4;
		a[pos]+=(l+r)*(r-l+1)/2;
	}
	getans(x+now,y+1,now-(y&1));
}
int main(){
	scanf("%lld%lld",&n,&k);
	getans(1,1,n);
	rep(i,1,n) s[i]+=s[i-1];

	rep(i,1,n) ssl[i]+=ssl[i-1];
	rep(i,1,n) ssl[i]=ssl[i]+ssl2[i];
	rep(i,1,n) ssl[i]+=ssl[i-1];

	nep(i,n,1) ssr[i]+=ssr[i+1];
	nep(i,n,1) ssr[i]=ssr[i]+ssr2[i];
	nep(i,n,1) ssr[i]+=ssr[i+1];

	rep(i,1,n) printf("%lld ",a[i]+s[i]+ssl[i]+ssr[i]);puts("");
	return 0;
}

题解

首先考虑每一圈都填满的情况。

容易发现，最下面一行是递增的等差数列，最上面一行是递减的等差数列。两者相加后是一个定值。先把算出来，那么对于当前被修改的列，都统一加上了这个定值。 之后考虑还有两个竖向的等差数列没加上去，这个可以通过等差数列求和公式计算出来。把它加到两侧。

这一过程可以使用差分数组先打标记，最后统一做前缀和维护出来。这部分的复杂度是O(n)的。

之后考虑还有一圈没填满的。这一圈就直接暴力沿着位置转圈即可。这部分复杂度也是O(n)的。

综合上面两部分就可以做完本题。

spq的闹腾代码

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
long long k,kk,n,nn;
long long ans[N];
long long a[N];
long long s[N];
int cnt=0;
long long res=0;
int main(){
	scanf("%lld",&n);
	nn=n;
	scanf("%lld",&k);
	cnt=1;
	while(k>=4*nn-4&&nn>1){
		k-=4*nn-4;
		a[nn/2]+=res*2+3*nn-1;
		ans[n-cnt+1]=(res+nn+res+2*nn-1)*(nn-2)/2;
		res+=4*nn-4;
		ans[cnt]=(2*res-nn+3)*(nn-2)/2;
		nn-=2;
		cnt++;
	}
	if(nn==1&&k==1){
		a[0]+=n*n;
		k=0;
	}
	if(k>0){
		for(int i=cnt;i<=n-cnt+1;i++){
			res++;
			ans[i]+=res;
			k--;
			if(k==0) break;
		}
		if(k>0){
			for(int i=1;i<=nn-2;i++){
				res++;
				ans[n-cnt+1]+=res;
				k--;
				if(k==0) break;
			}
		}
		if(k>0){
			for(int i=n-cnt+1;i>=cnt;i--){
				res++;
				ans[i]+=res;
				k--;
				if(k==0) break;
			}
		}
		if(k>0){
			for(int i=1;i<=nn-2;i++){
				res++;
				ans[cnt]+=res;
				k--;
				if(k==0) break;
			}
		}
	}
	for(int i=n/2;i>=0;i--){
		s[i]=s[i+1]+a[i];
	}
	for(int i=1;i<=n/2;i++){
		cout<<s[n/2+1-i]+ans[i]<<" ";
	}
	for(int i=n/2+1;i<=n;i++){
		cout<<s[n/2+1-(n+1-i)]+ans[i]<<" ";
	}
	return 0;
}