题解：P3688 [ZJOI2017] 树状数组

· · 题解

妙妙数据结构题！

Solution

1

树状数组倒过来变成什么？求后缀和哇！

那么 qry(r)-qry(l-1)= suf_r - suf_{l-1}，而 suf_r-suf_{l-1}\equiv \sum_{i=l-1}^{r-1}a_i \bmod 2。其中 suf_i 表示后缀和。

所以其实还是对区间求和。由此发现本题转化为：

2

题目让 a_i 对 2 取模，实在是大有用处哇。

对于操作 1 给出的 [L,R]，它们对操作 2 的 l,r 贡献大致分为三种情况：（记 len=R-L+1，P 为 a_l=a_r 成立的概率）

记上述“不变概率”为 Q。

显然有 P'=PQ+(1-P)(1-Q)。

3

挖掘上式性质。

P''=P'K+(1-P')(1-K)\\=(PQ+(1-P)(1-Q))K+(1-(PQ+(1-P)(1-Q)))(1-K)\\=4PQK-2PK-2QK-2PQ+P+Q+K

在最终化简的式子中，P,Q,K 是轮换对称的。

也即是说，上述变换满足结合律。也即是说，P 先和 Q 变换还是先和 K 变换，得到的结果都是一样的。

4

结合律的性质说明可以做标记永久化。而且又是区间修改单点查询，很符合线段树套线段树的使用场景。

外层线段树维护 l，内层维护对应的 r，线段树套线段树，标记永久化。然后就是板子了。

Code

实现细节：非常非常卡空间。不能开 long long，所以在快速幂等运算中要注意乘上 1ll。

感觉放在树套树中，是写得蛮清新了。

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define ll int
#define LL long long

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
bool Mst;

const int maxn = 1e5 + 5;
const ll mod = 998244353;

int n, m;

inline ll pw(ll x, int p = mod - 2){
    ll res = 1ll; x %= mod;
    while(p){ if(p & 1) res = (LL)1ll * res * x % mod; p >>= 1; x = (LL)1ll * x * x % mod; }
    return res;
}

inline void Mop(ll &p, ll q){
    int tmp = (LL)1ll * p % mod * q % mod;
    int P = (LL)1ll * (1ll - p + mod) % mod, Q = (LL)1ll * (1ll - q + mod) % mod;
    p = (LL)1ll * (1ll * tmp + 1ll * P * Q % mod) % mod;
}

struct tree{
    int ch[2]; ll p;
    tree(){ p = 1ll; }
}t[maxn * 400]; int tot;

#define ls t[x].ch[0]
#define rs t[x].ch[1]

inline void updtr(int &x, int l, int r, int L, int R, ll p){
    if(L > R) return;
    if(!x) x = ++tot;
    if(l >= L and r <= R) return Mop(t[x].p, p), void();
    int mid = l + r >> 1; 
    if(L <= mid) updtr(ls, l, mid, L, R, p);
    if(R > mid) updtr(rs, mid + 1, r, L, R, p);
}
inline void qryp(int x, int l, int r, int p, ll &val){
    if(!x) return; Mop(val, t[x].p);
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) qryp(ls, l, mid, p, val);
    else qryp(rs, mid + 1, r, p, val);
}

#undef ls
#undef rs

int tr[maxn << 2];

#define ls (x << 1)
#define rs (x << 1 | 1)

inline void updtr(int x, int l, int r, int L, int R, int ql, int qr, ll p){
    if(L > R) return;
    if(l >= L and r <= R) return updtr(tr[x], 1, n, ql, qr, p), void();
    int mid = l + r >> 1;
    if(L <= mid) updtr(ls, l, mid, L, R, ql, qr, p);
    if(R > mid) updtr(rs, mid + 1, r, L, R, ql, qr, p);
}
inline void qryp(int x, int l, int r, int L, int R, ll &val){
    qryp(tr[x], 1, n, R, val);
    if(l == r) return;
    int mid = l + r >> 1; 
    if(L <= mid) qryp(ls, l, mid, L, R, val);
    else qryp(rs, mid + 1, r, L, R, val);
}

#undef ls
#undef rs

bool Med;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    fprintf(stderr, "%.2lfMB\n", abs(&Mst - &Med) / 1024. / 1024.);

    cin >> n >> m; int T0 = ++tot;

    while(m--){
        int op, l, r; cin >> op >> l >> r;
        int len = r - l + 1;
        if(op == 1){
            updtr(1, 1, n, l, r, l, r, (LL)1ll * (len - 2) * pw(len) % mod);
            updtr(1, 1, n, l, r, r + 1, n, (LL)1ll * (len - 1) * pw(len) % mod);
            updtr(1, 1, n, 1, l - 1, l, r, (LL)1ll * (len - 1) * pw(len) % mod);

            updtr(T0, 1, n, l, r, pw(len));
            updtr(T0, 1, n, 1, l - 1, 0);
            updtr(T0, 1, n, r + 1, n, 0);
        } else{
            if(l == 1){
                ll ans = 1ll; qryp(T0, 1, n, r, ans);
                cout << ans << '\n';
            } else{
                ll ans = 1ll; qryp(1, 1, n, l - 1, r, ans);
                cout << ans << '\n';
            }
        }
    }
    return 0;
}