P3372 【模板】线段树 1

使用最基本的线段树即可。

遇到的坑

  • 内存要开够，考虑直接采用 N << 2
  • build 和 add 的时候都要 push_up
  • add 和 query 的时候都要 push_down
  • r - l == 1 不要写成 l - r == 1

P3373 【模板】线段树 2

将 tag 的使用顺序规定为先乘后加，

那么先加 a，后乘 b 等效于先乘 b，后加 a * b。

这一规则意味着：

  • push_down 时，先应用乘标记，再运用加标记
  • push_down 时，乘标记应用时会影响子代加标记
  • 当前节点已有加标记时，乘操作会影响加标记

由于时间宽裕，考虑使用 struct Z 处理模数。

遇到的坑

  • 乘法的懒标记要初始化为 1

P2023 [AHOI2009]维护序列

和上一题一模一样，只需修改读入顺序。

P1047 校门外的树

除了暴力做法之外，考虑使用区间修改线段树。

遇到的坑

  • 区间修改懒标记要初始化为数据值域之外的数，且应用懒标记时要特判。

P1531 I Hate It

使用线段树存储最大值即可。

遇到的坑

  • 除以二不是 >> 2！

P5057 [CQOI2006]简单题

虽然一眼树状数组差分，但也可以使用线段树模板，模 2 即可。

P4588 [TJOI2018]数学计算

用线段树维护区间乘积、单点修改。

遇到的坑

  • 不要忘记 build()
  • 线段树依赖全局 n 和 b[N]，不要遗忘为这些赋值

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define fori(n) for (ll i = 0; i < n; i++)
#define forj(n) for (ll j = 0; j < n; j++)
#define rofi(n) for (ll i = n - 1; i >= 0; i--)
#define rofj(n) for (ll j = n - 1; j >= 0; j--)
const ll N = 100004;
ll n, b[N];
ll T, Q, M, op, m;

// assume -M <= x < 2M
int norm(int x) {
  if (x < 0) {
    x += M;
  }
  if (x >= M) {
    x -= M;
  }
  return x;
}
template <class T> T power(T a, ll b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}
struct Z {
  int x;
  Z(int x = 0) : x(norm(x)) {}
  Z(ll x) : x(norm(x % M)) {}
  int val() const { return x; }
  Z operator-() const { return Z(norm(M - x)); }
  Z inv() const {
    assert(x != 0);
    return power(*this, M - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = (ll)(x)*rhs.x % M;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = norm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = norm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend std::istream &operator>>(std::istream &is, Z &a) {
    ll v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const Z &a) {
    return os << a.val();
  }
};

Z a[N << 2];

inline ll mid(ll l, ll r) { return l + (r - l) / 2; }
inline void build(ll l = 0, ll r = n, ll p = 1) {
  if (r - l == 1) {
    a[p] = b[l];
  } else {
    ll m = mid(l, r);
    build(l, m, p << 1);
    build(m, r, p << 1 | 1);
    a[p] = a[p << 1] * a[p << 1 | 1];
  }
}
inline void set(ll q, ll b, ll l = 0, ll r = n, ll p = 1) {
  if (r - l == 1) {
    if (q == l) {
      a[p] = b;
    }
  } else {
    ll m = mid(l, r);
    if (q < m) {
      set(q, b, l, m, p << 1);
    } else {
      set(q, b, m, r, p << 1 | 1);
    }
    a[p] = a[p << 1] * a[p << 1 | 1];
  }
}
inline Z query(ll lq, ll rq, ll l = 0, ll r = n, ll p = 1) {
  Z f = 1;
  if (lq <= l && rq >= r) {
    f = a[p];
  } else {
    ll m = mid(l, r);
    if (lq < m) {
      f *= query(lq, rq, l, m, p << 1);
    }
    if (rq > m) {
      f *= query(lq, rq, m, r, p << 1 | 1);
    }
  }
  return f;
}

void work(ll i) {
  std::cin >> op >> m;
  if (op == 1) {
    set(i, m);
  } else {
    set(m - 1, 1);
  }
  Z f = query(0, i + 1);
  std::cout << f << '\n';
}

void solve() {
  std::cin >> Q >> M;
  n = Q;
  fori(Q) b[i] = 1;
  build();
  fori(Q) work(i);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> T;
  fori(T) solve();
  return 0;
}