M_sea

洛谷2221 [HAOI2012]高速公路
Luogu分析看到有区间修改和区间查询,可以考虑一下线段树。显然一个询问 $[l,r]$ 的答案为 $\displ...
扫描右侧二维码阅读全文
11
2019/07

洛谷2221 [HAOI2012]高速公路

Luogu

分析

看到有区间修改和区间查询,可以考虑一下线段树。

显然一个询问 $[l,r]$ 的答案为 $\displaystyle\frac{\sum_{i=l}^r\sum_{j=l}^rdis(i,j)}{r-l+1\choose 2}$ 。下面的可以直接算,考虑怎么快速计算上面的东西。

可以考虑每一条边的贡献,那么分子可以变成 $\displaystyle\sum_{i=l}^ra_i\times(i-l+1)(r-i+1)$ 。这里的 $a_i$ 表示第 $i$ 条边的费用。

把这个式子手动化简可以得到 $\displaystyle(r-l+1-l\cdot r)\sum_{i=l}^ra_i+(l+r)\sum_{i=l}^ria_i-\sum_{i=l}^ri^2a_i$ 。

于是只需要维护 $\sum a_i,\sum ia_i,\sum i^2a_i$ 这三个值即可。

考虑修改操作。假设把 $[l,r]$ 区间加上了 $v$ ,那么 $\sum a_i$ 增加了 $len\times v$ ,$\sum ia_i$ 增加了 $v\sum i$ ,$\sum i^2a_i$ 增加了 $v\sum i^2$ 。于是再多维护 $\sum i$ 和 $\sum i^2$ 这两个值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;

struct data { int sum1,sum2,sum3,sum4,sum5; };
data operator +(data a,data b) {
    return (data){a.sum1+b.sum1,a.sum2+b.sum2,a.sum3+b.sum3,
                  a.sum4+b.sum4,a.sum5+b.sum5};
}

data t[N<<2]; int addv[N<<2],lenv[N<<2];

#define ls (o<<1)
#define rs (o<<1|1)

inline void add(int o,int v) {
    t[o].sum1+=lenv[o]*v;
    t[o].sum2+=t[o].sum5*v;
    t[o].sum3+=t[o].sum4*v;
    addv[o]+=v;
}

inline void pushup(int o) { t[o]=t[ls]+t[rs]; }
inline void pushdown(int o) {
    if (addv[o]) {
        add(ls,addv[o]),add(rs,addv[o]);
        addv[o]=0;
    }
}

inline void build(int o,int l,int r) {
    lenv[o]=r-l+1;
    if (l==r) { t[o].sum4=l*l,t[o].sum5=l; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}

inline void modify(int o,int l,int r,int ql,int qr,int v) {
    if (ql<=l&&r<=qr) { add(o,v); return; }
    int mid=(l+r)>>1;
    pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,v);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,v);
    pushup(o);
}

inline data query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1; data res=(data){0,0,0,0,0};
    pushdown(o);
    if (ql<=mid) res=res+query(ls,l,mid,ql,qr);
    if (qr>mid) res=res+query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}

#undef ls
#undef rs

signed main() {
    n=read(),m=read(); build(1,1,n);
    while (m--) {
        char s[2]; scanf("%s",s);
        int l=read(),r=read()-1;
        if (s[0]=='C') modify(1,1,n,l,r,read());
        else {
            data ans=query(1,1,n,l,r);
            int a=(r-l+1-r*l)*ans.sum1+(r+l)*ans.sum2-ans.sum3;
            int b=(r-l+2)*(r-l+1)/2;
            int d=__gcd(a,b);
            printf("%lld/%lld\n",a/d,b/d);
        }
    }
    return 0;
}
最后修改:2019 年 07 月 11 日 03 : 26 PM

发表评论