P3688 [ZJOI2017]树状数组

· · 题解

题目说其add和find的方向反了，即求成了后缀和；

对于询问l~r的区间和，正常是 sum[r] - sum[l - 1];

但是九条误弄成了 sum[r - 1] - sum[l - 2];(因为取模转正 所以无负数 变一下符号)

所以题目的询问即为val[r] == val[l - 1] 的概率；

设一个二元组（l,r）,记录val[l] == val[r] 的概率；

因此修改可以看作是区间修改，查询为单点查询；又因为要维护二元组

所以树套树没得跑了QAQ，发现没有区间查，标记永久化一下；

具体考虑的话，外层维护l，内层维护r。

如果以前val[l] == val[r] 相同的概率为P，对于一次操作，不会使其变化的概率为Q

则新的概率为 P Q + （1 - P） （1 - Q）；

接下来大力讨论。。。 设修改区间为 L ~ R

<1> l 在 [1,L - 1] ,r在[L,R],使其变化的概率为1 /（R - L + 1）;

<2> l 在[L,R] ,r 在[R + 1,n],使其变化的概率为 1 / (R - L + 1);

<3> l 在[L，R]，r 在[L,R] 使其变化的概率为 2 / (R - L + 1)；

~~

一种特殊情况: l == 1 发现 是 前缀和等于后缀和，（具体你看（模拟）一下就知道）

于是我们在第一维上单独开一个0点，维护前缀等于后缀的情况；

大力讨论：

<1> r < L 和 r > R 则一定会有影响；

<2> L <= r <= R 则有 1 / (R - L + 1) 的概率不会有影响；

CODE：

#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
const int N = 1e5 + 1000,mod = 998244353;
int n,T,cnt;
int rt[(N << 2) + 1000];
struct node{int ls,rs,v;} tr[N * 400];
ll ksm(ll x,ll y){ll res = 1; for(;y;y >>= 1,x = x * x % mod) if(y & 1) res = res * x % mod; return res;}
ll mul(ll p,ll q){ll res = p * q % mod; res = (res + (1 - p) * (1 - q) % mod) % mod; return (res + mod) % mod;}
void changey(int &k,int l,int r,int x,int y,ll p)
{
    if(!k){k = ++ cnt; tr[k].v = 1;}
    if(x <= l && y >= r) {tr[k].v = mul(tr[k].v,p); return;}
    int mid = (l + r) >> 1;
    if(x <=  mid) changey(tr[k].ls,l,mid,x,y,p);
    if(y > mid)   changey(tr[k].rs,mid + 1,r,x,y,p);
}
void changex(int k,int l,int r,int lx,int rx,int ly,int ry,ll p)
{
    if(lx <= l && rx >= r){changey(rt[k],1,n,ly,ry,p); return ;}
    int mid = (l + r) >> 1;
    if(lx <= mid) changex(k << 1,l,mid,lx,rx,ly,ry,p);
    if(rx > mid)  changex(k << 1 | 1,mid + 1,r,lx,rx,ly,ry,p);
}

ll asky(int k,int l,int r,int pos)
{
    if(!k) return 1;
    if(l == r) return tr[k].v;
    int mid = (l + r) >> 1;
    if(pos <= mid) return mul(tr[k].v,asky(tr[k].ls,l,mid,pos));
    else return mul(tr[k].v,asky(tr[k].rs,mid + 1,r,pos));
}

ll askx(int k,int l,int r,int posx,int posy)
{
    if(l == r) return asky(rt[k],1,n,posy);
    int mid = (l + r) >> 1;
    if(posx <= mid) return mul(askx(k << 1,l,mid,posx,posy),asky(rt[k],1,n,posy));
    else return mul(askx(k << 1 | 1,mid + 1,r,posx,posy),asky(rt[k],1,n,posy));
}

int main()
{
    n = read(); T = read();
    ll p; int opt,l,r;
    while(T --)
    {
        opt = read(); l = read(); r = read();
        if(opt == 1)
        {
            p = ksm(r - l + 1,mod - 2);
            if(l > 1) changex(1,0,n,1,l - 1,l,r,(1 - p + mod) % mod),changex(1,0,n,0,0,1,l - 1,0);
            if(r < n) changex(1,0,n,l,r,r + 1,n,(1 - p + mod) % mod),changex(1,0,n,0,0,r + 1,n,0);
            changex(1,0,n,l,r,l,r,(1 - 2ll * p + mod) % mod); changex(1,0,n,0,0,l,r,p);
        }
        else cout << askx(1,0,n,l - 1,r) << "\n";
    }
    return 0;
}