我终将成为你的倒影

题目名称检测到子串“终将成为你”，题面检测到子串“岛村”、“安达”。鉴定为百合题。

题面。

性质

$f (x) = ⌊ \frac{x + a}{b} ⌋ = ⌊ \frac{x}{b} ⌋ + ⌊ \frac{a}{b} ⌋ + [x \mod b + a \mod b \geq b]$

注意到 $1 \leq b \leq 500$ ，那么考虑枚举 $b$ 来预处理。

对于 $f (r_{1}) = f (r_{2})$ 按照 $⌊ \frac{r_{1}}{b} ⌋, ⌊ \frac{r_{2}}{b} ⌋$ 的大小分三类，可以得到 $⌊ \frac{a}{b} ⌋$ 的大小范围（都是一段区间）。

具体地：

若 $⌊ \frac{r_{1}}{b} ⌋ = ⌊ \frac{r_{2}}{b} ⌋$ 则 $r_{1} \mod b + a \mod b \geq b, r_{2} \mod b + a \mod b \geq b$ 或 $r_{1} \mod b + a \mod b < b, r_{2} \mod b + a \mod b < b$ 即 $a \mod b \geq max (b - r_{1} \mod b, b - r_{2} \mod b)$ 或 $a \mod b < min (b - r_{1} \mod b, b - r_{2} \mod b)$ 。
若 $⌊ \frac{r_{1}}{b} ⌋ = ⌊ \frac{r_{2}}{b} ⌋ + 1$ 则 $r_{1} \mod b + a \mod b < b, r_{2} \mod b + a \mod b \geq b$ 即 $a \mod b < b - r_{1} \mod b, a \mod b \geq b - r_{2} \mod b$
若 $⌊ \frac{r_{1}}{b} ⌋ + 1 = ⌊ \frac{r_{2}}{b} ⌋$ 则 $r_{1} \mod b + a \mod b \geq b, r_{2} \mod b + a \mod b < b$ 即 $a \mod b \geq b - r_{1} \mod b, a \mod b < b - r_{2} \mod b$

思路

考虑分块。

每个 $b$ 开块数个值域为 $b$ 的桶，在其上预处理差分之后可以快速计算整块，空间复杂度 $O (\frac{n}{s i z} b^{2})$ ，可以直接取 $s i z = b$ ，然后开 short。

预处理复杂度： $O (n b + \frac{n}{s i z} b^{2})$ ，处理询问复杂度： $O (\frac{n}{s i z} + s i z)$ 。

鲜花

仙台叶月向宫城志绪理表白了。

code

cpp

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
using namespace std;
const int sz=500,N=1e5+10,testB=500;
int a[N],rev[N],L[N],R[N],blocks;
short cf[N/sz+100][testB+5][testB+5];
int f(int x,int a,int b){return (x+a)/b;}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m;cin>>n>>m;
	rep(i,1,n)cin>>a[i];
	rep(i,1,n){
		int id=(i-1)/sz+1;blocks=id;
		rev[i]=id;R[id]=i;
		if(!L[id])L[id]=i;
		if(i==1)continue;
		rep(b,1,testB){
			int c=a[i]/b-a[i-1]/b;
			if(abs(c)>1)continue;
			if(c==0){
				int x=a[i]%b,y=a[i-1]%b;
				cf[id][b][0]+=1;
				cf[id][b][max(0,b-max(x,y))]-=1;
				cf[id][b][min(testB+1,b-min(x,y))]+=1;
			}else if(c==1){
				int x=a[i]%b,y=a[i-1]%b;
				if(b-y<b-x){
					cf[id][b][max(0,b-y)]+=1;
					cf[id][b][min(testB+1,b-x)]-=1;
				}
			}else{
				int x=a[i]%b,y=a[i-1]%b;
				if(b-x<b-y){
					cf[id][b][max(0,b-x)]+=1;
					cf[id][b][min(testB+1,b-y)]-=1;
				}
			}
		}
	}
	rep(i,1,blocks)rep(b,1,testB)rep(s,1,testB)cf[i][b][s]+=cf[i][b][s-1];
	int last=0;
	while(m--){
		int l,r,a,b;cin>>l>>r>>a>>b;
		l^=last;r^=last;a^=last;b^=last;
		int ans=0;
		if(rev[r]<=rev[l]+1)rep(i,l+1,r)ans+=(f(::a[i],a,b)==f(::a[i-1],a,b));
		else{
			rep(i,l+1,R[rev[l]])ans+=(f(::a[i],a,b)==f(::a[i-1],a,b));
			rep(i,L[rev[r]],r)ans+=(f(::a[i],a,b)==f(::a[i-1],a,b));
			int t=a%b;
			rep(i,rev[l]+1,rev[r]-1){
				ans+=cf[i][b][t];
			}
		}
		cout<<(last=ans)<<'\n';
	}
	return 0;
}