luogu P2221 [HAOI2012]高速公路题解

题面

很套路的拆式子然后线段树上维护区间和的题。一般都是把式子拆成区间内几个形如\(\sum i*a_i, \sum i^2 * a_i\)的式子相加减的形式。

考虑一次询问[l,r]的答案怎么算：

\[ans=\sum_{i=l}^{r}a_i*(i-l+1)*(r-i+1)
\]

把括号拆开，就成了：

\[(l+r)\sum_{i=l}^{r}a_i*i-\sum_{i=l}^{r}a_i*i^2-(l-1)*(r+1)\sum_{i=l}^{r}a_i
\]

线段树上维护区间\(\sum i^2*a_i\)的和即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define N 200007

#define ll long long

struct data

{

    ll s1,s2,s3;

};

data operator +(data l,data r)

{

    return (data){l.s1+r.s1,l.s2+r.s2,l.s3+r.s3};

}

data operator *(data v,ll d)

{

    return (data){v.s1*d,v.s2*d,v.s3*d};

}

int n;

struct Tree

{

#define lc (k<<1)

#define rc (k<<1|1)

    data val[N<<2],sum[N<<2];

    ll add[N<<2];

    void mark(int k,ll d)

	{

	    val[k]=val[k]+sum[k]*d;

	    add[k]+=d;

	}

    void pushdown(int k)

	{

	    mark(lc,add[k]);

	    mark(rc,add[k]);

	    add[k]=0;

	}

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

	{

	    if(l==r)

	    {

		sum[k]={1,l,1ll*l*l};

		return;

	    }

	    int mid=l+r>>1;

	    build(lc,l,mid),build(rc,mid+1,r);

	    sum[k]=sum[lc]+sum[rc];

	}

    void modify(int k,int l,int r,int x,int y,ll d)

	{

	    if(l>=x&&r<=y)return mark(k,d);

	    int mid=l+r>>1;

	    pushdown(k);

	    if(x<=mid)modify(lc,l,mid,x,y,d);

	    if(y>mid)modify(rc,mid+1,r,x,y,d);

	    val[k]=val[lc]+val[rc];

	}

    data query(int k,int l,int r,int x,int y)

	{

	    if(l>=x&&r<=y)return val[k];

	    int mid=l+r>>1;

	    data ans={0,0,0};

	    pushdown(k);

	    if(x<=mid)ans=ans+query(lc,l,mid,x,y);

	    if(y>mid)ans=ans+query(rc,mid+1,r,x,y);

	    return ans;

	}

    void mdy(int l,int r,ll d)

	{

	    modify(1,1,n,l,r,d);

	}

    ll ask(ll l,ll r)

	{

	    data ans=query(1,1,n,l,r);

	    return (l+r)*ans.s2-ans.s3-(l-1)*(r+1)*ans.s1;

	}

}T;

ll gcd(ll x,ll y)

{

    return y?gcd(y,x%y):x;

}

int main()

{

    int m;

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

    int l,r;

    ll d;

    char s[10];

    T.build(1,1,n);

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

    {

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

	if(s[0]=='C')

	{

	    scanf("%lld",&d);

	    T.mdy(l,r,d);

	}

	else

	{

	    ll x=T.ask(l,r),len=r-l+1,y=1ll*len*(len+1)/2;

	    ll gd=gcd(x,y);

	    printf("%lld/%lld\n",x/gd,y/gd);

	}

    }

    return 0;

}

巴特西

luogu P2221 [HAOI2012]高速公路题解

最新文章

热门文章