ZJOI2017 树状数组

题目:

  漆黑的晚上,九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的OI 比赛经历。那是一道基础的树状数组题。
  给出一个长度为 的数组 ,初始值都为 ,接下来进行 次操作,操作有两种:

  ,表示将 变成
  ,表示询问

  尽管那个时候的可怜非常的 simple,但是她还是发现这题可以用树状数组做。当时非常 young 的她写了如下的算法:

  其中 表示数字 最低的非0二进制位,例如 。进行第一类操作的时候就调用 ,第二类操作的时候答案就是
  如果你对树状数组比较熟悉,不难发现可怜把树状数组写错了: 变化的方向反了。因此这个程序在最终测试时华丽的爆 0 了。
  然而奇怪的是,在当时,这个程序通过了出题人给出的大样例——这也是可怜没有进行对拍的原因。
  现在,可怜想要算一下,这个程序回答对每一个询问的概率是多少,这样她就可以再次的感受到自己是一个多么非的人了。然而时间已经过去了很多年,即使是可怜也没有办法完全回忆起当时的大样例。幸运的是,她回忆起了大部分内容,唯一遗忘的是每一次第一类操作的 的值,因此她假定这次操作的 是在 范围内等概率随机的。
  具体来说,可怜给出了一个长度为 的数组 ,初始为 ,接下来进行了 次操作:

  ,表示在区间 中等概率选取一个 并执行
  ,表示询问执行 得到的结果是正确的概率是多少。

思路:

  观察伪代码发现,可怜给出的 所求的是区间 的异或和(先不考虑 的情况)。所以答案不同的概率也就是 的概率。
  对于每一次查询,考虑每一个在它之前的修改对它的贡献(我记录的是不正确的概率 )。先设 (即两件事恰有一个不成立的概率),如果操作区间(长度为 )同时覆盖了 ,那么 ,如果只覆盖了其中一个 ,如果没有覆盖显然是没有影响的。
  注意到 这个运算是满足结合率的,所以可以把贡献全部扔到二维点对上,每次就是一个矩形乘、单点查的操作,二维线段树可以 解决。
   的情况就只用记录一下整个序列的异或和,特判一下就行了。

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int MOD = 998244353, N = 1e5 + 5;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

bool cur1;

namespace Math {
    void exgcd(int a, int b, int &x, int &y) {
        if(!b) {x = 1; y = 0; return;}
        exgcd(b, a % b, y, x); y -= a / b * x;
    }
    int inv(int a) {
        int x, y;
        exgcd(a, MOD, x, y);
        return (x % MOD + MOD) % MOD;
    }
}

int calc(int p, int d) {
    return ((ll) (1 - p + MOD) * d + (ll) p * (1 - d + MOD)) % MOD;
}


namespace Segment1 {
    const int SIZE = N * 20 * 20;
    int seg[SIZE], ls[SIZE], rs[SIZE], tot;
    struct Node {
        int rt;
        void upd(int l, int r, int x, int &o, int L, int R) {
            if(!o) o = ++tot;
            if(l == L && r == R) {seg[o] = calc(seg[o], x); return;}
            int m = (L + R) >> 1;
            if(r <= m) upd(l, r, x, ls[o], L, m);
            else if(l > m) upd(l, r, x, rs[o], m + 1, R);
            else upd(l, m, x, ls[o], L, m), upd(m + 1, r, x, rs[o], m + 1, R);
        }
        int qry(int x, int o, int L, int R) {
            if(!o) return 0;
            if(L == R) return seg[o];
            int m = (L + R) >> 1;
            if(x <= m) return calc(seg[o], qry(x, ls[o], L, m));
            else return calc(seg[o], qry(x, rs[o], m + 1, R));
        }
    };
}

namespace Segment2 {
    Segment1::Node seg[N << 2];
    void upd(int x1, int x2, int y1, int y2, int v, int o, int X1, int X2, int Y1, int Y2) {
        if(x1 > x2 || y1 > y2) return;
        if(x1 == X1 && x2 == X2) {
            seg[o].upd(y1, y2, v, seg[o].rt, Y1, Y2);
            return;
        }
        int m = (X1 + X2) >> 1;
        if(x2 <= m) upd(x1, x2, y1, y2, v, o << 1, X1, m, Y1, Y2);
        else if(x1 > m) upd(x1, x2, y1, y2, v, o << 1 | 1, m + 1, X2, Y1, Y2);
        else {
            upd(x1, m, y1, y2, v, o << 1, X1, m, Y1, Y2);
            upd(m + 1, x2, y1, y2, v, o << 1 | 1, m + 1, X2, Y1, Y2);
        }
    }
    int qry(int x, int y, int o, int X1, int X2, int Y1, int Y2) {
        if(X1 == X2) return seg[o].qry(y, seg[o].rt, Y1, Y2);
        int m = (X1 + X2) >> 1;
        if(x <= m) return calc(seg[o].qry(y, seg[o].rt, Y1, Y2), qry(x, y, o << 1, X1, m, Y1, Y2));
        else return calc(seg[o].qry(y, seg[o].rt, Y1, Y2), qry(x, y, o << 1 | 1, m + 1, X2, Y1, Y2));
    }
}
using namespace Segment2;

bool cur2;

int main() {
    int n, m;
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(bit);
    rd(n); rd(m);
    int cnt = 0;
    rep(i, 1, m) {
        int f, a, b;
        rd(f); rd(a); rd(b);
        if(f == 1) {
            cnt++;
            int p = Math::inv(b - a + 1);
            upd(a, b, a, b, p * 2 % MOD, 1, 0, n, 0, n);
            upd(0, a - 1, a, b, p, 1, 0, n, 0, n);
            upd(b + 1, n, a, b, p, 1, 0, n, 0, n);
            upd(a, b, 0, a - 1, p, 1, 0, n, 0, n);
            upd(a, b, b + 1, n, p, 1, 0, n, 0, n);
        }
        else {
            int p = (1 - qry(a - 1, b, 1, 0, n, 0, n) + MOD) % MOD;
            if(a == 1 && (cnt & 1)) p = (1 - p + MOD) % MOD;
            printf("%d\n", p);
        }
    }
    return 0;
}