HAOI2012 高速公路

一道非常好的线段树题。

Sol.

优先想到线段树，考虑怎么维护。

记第 \(i\) 到第 \(i+1\) 条边为第 \(i\) 条边，将问题转化成维护 \(n-1\) 个数。

那么，我们维护一个前缀和 \(sum\)，根据题意：

\[ Ans=\frac{\sum\limits_{i=l}^{r}\sum\limits_{j=l}^{r}sum_j-sum_i}{\binom{r-l+1}{2}}(i\neq j) \]

下面的东西很好算，重点是上面的东西怎么维护。

我们把上面的东西记作 \(ans\)，考虑枚举每条边被计算的次数，可以理解成枚举每个点左右两条路。

所以：

\[ \begin{split} ans &=\sum\limits_{i=l}^{r}a_i\times (r-i+1)(i-l+1)\\ &=\sum\limits_{i=l}^{r}a_i\times (ir-lr+r-i^2+il-i+i-l+1)\\ &=\sum\limits_{i=l}^{r}a_i\times (-i^2+(l+r)i-lr+r-l+1)\\ &=-\sum\limits_{i=l}^{r}a_i\times i^2+(l+r)\sum\limits_{i=l}^{r}a_i\times i+(r-l-lr+1)\sum\limits_{i=l}^{r}a_i \end{split} \]

现在需要维护 \(sum_1=\sum_{i=l}^{r}a_i\times i^2\)，\(sum_2=\sum_{i=l}^{r}a_i\times i\)，\(sum_3=\sum_{i=l}^{r}a_i\)。

即变成：

\[ans=-sum1+(l+r)sum2+(r-l-lr+1)sum3\]

考虑 pushup 的时候，直接相加就可以了。

考虑在区间 \([L,R]\) 加上一个 \(x\) 的时候怎么做：

\[ \begin{split} sum_3' &= \sum\limits_{i=L}^{R}(a_i+x)\\ &= (R-L+1)x+\sum\limits_{i=L}^{R}a_i\\ &= (R-L+1)x+sum_3\\ \Delta sum_3 &= (R-L+1)x \end{split} \]

直接维护。

\[ \begin{split} sum_2' &= \sum\limits_{i=L}^{R}i(a_i+x)\\ &= \sum\limits_{i=L}^{R}i\times a_i+\sum\limits_{i=L}^{R}ix\\ &= \sum\limits_{i=L}^{R}i\times a_i+x\sum\limits_{i=L}^{R}i\\ &= x\sum\limits_{i=L}^{R}i+sum_2\\ \Delta sum_2 &= x\sum\limits_{i=L}^{R}i \end{split} \]

维护区间和。

\[ \begin{split} sum_1' &= \sum\limits_{i=L}^{R}i^2(a_i+x)\\ &= \sum\limits_{i=L}^{R}i^2\times a_i+\sum\limits_{i=L}^{R}i^2x\\ &= \sum\limits_{i=L}^{R}i^2\times a_i+x\sum\limits_{i=L}^{R}i^2\\ &= x\sum\limits_{i=L}^{R}i^2+sum_1\\ \Delta sum_1 &= x\sum\limits_{i=L}^{R}i^2 \end{split} \]

维护区间平方和。

最后求期望约分即可。

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 100007;

int n, m;
int ans1, ans2, ans3;

class Tree
{
    #define int long long
	private:
		struct Node
        {
            int sum1, sum2, sum3, sum4, sum5;
            int lazy;
            int l, r;
        }tree[MAXN << 2];
		
		inline int lc(int k){return k << 1;}
		
		inline int rc(int k){return k << 1 | 1;}
		
		inline void f(int k, int v)
		{
			tree[k].lazy += v;
			tree[k].sum1 += (tree[k].r - tree[k].l + 1) * v;
            tree[k].sum2 += v * tree[k].sum5;
            tree[k].sum3 += v * tree[k].sum4;
		}
		
		inline void pushup(int k)
		{
			tree[k].sum1 = tree[lc(k)].sum1 + tree[rc(k)].sum1;
            tree[k].sum2 = tree[lc(k)].sum2 + tree[rc(k)].sum2;
            tree[k].sum3 = tree[lc(k)].sum3 + tree[rc(k)].sum3;
		}
		
		inline void pushdown(int k)
		{
			f(lc(k), tree[k].lazy);
			f(rc(k), tree[k].lazy);
			tree[k].lazy = 0;
		}
		
	public:
		void build(int k,int l, int r)
		{
			tree[k].lazy = 0;
            tree[k].l = l;
            tree[k].r = r;
			if(l == r)
			{
				tree[k].sum4 = l * l;
                tree[k].sum5 = l;
				return;
			}
			int mid = (l + r) >> 1;
			build(lc(k), l, mid);
			build(rc(k), mid + 1, r);
			tree[k].sum4 = tree[lc(k)].sum4 + tree[rc(k)].sum4;
            tree[k].sum5 = tree[lc(k)].sum5 + tree[rc(k)].sum5;
		}
		
		void update(int k, int L, int R, int v)
		{
			if(L <= tree[k].l && tree[k].r <= R)
			{
				f(k, v);
				return;
			}
			pushdown(k);
			int mid = (tree[k].l + tree[k].r) >> 1;
			if(L <= mid) update(lc(k), L, R, v);
			if(R > mid) update(rc(k), L, R, v);
			pushup(k);
		}
		
		void query(int k, int L, int R)
		{
			if(L <= tree[k].l && tree[k].r <= R)
            {
                ans1 += tree[k].sum1;
                ans2 += tree[k].sum2;
                ans3 += tree[k].sum3;
                return;
            }
			pushdown(k);
			int mid = (tree[k].l + tree[k].r) >> 1;
			if(L <= mid) query(lc(k), L, R);
			if(R > mid) query(rc(k), L, R);
			return;
		}	
};

Tree t;

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

signed main()
{
    scanf("%lld%lld", &n, &m);
    t.build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        char op;
        int l, r, v;
        cin >> op;
        scanf("%lld%lld", &l, &r);
        r--;
        if(op == 'C')
        {
            scanf("%lld", &v);
            t.update(1, l, r, v);
        }
        else
        {
            ans1 = ans2 = ans3 = 0;
            t.query(1, l, r);
            int a, b, c;
            a = (r - l + 1 - r * l) * ans1 + (r + l) * ans2 - ans3;
            b = (r - l + 2) * (r - l + 1) / 2;
            c = gcd(a, b);
            //cout << l << r << b;
            printf("%lld/%lld\n", a / c, b / c);
        }
    }
    return 0;
}