【HAOI 2012】高速公路

2021-08-22 07:54:57

Problem

Description

\(Y901\) 高速公路是一条重要的交通纽带，*部门建设初期的投入以及使用期间的养护费用都不低，因此*在这条高速公路上设立了许多收费站。

\(Y901\) 高速公路是一条由 \(n-1\) 段路以及 \(n\) 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 \(1\sim n\) ，从收费站 \(i\) 行驶到 \(i+1\) (或从 \(i+1\) 行驶到 \(i\) )需要收取 \(V_i\) 的费用。高速路刚建成时所有的路段都是免费的。

*部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小 \(A\) 同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的\(l,r(l< r)\) ,在第 \(l\) 个到第 \(r\) 个收费站里等概率随机取出两个不同的收费站 \(a\) 和 \(b\)，那么从 \(a\) 行驶到 \(b\) 将期望花费多少费用呢?

Input Format

第一行 \(2\) 个正整数 \(n,m\)，表示有 \(n\) 个收费站，\(m\) 次调整或询问

接下来 \(m\) 行，每行将出现以下两种形式中的一种

\(C\ \ l\ \ r\ \ v\) 表示将第 \(l\) 个收费站到第 \(r\) 个收费站之间的所有道路的通行费全部增加 \(v\)

\(Q\ \ l\ \ r\) 表示对于给定的 \(l,r\)，要求回答小 \(A\) 的问题

所有 \(C\) 与 \(Q\) 操作中保证 \(1\le l< r\le n\)

Output Format

对于每次询问操作回答一行，输出一个既约分数

若答案为整数 \(ans\) ，输出 \(ans/1\)。

Sample

Input

Output

1/1

8/3

17/6

Explanation

所有 \(C\) 操作中的 \(v\) 的绝对值不超过 \(10000\)

在任何时刻任意道路的费用均为不超过 \(10000\) 的非负整数

所有测试点的详细情况如下表所示

Range

\(Test\)	\(n\)	\(m\)
1	=10	=10
2	=100	=100
3	=1000	=1000
4	=10000	=10000
5	=50000	=50000
6	=60000	=60000
7	=70000	=70000
8	=80000	=80000
9	=90000	=90000
10	=100000	=100000

Algorithm

线段树

Mentality

很显然，这题和期望概率毫无关系，只需要求出总贡献再去除以 \(C_{r-l+1}^2\) 即可。

那么如何求总贡献呢？

考虑分开计算贡献，我们最后的总贡献肯定是：

\[\sum_{i=l}^r V[i]*(i-l+1)*(r-i+1)
\]

仔细凝视这个式子肯定是看不出什么的还会显得你很愚蠢，动手才是正途。我们先把这两个括号拆开看看：

\[V[i]*(i-l+1)*(r-i+1)=V[i]*(r*i-i^2+i-l*r+l*i-l+r-i+1)\\
=V[i]*(r-l+1-r*l)+V[i]*i*(r+l)-V[i]*i^2
\]

好的，既然我们拆成了这样，那么我们的 \(\sum\) 就成功地被一拆三了！由于我们已经把包含 \(i\) 的项都单独放在了外面，剩下的都是定值，那么我们的总贡献就改为了这样的三个 \(\sum\) 之和：

\[((r-l+1-r*l)*\sum V[i])+((r+l)*\sum V[i]*i)+(\sum V[i]*i^2)
\]

由于 \(r-l+1-r*l\) 和 \(r+l\) 都很普通，我们只需要用线段树维护三个含 \(i\) 的值就好啦！

至于这三个值怎么维护呢？看着满阔怕，但是由于 \(\sum\) 中的每一项都是单独算的，那么不难发现，我们对一个区间都加上 \(v\) 时，这段区间上三个值加上的贡献肯定分别为：\(v*(r-l+1)\) ，\(v*\sum i\)，\(v*\sum i^2\) 。那么我们只需要预处理一下 \(i\) 和 \(i^2\) 的前缀和即可！

最后和 \(C_{r-l+1}^2\) 同除 \(gcd\) 即可。

啥？代码有哪些坑点？没啥坑点，自己体会 = = 。

Code

#include <cstdio>

#include <iostream>

using namespace std;

#define ls (o << 1)

#define rs ((o << 1) + 1)

#define mid ((l + r) >> 1)

int n, m;

long long x, L, R, ans[4], a[100001], q1[100001], q2[100001], adv[400001],

    sum[4][400001];

char opt;

void pushup(int o) {

  for (int i = 1; i <= 3; i++) sum[i][o] = sum[i][ls] + sum[i][rs];

}

void pushdown(int o, int l, int r) {

  sum[1][ls] += 1ll * adv[o] * (mid - l + 1);

  sum[2][ls] += adv[o] * (q1[mid] - q1[l - 1]);

  sum[3][ls] += adv[o] * (q2[mid] - q2[l - 1]);

  sum[1][rs] += 1ll * adv[o] * (r - mid);

  sum[2][rs] += adv[o] * (q1[r] - q1[mid]);

  sum[3][rs] += adv[o] * (q2[r] - q2[mid]);

  adv[ls] += adv[o], adv[rs] += adv[o];

  adv[o] = 0;

}

void add(int o, int l, int r) {

  if (l >= L && r <= R) {

    adv[o] += x;

    sum[1][o] += 1ll * x * (r - l + 1);

    sum[2][o] += x * (q1[r] - q1[l - 1]);

    sum[3][o] += x * (q2[r] - q2[l - 1]);

    return;

  }

  pushdown(o, l, r);

  if (mid >= L) add(ls, l, mid);

  if (mid < R) add(rs, mid + 1, r);

  pushup(o);

}

void query(int o, int l, int r) {

  if (l >= L && r <= R) {

    for (int i = 1; i <= 3; i++) ans[i] += sum[i][o];

    return;

  }

  pushdown(o, l, r);

  if (mid >= L) query(ls, l, mid);

  if (mid < R) query(rs, mid + 1, r);

  pushup(o);

}

long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }

int main() {

  freopen("2221.in", "r", stdin);

  freopen("2221.out", "w", stdout);

  cin >> n >> m;

  for (int i = 1; i <= n; i++) {

    scanf("%lld", &a[i]);

    q1[i] = q1[i - 1] + 1ll * i;

    q2[i] = q2[i - 1] + 1ll * i * i;

  }

  while (m--) {

    scanf("%s%lld%lld", &opt, &L, &R);

    R--;

    if (opt == 'C') {

      scanf("%lld", &x);

      add(1, 1, n);

    } else {

      ans[1] = ans[2] = ans[3] = 0;

      query(1, 1, n);

      long long Ans = (R - L + 1 - R * L) * ans[1] + (L + R) * ans[2] - ans[3],

                Tot = (R - L + 2) * (R - L + 1) / 2;

      long long Gcd = gcd(Ans, Tot);

      printf("%lld/%lld\n", Ans / Gcd, Tot / Gcd);

    }

  }

}

码农公寓