LibreOJ 2251 「ZJOI2017」树状数组

维护后缀和的话，实际得到的是 [l−1,r) 的和。
但是我们想要 [l,r] 的和。
所以问题是询问 al−1=ar 的概率。

考虑用二维线段树维护二元组 (x,y) 不相等的概率。
考虑一个修改，它会对以下三种二元组分别产生贡献： 1. (x,y)(x∉[l,r],y∈[l,r])。 2. (x,y)(x∈[l,r],y∉[l,r])。 3. (x,y)(x,y∈[l,r])。

前两种会产生 1r−l+1 的贡献，后一种会产生 2r−l+1 的贡献。

注意，询问时若 l=1，询问的是前缀和与后缀和相等的概率，需要特别注意。

然后标记永久化，注意输出的时候把概率取反。

代码：

#include <cstdio>
#include <vector>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w ? x = -x : x;
}

const int N = 1e5;
const long long mod = 998244353;
int n,m;
inline long long fpow(long long a,long long b)
{
    long long ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = ret * a % mod),a = a * a % mod;
    return ret;
}
inline long long merge(long long a,long long b)
{
    return (1 - a + mod) * b % mod + (1 - b + mod) * a % mod;
}
struct segnode
{
    long long val;
    int ls,rs;
} seg[(N << 9) + 10];
struct node
{
    int rt;
    int ls,rs;
} tree[(N << 2) + 10];
int rt,rt1;
void update(int l,int r,long long k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    if(l <= tl && tr <= r)
    {
        seg[p].val = merge(seg[p].val,k);
        return ;
    }
    int mid = tl + tr >> 1;
    if(l <= mid)
        update(l,r,k,seg[p].ls,tl,mid);
    if(r > mid)
        update(l,r,k,seg[p].rs,mid + 1,tr);
}
long long query(int x,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return seg[p].val;
    int mid = tl + tr >> 1;
    return merge(seg[p].val,x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr));
}
void update(int x1,int y1,int x2,int y2,long long k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    if(x1 <= tl && tr <= y1)
    {
        update(x2,y2,k,tree[p].rt,1,n);
        return ;
    }
    int mid = tl + tr >> 1;
    if(x1 <= mid)
        update(x1,y1,x2,y2,k,tree[p].ls,tl,mid);
    if(y1 > mid)
        update(x1,y1,x2,y2,k,tree[p].rs,mid + 1,tr);
}
long long query(int x,int y,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return query(y,tree[p].rt,1,n);
    int mid = tl + tr >> 1;
    return merge(query(y,tree[p].rt,1,n),x <= mid ? query(x,y,tree[p].ls,tl,mid) : query(x,y,tree[p].rs,mid + 1,tr));
}
vector<int> qry[3];
int main()
{
    read(n),read(m);
    int op,l,r,cnt = 0;
    for(register int i = 1;i <= m;++i)
    {
        read(op),read(l),read(r);
        qry[0].push_back(op),qry[1].push_back(l),qry[2].push_back(r);
        if(op == 2)
            ++cnt;
    }
    if(!cnt)
        return 0;
    for(register int i = 0;i < m;++i)
    {
        op = qry[0][i],l = qry[1][i],r = qry[2][i];
        if(op == 1)
        {
            long long inv = fpow(r - l + 1,mod - 2);
            if(l > 1)
                update(1,l - 1,l,r,inv,rt,1,n),update(1,l - 1,1,rt1,1,n);
            if(r < n)
                update(l,r,r + 1,n,inv,rt,1,n),update(r + 1,n,1,rt1,1,n);
            update(l,r,l,r,2 * inv,rt,1,n),update(l,r,(r - l) * inv % mod,rt1,1,n);
        }
        else
            printf("%lld\n",merge(1,l == 1 ? query(r,rt1,1,n) : query(l - 1,r,rt,1,n)));
    }
}