题解：P3688 [ZJOI2017] 树状数组

· · 题解

观察或打表得，题目给出的 FIND 函数返回的是后缀和。于是我们要求出的就是 a_{l-1}=a_r 的概率。特别的，若 l=0 则求的是 S_{[1,r]} = S_{[r,n]} 的概率。后者容易维护，下面考虑如何维护前者。

思考操作对答案的影响。我们建一个二维矩阵 P_{i,j}，表示 a_i=a_j 的概率。修改区间 [l,r] 内的一个数，会使：

不难发现我们要维护矩阵修改（概率计算式满足交换律和结合律，所以可以当作乘法），单点查询操作。于是使用二维线段树，树上区间完全落在修改区间内时，进入第二维进行类似操作。查询时要统计所有包含该点的矩阵。

第一次写二维线段树，代码很丑，但是思路是清晰的。


/*

       2025.11.17

 * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int MAXN=100005,mod=998244353;
int n,m,cnt,t;
struct node{int l,r,w,son;}tree[MAXN*405];
int neo(){tree[++cnt]=node{0,0,0,0};return cnt;}
int gt(ll x){return (x%mod+mod)%mod;}
int merge(int x,int y){return gt(1ll*x*(1-y)+1ll*(1-x)*y);}
void add2(int x,int l,int r,int ll,int rr,int t){
    if(l>=ll&&r<=rr){
        tree[x].w=merge(tree[x].w,t);
        return ;
    }
    int mid=(l+r)>>1;
    if(ll<=mid){
        if(!tree[x].l)tree[x].l=neo();
        add2(tree[x].l,l,mid,ll,rr,t);
    }
    if(rr>mid){
        if(!tree[x].r)tree[x].r=neo();
        add2(tree[x].r,mid+1,r,ll,rr,t);
    }
}
void add(int x,int l,int r,int ll,int rr,int _l,int _r,int t){
    if(ll>rr||_l>_r)return ;
    if(l>=ll&&r<=rr){
        if(!tree[x].son)tree[x].son=neo();
        add2(tree[x].son,l,n,_l,_r,t);
        return ;
    }
    int mid=(l+r)>>1;
    if(ll<=mid){
        if(!tree[x].l)tree[x].l=neo();
        add(tree[x].l,l,mid,ll,rr,_l,_r,t);
    }
    if(rr>mid){
        if(!tree[x].r)tree[x].r=neo();
        add(tree[x].r,mid+1,r,ll,rr,_l,_r,t);
    }
}
int ask2(int x,int l,int r){
    if(x==0)return 0;
    if(l==r)return tree[x].w;
    int mid=(l+r)>>1;
    if(t<=mid)return merge(tree[x].w,ask2(tree[x].l,l,mid));
    return merge(tree[x].w,ask2(tree[x].r,mid+1,r));
}
int ask(int x,int l,int r,int tt){
    if(x==0)return 0;
    int ans=ask2(tree[x].son,l,n);
    if(l==r)return ans;
    int mid=(l+r)>>1;
    if(tt<=mid)return merge(ans,ask(tree[x].l,l,mid,tt));
    else return merge(ans,ask(tree[x].r,mid+1,r,tt));
}
int pw(ll base,int t){
    ll ans=1;
    while(t){
        if(t&1)ans=ans*base%mod;
        base=base*base%mod,t>>=1;
    }
    return ans;
}
struct FS{
    struct FFS{int l,r,w,d;}tree[MAXN*4];
    void build(int x,int l,int r){
        tree[x].l=l,tree[x].r=r;tree[x].w=0,tree[x].d=0;
        if(tree[x].l==tree[x].r)return ;
        int mid=(l+r)>>1;
        build(x*2,l,mid);build(x*2+1,mid+1,r);
    }
    void down(int x){
        tree[x*2].w=merge(tree[x*2].w,tree[x].d);
        tree[x*2+1].w=merge(tree[x*2+1].w,tree[x].d);
        tree[x*2].d=merge(tree[x*2].d,tree[x].d);
        tree[x*2+1].d=merge(tree[x*2+1].d,tree[x].d);
        tree[x].d=0;
    }
    void add(int x,int l,int r,int t){
        if(l>r)return ;
        if(tree[x].l>=l&&tree[x].r<=r){tree[x].w=merge(tree[x].w,t),tree[x].d=merge(tree[x].d,t);return ;}
        if(tree[x].d)down(x);
        int mid=(tree[x].l+tree[x].r)>>1;
        if(l<=mid)add(x*2,l,r,t);
        if(r>mid)add(x*2+1,l,r,t);
    }
    int ask(int x,int l){
        if(tree[x].l==tree[x].r)return tree[x].w;
        if(tree[x].d)down(x);
        int mid=(tree[x].l+tree[x].r)>>1;
        if(l<=mid)return ask(x*2,l);
        return ask(x*2+1,l);
    }
}tr;
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m;neo();tr.build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r;cin>>op>>l>>r;
        if(op==1){
            add(1,1,n,1,l-1,l,r,pw(r-l+1,mod-2));
            if(l!=r)add(1,1,n,l,r,l,r,2ll*pw(r-l+1,mod-2)%mod);
            add(1,1,n,l,r,r+1,n,pw(r-l+1,mod-2));
            tr.add(1,l,r,1ll*(r-l)*pw(r-l+1,mod-2)%mod);
            tr.add(1,1,l-1,1);tr.add(1,r+1,n,1);
        }
        else{
            if(l==1)cout<<gt(1-tr.ask(1,r))<<"\n";
            else t=r,cout<<gt(1-ask(1,1,n,l-1))<<"\n";
        }
    }
    return 0;
}