题解：B3646 数列前缀和 3

UnionRE · 2026-08-07 19:47:25 · 题解

Part 0 前言

如何发明 Sqrt Tree？？

Part 1 怎么做？

设运算符为 \odot（当然这里是矩阵乘法）。

考虑使用由乃救爷爷的做法（当然也是区间静态半群信息查询那道题的第一篇题解），很容易写出分块：

分 \sqrt n 个块，记录：

然后查询就很好做了。l,r 不在一个块那就直接做，O(1)。在一个块就是 O(\sqrt n) 暴力查。

期望复杂度 O(1)。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1145141;
const int maxn=1e6+10,masq=sqrt(maxn)+10;
struct sqr{
    int a[3][3],ns;
    bool ie;
    sqr(){ie=1;memset(a,0,sizeof(a));}
    sqr(int ns_){ns=ns_;ie=0;memset(a,0,sizeof(a));}
    sqr(int ns_,bool _){ns=ns_;ie=_;}
    friend sqr multiply(sqr A,sqr B){
        int tn=A.ns;
        sqr C(tn);
        for(int i=0;i<tn;i++){
            for(int j=0;j<tn;j++){
                for(int k=0;k<tn;k++){
                    C.a[i][j]+=1ll*A.a[i][k]*B.a[k][j]%mod;
                    C.a[i][j]%=mod;
                }
            }
        } 
        return C;
    }
    friend sqr operator*(sqr A,sqr B){
        if(A.ie&&B.ie)return sqr();
        else if(A.ie&&!B.ie)return B;
        else if(!A.ie&&B.ie)return A;
        else return multiply(A,B);
    }
    friend sqr merge(sqr A,sqr B){return A*B;}
    int xorv(){
        int ans=0;
        for(int i=0;i<ns;i++){
            for(int j=0;j<ns;j++)ans^=a[i][j];
        }
        return ans;
    }
};
int n,k,B;
sqr a[maxn],f[masq][masq],b[masq],suf[masq][masq],pre[masq][masq];
int bel(int x){return (x-1)/B+1;}//block id
int L(int bid){return (bid-1)*B+1;}
int R(int bid){return min(bid*B,n);}
void build(){
    B=sqrt(n);
    for(int i=1;i<=n;i++)b[bel(i)]=merge(b[bel(i)],a[i]);
    for(int i=1;i<=bel(n);i++){
        f[i][i]=b[i];
        for(int j=i+1;j<=bel(n);j++)f[i][j]=merge(f[i][j-1],b[j]);
    }
    for(int i=1;i<=bel(n);i++){
        for(int j=L(i);j<=R(i);j++)pre[i][j-L(i)+1]=merge(pre[i][j-L(i)],a[j]);
        for(int j=R(i);j>=L(i);j--)suf[i][j-L(i)+1]=merge(a[j],suf[i][j-L(i)+2]);
    }
}
sqr query(int l,int r){
    if(bel(l)==bel(r)){
        sqr ans=sqr();
        for(int i=l;i<=r;i++)ans=ans*a[i];
        return ans;
    }
    else return merge(merge(suf[bel(l)][l-L(bel(l))+1],f[bel(l)+1][bel(r)-1]),pre[bel(r)][r-L(bel(r))+1]);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int q;
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        sqr M(k,0);
        for(int x=0;x<k;x++){
            for(int y=0;y<k;y++){
                cin>>M.a[x][y];
            }
        }
        a[i]=M;
    }
    build();
    int ans=0;
    while(q--){
        int l,r;
        cin>>l>>r;
        ans^=query(l,r).xorv();
    }
    cout<<ans;
    return 0;
}

:::

Part 2 我随便卡！

是的，如你所见，让 l,r 在同一个块即可。

Part 3 我乱搞，你卡不了！

我们把第一个块的块长随便搞一下，让数组有个偏移，这样 l=k\sqrt n+1,r=(k+1)\sqrt n-1 就不在一个块了。

还可以乱搞块长，反正是想怎么搞就怎么搞。

Part 4 我在打 CF，这样还是会被 hack！

我们使出绝招：

O(n\log \log n)- 期望 O(1) 最坏 O(\log \log n) 区间半群信息查询

考虑进行类似递归分块操作，可以做到 \log \log n 层的诡异东西。然后就是期望 O(1) 最坏 O(\log \log n) 的 RMQ。空间 O(n\log\log n)。

注意这个与递归分块不同，递归分块整块不是 O(1) 的。而这个是，所以递归 B 层复杂度为 O(B+\sqrt[2^B]{n})。

:::info[复杂度分析]{open} 设每层每块长度为 f(Q)。Q 为当前层的长度。

考虑两层的情形：