【题解】HAOI2012高速公路

　　一节政治课的结果……推式子+推式子+推式子……

　　首先注意到一个区间里面，选择（x, y）和（y, x）的费用是一样的。所以我们把这两种情况合为一种，那么现在询问的区间为（l, r），则一共的情况就有 1 / （k + 1）*（k）种（k = r - l + 1）。所以我们只需要求出区间内所有的子集之和 * 2 / （k + 1） * k（每种情况有两种）。但这样复杂度还是太高了，我们考虑继续推下式子。

　　顺着一个比较常见的思路想：分离出每一段路对于答案的贡献再累加起来。那么我们的ans = Vx（这一段路的代价） * 包含了这条道路的区间个数。包含了第x条道路的区间个数一共是（x - l + 1） * （r - x）。但这个东西我们不好维护，所以将它拆分一下，尽量分离出不变的量。这个东西就等于：（（rx + lx） - （x * x + x） + （r - l * r））* Vx。由此，问题转化为维护区间内的 Vx 之和， Vx * x之和，与 Vx * x * (x + 1)之和。线段树完美解决！

// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

#define int unsigned long long

int n, m, mark[maxn * ];

struct tree

{

    int l, r, num[], size, x, xx;

}T[maxn * ];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Build(int p, int l, int r)

{

    T[p].l = l, T[p].r = r, T[p].size = (r - l + );

    if(l == r)

    {

        T[p].num[] = T[p].num[] = T[p].num[] = ;

        T[p].x = l, T[p].xx = T[p].x * (T[p].x + );

        return;

    }

    int mid = (l + r) >> ;

    Build(p << , l, mid), Build(p <<  | , mid + , r);

    T[p].x = T[p << ].x + T[p <<  | ].x;

    T[p].xx = T[p << ].xx + T[p <<  | ].xx;

    return;

}

void push_up(int p, int num)

{

    T[p].num[] += num * T[p].x;

    T[p].num[] += num * T[p].xx;

    T[p].num[] += num * T[p].size;

    mark[p] += num;

}

void push_down(int p)

{

    if(!mark[p]) return;

    push_up(p << , mark[p]);

    push_up(p <<  | , mark[p]);

    mark[p] = ;

}

void update(int p, int l, int r, int num) // num1 :Vx * x, num2 :Vx * x * (x + 1), num3 : Vx;

{

    int mid = (l + r) >> ;

    int L = T[p].l, R = T[p].r;

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

    {

        push_up(p, num);

        return;

    }

    if(R < l || L > r) return;

    push_down(p);

    update(p << , l, r, num), update(p <<  | , l, r, num);

    T[p].num[] = T[p << ].num[] + T[p <<  | ].num[];

    T[p].num[] = T[p << ].num[] + T[p <<  | ].num[];

    T[p].num[] = T[p << ].num[] + T[p <<  | ].num[];

}

int query(int p, int l, int r, int opt)

{

    int L = T[p].l, R = T[p].r;

    if(R < l || L > r) return ;

    if(L >= l && R <= r) return T[p].num[opt];

    push_down(p);

    return query(p << , l, r, opt) + query(p <<  | , l, r, opt);

}

int Get(int a, int b)

{

    while(b)

    {

        int c = a % b;

        a = b;

        b = c;

    }

    return a;

}

signed main()

{

    n = read(), m = read();

    Build(, , n);

    for(int i = ; i <= m; i ++)

    {

        char c;

        cin >> c;

        int l = read(), r = read();

        if(c == 'C')

        {

            int v = read();

            update(, l, r - , v);

        }

        else // num1 :Vx * x, num2 :Vx * x * (x + 1), num3 : Vx;

        {

            int ans = query(, l, r - , ) * (l + r);

            ans -= query(, l, r - , );

            ans += query(, l, r - , ) * (r - l * r);

            int K = (r - l + ) * (r - l);

            int GCD = Get(ans * , K);

            printf("%lld/%lld\n", ans *  / GCD, K / GCD);

        }

    }

    return ;

}

巴特西

【题解】HAOI2012高速公路

最新文章

热门文章