【BZOJ2752】[HAOI2012]高速公路(road)

2015.08.17 20:37 Mon | 21次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给出一段序列,要求支持给一个区间加一个数,或查询在区间中任选两个点构成区间的区间和的期望值。
n,q<=100000

题解

一段区间总共有len*(len-1)/2种选择。
每个点能被选择的次数是(i-st)(ed-i),i为这个点的下标,st,ed为区间的起点终点,总的答案就是Σv[i](i-st)(ed-i)/(len(len-1)/2),
把式子拆开可以发现,我们只要维护处 v[i]的和,v[i]*i的和,v[i]*i*i的和就可以了,这个用一个线段树搞就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define N 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int n,m,l,r,v;
char s[5];
struct node
{
    ll s,si,sii,add;
}a[N<<2];
void add(ll l,ll r,int rt,ll v)
{
    a[rt].s+=(r-l+1)*v;
    a[rt].si+=v*(r+l)*(r-l+1)/2;
    a[rt].sii+=v*(r*(r+1)*(2*r+1)/6-(l-1)*l*(2*l-1)/6);
    a[rt].add+=v;
}
void pushdown(int rt,int l,int r)
{
    if(a[rt].add)
    {
        int mid=(l+r)>>1;
        add(lson,a[rt].add);
        add(rson,a[rt].add);
        a[rt].add=0;
    }
}
void pushup(node &a,node b,node c)
{
    a.s=b.s+c.s;a.si=b.si+c.si;a.sii=b.sii+c.sii;
}
void update(int l,int r,int rt,int L,int R,ll v)
{
    if(L<=l&&R>=r)
    {
        add(l,r,rt,v);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) update(lson,L,R,v);
    if(R>mid) update(rson,L,R,v);
    pushup(a[rt],a[rt<<1],a[rt<<1|1]);
}
node query(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r) return a[rt];
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(R<=mid) return query(lson,L,R);
    else if(L>mid) return query(rson,L,R);
    else {node tmp;pushup(tmp,query(lson,L,mid),query(rson,mid+1,R));return tmp;}
}
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
void calc(ll st,ll ed,node tmp)
{
    ll len=ed-st+1,d=len*(len+1)/2;
    ll u=tmp.si*(ed+st)-tmp.sii-tmp.s*(ed*st-ed+st-1);
    if(u==0) puts("0/1");
    else
    {
        ll g=gcd(d,u);
        printf("%lld/%lld\n",u/g,d/g);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='C') scanf("%d%d%d",&l,&r,&v),update(1,n,1,l,r-1,v);
        else scanf("%d%d",&l,&r),calc(l,r-1,query(1,n,1,l,r-1));
    }
}```