Submission #68384376

---

Source Code Expand

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ostream>
#include <set>
using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll N = 2e5 + 5, SQRT = 400;

template <ll MOD>
struct modular {
    ll x;
    modular() : x(0) {}
    modular(ll _x) {
        x = _x;
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return;
    }
    modular operator+(const modular &b) const { return modular(x + b.x); }
    modular operator*(const modular &b) const { return modular(x * b.x); }
    modular operator+=(const modular &b) { return *this = *this + b; }
    modular operator*=(const modular &b) { return *this = *this * b; }
};

using mll = modular<(ll)998244353>;

mll prod[N], inv_prod[N];
mll C(ll n, ll m) {
    if (m < 0 || m > n) {
        return 0;
    }
    return prod[n] * inv_prod[m] * inv_prod[n - m];
}
mll qp(mll a, ll b) {
    mll ret = 1;
    for (; b; b >>= 1, a *= a) {
        if (b & 1) {
            ret *= a;
        }
    }
    return ret;
}
mll inv(mll x) { return qp(x, 998244353 - 2); }

ll n;

mll ways(ll n, ll m, bool beg, bool ed) {
    // n 中取 m 个，头/尾是否要选。
    if (n == 1) {
        if (beg != ed) {
            return 0;
        }
        else {
            if ((m == 1 && beg) || (m == 0 && !beg)) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
    return C(n - m - 1, m - beg - ed);
}

struct blk_stat {
    mll cnt[2][2];
    blk_stat operator*(const blk_stat &b) const {
        blk_stat ret;
        for (ll i = 0; i < 2; i++) {
            for (ll j = 0; j < 2; j++) {
                ret.cnt[i][j] = ((cnt[i][1] + cnt[i][0]) * b.cnt[0][j] +
                                 cnt[i][0] * b.cnt[1][j]);
            }
        }
        return ret;
    }
    blk_stat(const blk_stat &b) { memcpy(cnt, b.cnt, sizeof(cnt)); }
    blk_stat(blk_stat &&) = default;
    blk_stat &operator=(const blk_stat &) = default;
    blk_stat() { memset(cnt, 0, sizeof(cnt)); }
};

blk_stat ways_cnt[N]; // 对于没有限制的情况，维护这个。

struct segment {
    ll l, r;
    ll nxt_blk;
    blk_stat st; // 第一位/最后一位是咖啡/茶的方案数。
    ll num_coffee;
    ll sum_coffee;
    ll size() { return r - l + 1; }
    void get_stat() {
        if (sum_coffee == -1) {
            st = ways_cnt[size() - 1];
            return;
        }
        // 根据 num_coffee 和 size() 求出 st
        for (ll i = 0; i < 2; i++) {
            for (ll j = 0; j < 2; j++) {
                st.cnt[i][j] = ways(size(), num_coffee, i, j);
            }
        }
    }
};

ll blk_len;
segment seg[N];
ll i2blk[N];
pair<ll, ll> rng[N / SQRT];

bool cur_val[N];
set<ll> s;

void recal(ll blk) {
    ll blk_beg = rng[blk].first, blk_end = rng[blk].second;
    bool flag = true;
    for (ll i = blk_end - 1; i >= blk_beg; i--) {
        auto &cur_seg = seg[i], &nxt_seg = seg[seg[i].r + 1];
        if (cur_val[i]) {
            if (flag) {
                cur_seg.nxt_blk = cur_seg.r + 1;
                assert(cur_seg.r + 1 >= blk_end);
                cur_seg.get_stat();
                flag = false;
            }
            else {
                cur_seg.nxt_blk = nxt_seg.nxt_blk;
                cur_seg.get_stat();
                cur_seg.st = cur_seg.st * nxt_seg.st;
            }
        }
    }
    return;
}

void cut(ll l, ll pos, ll lval) {
    auto sum_coffee_prev = seg[l].sum_coffee - seg[l].num_coffee;
    ll rval = seg[l].sum_coffee, r = seg[l].r;
    seg[l].sum_coffee = lval;
    seg[l].num_coffee = lval - sum_coffee_prev;
    seg[l].r = pos;
    seg[l].l = l;
    if (pos == r) {
        seg[r + 1].num_coffee = seg[r + 1].sum_coffee - lval;
        recal(i2blk[l]);
        recal(i2blk[(r + 1)]);
        return;
    }
    seg[pos + 1].l = pos + 1;
    seg[pos + 1].r = r;
    seg[pos + 1].sum_coffee = rval;
    seg[pos + 1].num_coffee = rval - lval;
    // 最后一段固定个数为 -1，没有限制.
    s.insert(pos + 1);
    cur_val[pos + 1] = true;
    recal(i2blk[l]);
    if (i2blk[(pos + 1)] != i2blk[l]) recal(i2blk[(pos + 1)]);
}

void merge(ll posl, ll posr) {
    auto sum_coffee_prev = seg[posl].sum_coffee - seg[posl].num_coffee;
    seg[posl].l = posl;
    seg[posl].r = seg[posr].r;
    seg[posl].sum_coffee = seg[posr].sum_coffee;
    seg[posl].num_coffee = seg[posl].sum_coffee - sum_coffee_prev;
    s.erase(posr);
    cur_val[posr] = false;
    recal(posl / blk_len);
}

void modify(ll pos, ll val) {
    auto it = s.lower_bound(pos);
    if (it == s.end() || *it > pos) {
        it--;
    }
    if (val == -1) {
        //assert(*it == pos);
        if (s.find(pos + 1) == s.end()) {
            return;
        }
        auto r = s.lower_bound(pos + 1);
        merge(*it, *r);
    }
    else {
        cut(*it, pos, val);
    }
}

mll query() {
    blk_stat cnt;
    cnt.cnt[0][0] = 1;
    ll cur = 0;
    while (cur < n) {
        cnt = cnt * seg[cur].st;
        cur = seg[cur].nxt_blk;
    }
    return cnt.cnt[0][0] + cnt.cnt[0][1];
}

ll q;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q;
    prod[0] = 1;
    inv_prod[0] = 1;
    for (ll i = 1; i <= n; i++) {
        prod[i] = prod[i - 1] * i;
        inv_prod[i] = inv(prod[i]);
    }
    ways_cnt[0].cnt[0][0] = 1;
    ways_cnt[1].cnt[0][0] = 1;
    ways_cnt[1].cnt[1][1] = 1;
    blk_len = sqrt(n);
    i2blk[0] = 0 / blk_len;
    i2blk[1] = 1 / blk_len;
    for (ll i = 2; i <= n; i++) {
        ways_cnt[i] = ways_cnt[i - 1] * ways_cnt[1];
        i2blk[i] = i / blk_len;
    }
    seg[0].l = 0;
    seg[0].r = n;
    seg[0].num_coffee = -1;
    seg[0].sum_coffee = -1;
    cur_val[0] = true;
    s.insert(0);
    for (ll i = 0; i <= (n - 1) / blk_len; i++) {
        rng[i].first = i * blk_len;
        rng[i].second = min((i + 1) * blk_len, n);
        recal(i);
    }
    while (q--) {
        ll x, y;
        cin >> x >> y;
        x--;
        modify(x, y);
        cout << query().x << "\n";
    }
    cout << flush;
    return 0;
}

/*
n 选 i 个不相邻的数就是 C(n-i+1,i)
就相当于是这几段拼起来。
有几种操作，切开一个序列，合并两个序列。
每次还要计算答案。呃呃。
拼起来的时候还需要注意。
如果上一个的最后一个是咖啡，那么第一个就只能是茶。
否则茶和咖啡都可。将两种方案记作 c_i,t_i
c_i = c_{i-1} * C(len-k-1,i-1) + t_{i-1} * C(len-k+1-1,i-1)
t_i = c_{i-1} * C(len-k-1,i) + t_{i-1} * C(len-k+1-1,i)
哦，是不是可以从后往前和从前往后扫一遍。然后再填出中间的情况。
那你就需要连着后面一起更新。
考虑线段树分治。首先切和合并显然是满足交换律的。
但是这道题难点不在于切和合并，在于如何高校的切。
考虑分块。
感觉可做。
*/

Submission Info

Judge Result