【BZOJ2752】[HAOI2012]高速公路

题目链接：传送门
题解：
对于l到r中的第i段公路，贡献是
<nobr> (i−l+1)∗(r−i)∗v[i]=v[i]∗(r−l∗r)+v[i]∗i∗(l+r−1)−v[i]∗i∗i </nobr>
线段树随便维护一下就好了

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define gmid int mid=(l+r)>>1
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010;
int n,m;
LL b[N],c[N],w;
inline int in()
{
    char ch=getchar();
    int f=1,tmp=0;
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
    return tmp*f;
}
char s[10];
struct node
{
    LL a,b,c,col;
}t[N*4+5];

void pushdown(int rt,int l,int r,int mid)
{
    if(!t[rt].col) return;
    LL x=t[rt].col;t[rt].col=0;
    t[L(rt)].col+=x;
    t[R(rt)].col+=x;
    t[L(rt)].a+=(mid-l+1)*x;
    t[R(rt)].a+=(r-mid)*x;
    t[L(rt)].b+=(b[mid]-b[l-1])*x;
    t[R(rt)].b+=(b[r]-b[mid])*x;
    t[L(rt)].c+=(c[mid]-c[l-1])*x;
    t[R(rt)].c+=(c[r]-c[mid])*x;
}

void upd(int rt)
{
    t[rt].a=t[L(rt)].a+t[R(rt)].a;
    t[rt].b=t[L(rt)].b+t[R(rt)].b;
    t[rt].c=t[L(rt)].c+t[R(rt)].c;
}

void add(LL val,LL L,LL R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        t[rt].a+=(r-l+1)*val;
        t[rt].b+=(b[r]-b[l-1])*val;
        t[rt].c+=(c[r]-c[l-1])*val;
        t[rt].col+=val;
        return;
    }
    gmid;
    pushdown(rt,l,r,mid);
    if(L<=mid) add(val,L,R,lson);
    if(R>mid)  add(val,L,R,rson);
    upd(rt);
}

LL query(int op,LL L,LL R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        if(op==1) return t[rt].a;
        if(op==2) return t[rt].b;
        if(op==3) return t[rt].c;       
    }
    gmid;
    pushdown(rt,l,r,mid);
    LL ans=0;
    if(L<=mid) ans+=query(op,L,R,lson);
    if(R>mid)  ans+=query(op,L,R,rson);
    return ans;
}

LL gcd(LL a,LL b) {return (b)?gcd(b,a%b):a;}
void gi(LL l,LL r)
{
    LL ans=-1ll*query(3,l,r-1,1,n-1,1)+(r+l-1)*query(2,l,r-1,1,n-1,1)+(r-l*r)*query(1,l,r-1,1,n-1,1);
    LL k=(r-l+1)*(r-l)/2ll;
    LL G=gcd(ans,k);
    printf("%lld/%lld\n",ans/G,k/G);
}

int main()
{

    n=in(),m=in();
    for(LL i=1;i<=n;i++) b[i]=b[i-1]+i,c[i]=c[i-1]+i*i;
    LL l,r;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        l=in(),r=in();
        if(s[0]=='C')
        {
            w=in();
            add(w,l,r-1,1,n-1,1);
        }
        else gi(l,r);
    }
    return 0;
}