题解：P11660 终将成为你

· · 题解

首先将 a 改成 a \bmod b，无影响。

分块，对于块内每个 b 预处理答案。对于每个 b，一个点对在至多两个 a 的区间有贡献，差分即可。

查询正常查询。

以上内容，管理员说写了滚木打回了。

令 g,z 分别为 \lfloor\frac{A_{i-1}}{b}\rfloor 和 \lfloor\frac{A_{i}}{b}\rfloor，r_{1},r_{2} 分别为 A_{i-1} \bmod b 和 A_{i} \bmod b。

如果 g 和 z 相差大于 1，将永远错过。

如果 g-z=1，会在 [b-r1,b-r2) 相遇。

如果 z-g=1，同理。

如果 g=z，假设 r1>r2，会在 [b-r1,b-r2) 离别。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,B=512;
int A[N],c[N/B+5][125500],L[N/B+5],R[N/B+5],belong[N];
struct node{
    int l,r,a,b;
}q[N];
inline int id(int x,int y){
    return x*(x-1)/2+y;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,num,ans=0;cin>>n>>m;num=(n+B-1)/B;
    for (int i=1;i<=n;i++) cin>>A[i];
    for (int bel=1;bel<=num;bel++){
        L[bel]=(bel-1)*B+1,R[bel]=min(n,bel*B);
        for (int j=L[bel];j<=R[bel];j++) belong[j]=bel;
        for (int j=1;j<=500;j++){
            for (int i=L[bel]+1;i<=R[bel];i++){
                int g=A[i-1]/j,z=A[i]/j,r1=A[i-1]%j,r2=A[i]%j;
                if (abs(g-z)>1) continue;
                if (g==z){
                    if (r1>r2) swap(r1,r2);
                    c[bel][id(j,0)]++;
                    if (r2) c[bel][id(j,j-r2)]--;
                    if (r1) c[bel][id(j,j-r1)]++;
                }
                if (g<z){
                    if (r1<=r2) continue;
                    c[bel][id(j,j-r1)]++;
                    if (r2) c[bel][id(j,j-r2)]--;
                }
                if (g>z){
                    if (r1>=r2) continue;
                    c[bel][id(j,j-r2)]++;
                    if (r1) c[bel][id(j,j-r1)]--;
                }
            }
            for (int i=1;i<j;i++) c[bel][id(j,i)]+=c[bel][id(j,i-1)];
        } 
    }
    for (int i=1;i<=m;i++){
        int l,r,a,b;cin>>l>>r>>a>>b;
        l^=ans,r^=ans,a^=ans,b^=ans;
        a%=b,ans=0;
        int bl=belong[l],br=belong[r];
        if (bl==br){
            int lst=(A[l]+a)/b;
            for (int j=l+1;j<=r;j++){
                int k=(A[j]+a)/b;
                if (k==lst) ans++;
                lst=k;
            }
        }else{
            int lst=(A[l]+a)/b;
            for (int j=l+1;j<=R[bl];j++){
                int k=(A[j]+a)/b;
                if (k==lst) ans++;
                lst=k;
            }
            for (int j=bl+1;j<br;j++){
                if (lst==(A[L[j]]+a)/b) ans++;
                ans+=c[j][id(b,a)];
                lst=(A[R[j]]+a)/b;
            }
            for (int j=L[br];j<=r;j++){
                int k=(A[j]+a)/b;
                if (k==lst) ans++;
                lst=k;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

不敢插管理员说我写了滚木后面，插最后了。

好麻烦啊！