11/7
18:30
OI

CSP模拟赛104 T3 最大值 题解

我们有一个这样的式子

E(x) = \sum_{i} P(i \leq x)

证明:

E(x) = i P(i) = \sum_{i} iP(x=i)

= \sum_{i} i (P(x \geq i) – P(x \leq i+1))

由期望线性性,E = \sum_i E(max=i).

考虑组合意义,可以得到:

P(x \leq \max_{i=l}^r y_i)

= 1- \prod_{i=l}^r (1-P(x \leq y_i))

我们考虑如果x不存在于y_i中,那么P不会产生新的值,所以枚举所有y_ix,求解答案即可

把上面式子后面\prod部分取出来,记作q,考虑维护q

y_i从大到小排序,那么插入一个新的y_i,只会让P一次性增大,可以简单维护.考虑同一个位置只有\min可以对答案产生贡献,还要删掉旧的y.用vector维护每个位置排序后的点.

q = q \frac{P_{new}}{P_{old}}

对于期望计算式子里\sum,因为不存在的值不影响P的结果,乘上就行了

如果是单次询问就做完了,对于多次询问,把询问排序,一个点可以覆盖一个区间的询问.把询问离散成点建立线段树,区间乘,维护区间q和即可,不是本题难点.

#include <bits/stdc++.h>

using std::cerr;
using std::endl;

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

typedef long long ll;
const int N = 2e5 + 233, P = 1e9 + 7;

inline int fpow(int x, int y) {
  int ret = 1;
  for ( ; y; y >>= 1, x = (ll)x * x % P)
    if (y & 1) ret = (ll)ret * x % P;
  return ret;
}

int n, m, q, ans, left[N], right[N];

struct Stone {
  int x, y, p;
} st[N];
int cnt;

struct Query {
  int l, r;
} qu[N];

std::vector<int> vec[N];
int not_pick[N];

bool operator<(const Stone &a, const Stone &b) {
  return a.y < b.y;
}

bool operator<(const Query &a, const Query &b) {
  return a.l < b.l;
}

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

int val[N * 4], tag[N * 4];

inline void pushup(int p) {
  val[p] = (val[ls(p)] + val[rs(p)]) % P;
}

inline void push(int p, int v) {
  val[p] = (ll)val[p] * v % P;
  tag[p] = (ll)tag[p] * v % P;
}

inline void pushdown(int p) {
  if (tag[p] != 1) {
    push(ls(p), tag[p]);
    push(rs(p), tag[p]);
    tag[p] = 1;
  }
}

void build(int p, int L, int R) {
  tag[p] = val[p] = 1;
  if (L == R)
    return;
  int mid = (L + R) >> 1;
  build(ls(p), L, mid);
  build(rs(p), mid + 1, R);
  pushup(p);
}

void mul(int p, int l, int r, int v, int L, int R) {

  if (l <= L && r >= R)
    return push(p, v);
  pushdown(p);
  int mid = (L + R) >> 1;
  if (l <= mid)
    mul(ls(p), l, r, v, L, mid);
  if (r > mid)
    mul(rs(p), l, r, v, mid + 1, R);
  pushup(p);
}

void change(int x) {

  // cerr << x << endl;

  if (left[x] > right[x])
    return;

  ll u = (1 - (vec[x].back() - not_pick[x]) % P + P) % P;
  u = fpow(u, P - 2);
  vec[x].pop_back();
  ll v = (1 - (vec[x].back() - not_pick[x]) % P + P) % P;

  u = u * v % P;

  mul(1, left[x], right[x], u, 1, q);
}


int main() {
  freopen("max.in", "r", stdin);
  freopen("max.out", "w", stdout);
  // freopen("example_max3.in", "r", stdin);

  n = rd(), m = rd(), q = rd();

  build(1, 1, q);

  for (int i = 1; i <= m; ++i) {
    int x = rd(), y = rd(), p = rd();
    if (!p || !y)
      continue;
    st[++cnt] = { x, y, p };

  }
  std::sort(st + 1, st + cnt + 1);

  for (int i = 1; i <= n; ++i)
    vec[i].push_back(1);

  for (int i = 1; i <= cnt; ++i) {
    vec[st[i].x].push_back((ll)vec[st[i].x].back() * (1 - st[i].p) % P);
    vec[st[i].x].back() = (vec[st[i].x].back() + P) % P;
  }

  for (int i = 1; i <= n; ++i)
    not_pick[i] = vec[i].back();

  for (int i = 1; i <= q; ++i) {
    int l = rd(), r = rd();
    qu[i] = { l, r };
  }
  std::sort(qu + 1, qu + q + 1);

  for (int i = 1, l = 1, r = 0; i <= n; ++i) {
    while (l <= r && qu[l].r < i)
      ++l;
    while (r < q && qu[r + 1].l <= i)
      ++r;
    left[i] = l, right[i] = r;
  }

  for (int i = cnt, j; i >= 1; ) {
    for (j = i; i >= 1 && st[i].y == st[j].y; --i)
      change(st[i].x);
    ans = (ans + (ll)val[1] * (st[j].y - st[i].y)) % P;
  }

  ans = ((ll)st[cnt].y * q - ans) % P;
  ans = (ans % P + P) % P;
  std::cout << ans << std::endl;
  return 0;
}