[BZOJ 2752] 高速公路

Link:

BZOJ 2752 传送门

Solution:

虽然有期望，但实际上就是除了个总数……

此题计算总代价明显还是要使用对每个$w_i$计算贡献的方式：

$w_i的贡献为w_i*(i-l+1)*(r-i)$（左端点的方案数乘上右端点的方案数）

为了能使维护的数据符合$RMQ$的性质，我们要将$l,r$分离出来，拆项得到：

$-w_i*i^2+w_i*i*(l+r-1)+w_i*(r-r*l)$

求完前缀和后用3棵线段树分别维护0/1/2次项的区间和即可

Code:

#include <bits/stdc++.h>

using namespace std;

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

#define lc k<<1,l,mid

#define rc k<<1|1,mid+1,r

typedef long long ll;

const int MAXN=1e5+;

char op[];

int n,m,l,r,v;

ll seg[MAXN<<][],tag[MAXN<<],s1[MAXN],s2[MAXN];

void merge(int k)

{for(int i=;i<;i++) seg[k][i]=seg[k<<][i]+seg[k<<|][i];}

void modify(int k,int l,int r,ll inc)

{

    tag[k]+=inc;

    seg[k][]+=inc*(r-l+);

    seg[k][]+=inc*(s1[r]-s1[l-]);

    seg[k][]+=inc*(s2[r]-s2[l-]);

}

void pushdown(int k,int l,int r)

{

    if(!tag[k]) return;

    modify(lc,tag[k]);modify(rc,tag[k]);

    tag[k]=;

}

void Update(int a,int b,int x,int k,int l,int r)

{

    if(a<=l&&r<=b){modify(k,l,r,x);return;}

    pushdown(k,l,r);

    if(a<=mid) Update(a,b,x,lc);

    if(b>mid) Update(a,b,x,rc);

    merge(k);

}

ll Query(int a,int b,int x,int k,int l,int r)

{

    if(a<=l&&r<=b) return seg[k][x];

    pushdown(k,l,r);

    ll ret=;

    if(a<=mid) ret+=Query(a,b,x,lc);

    if(b>mid) ret+=Query(a,b,x,rc);

    return ret;

}

ll gcd(ll a,ll b)

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

int main()

{

    scanf("%d%d",&n,&m);

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

        s1[i]=s1[i-]+i,s2[i]=s2[i-]+1ll*i*i;

    while(m--)

    {

        scanf("%s%d%d",op,&l,&r);

        if(op[]=='C')

            scanf("%d",&v),Update(l,r-,v,,,n);

        else

        {

            ll res=Query(l,r-,,,,n)*r*(-l)+Query(l,r-,,,,n)*(r+l-)-Query(l,r-,,,,n);

            ll div=1ll*(r-l+)*(r-l)/;ll GCD=gcd(res,div);

            printf("%lld/%lld\n",res/GCD,div/GCD);

        }

    }

    return ;

}