BJOI2018 链上二次求和

wjh15101051's space

卧薪尝胆，厚积薄发。

BJOI2018 链上二次求和

Date: Wed Feb 27 11:06:56 CST 2019

In Category: NoCategory

Description：

一个序列，支持区间加，统计所有长度在 $[l,r]$ 内的路径和的和。

$1\leqslant n\leqslant 2\times10^5$

Solution：

首先可以转化成长度在 $[1,r]$ 的减去长度在 $[l,l-1]$ 的。

然后枚举长度和起始点，再交换求和号，最后可以写出这样一段代码：


int calc(int l)

{

	int ans = 0;

	for(int j = 1;j <= l;++j)ans += sum[j] * j;

	for(int j = l + 1;j <= n;++j)ans += l * sum[j];

	for(int j = 1;j <= n - l;++j)ans -= l * sum[j];

	for(int j = n - l + 1;j <= n - 1;++j)ans -= (n - j) * sum[j];

	return ans;

}

然后我们发现我们要维护的东西就是： $\sum a[i],\sum a[i]\times i,\sum a[i]\times (n-i)$ ，还要支持区间加等差数列，可以用线段树维护，类似SDOI相关分析。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 200010

#define MOD 1000000007

#define I inline 

int a[MAXN];

int sum[MAXN]; 

struct node

{

    int lc,rc,l,r;

    int sum,sum1,sum2,tagk,tagb;

}t[MAXN << 1];

int ptr = 0;

I int newnode(){return ++ptr;}

int root;

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

I void pushup(int rt)

{

    t[rt].sum = (t[t[rt].lc].sum + t[t[rt].rc].sum) % MOD;

    t[rt].sum1 = (t[t[rt].lc].sum1 + t[t[rt].rc].sum1) % MOD;

    t[rt].sum2 = (t[t[rt].lc].sum2 + t[t[rt].rc].sum2) % MOD;

    return;

}

void build(int &rt,int l,int r)

{

    rt = newnode();

    t[rt].l = l;t[rt].r = r;

    if(l == r)

    {

        t[rt].sum = sum[l];

        t[rt].sum1 = 1ll * l * sum[l] % MOD;

        t[rt].sum2 = 1ll * (n - l) * sum[l] % MOD;

        return;

    }

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    pushup(rt);

    return;

}

#define INV6 166666668

#define INV2 500000004

I int Mod(int a){return (a >= MOD ? a - MOD : (a < 0 ? a + MOD : a));}

I int sum2(int n){return 1ll * n * (n + 1) % MOD * (2 * n + 1) % MOD * INV6 % MOD;}

I int sum1(int l,int r){return Mod(1ll * r * (r + 1) % MOD * INV2 % MOD - 1ll * (l - 1) * l % MOD * INV2 % MOD);}

I int sum2(int l,int r){return Mod(sum2(r) - sum2(l - 1));}

I void addtag(int rt,int k,int b)

{

	int s0 = t[rt].r - t[rt].l + 1,s1 = sum1(t[rt].l,t[rt].r),s2 = sum2(t[rt].l,t[rt].r);

    if(b)t[rt].sum = Mod(t[rt].sum + 1ll * b * s0 % MOD);

    if(k)t[rt].sum = Mod(t[rt].sum + 1ll * k * s1 % MOD);

    if(b)t[rt].sum1 = Mod(t[rt].sum1 + 1ll * b * s1 % MOD);

    if(k)t[rt].sum1 = Mod(t[rt].sum1 + 1ll * k * s2 % MOD);

    if(b)t[rt].sum2 = Mod(t[rt].sum2 + Mod(1ll * b * n % MOD * s0 % MOD - 1ll * b * s1 % MOD));

    if(k)t[rt].sum2 = Mod(t[rt].sum2 + Mod(1ll * k * n % MOD * s1 % MOD - 1ll * k * s2 % MOD));

    t[rt].tagk = Mod(t[rt].tagk + k);t[rt].tagb = Mod(t[rt].tagb + b);

    return;

}

I void pushdown(int rt)

{

    if(t[rt].tagk == 0 && t[rt].tagb == 0)return;

    addtag(t[rt].lc,t[rt].tagk,t[rt].tagb);

    addtag(t[rt].rc,t[rt].tagk,t[rt].tagb);

    t[rt].tagk = 0;t[rt].tagb = 0;

    return;

}

void add(int rt,int L,int R,int k,int b,int l,int r)

{

    if(L > R)return;

    if(L <= l && r <= R){addtag(rt,k,b);return;}

    pushdown(rt);

    if(L <= mid)add(t[rt].lc,L,R,k,b,l,mid);

    if(R > mid)add(t[rt].rc,L,R,k,b,mid + 1,r);

    pushup(rt);

    return; 

}

int query(int rt,int L,int R,int k,int l,int r)

{

    if(L <= l && r <= R)

    {

        if(k == 0)return t[rt].sum;

        if(k == 1)return t[rt].sum1;

        if(k == 2)return t[rt].sum2;

    }

    pushdown(rt);

    register int res = 0;

    if(L <= mid)res = Mod(res + query(t[rt].lc,L,R,k,l,mid));

    if(R > mid)res = Mod(res + query(t[rt].rc,L,R,k,mid + 1,r));

    return res;

}

I int calc(int l)

{

    register int ans = 0;

    if(1 <= l)ans = Mod(ans + query(root,1,l,1,1,n));

    if(l + 1 <= n)ans = Mod(ans + 1ll * l * query(root,l + 1,n,0,1,n) % MOD);

    if(1 <= n - l)ans = Mod(ans - 1ll * l * query(root,1,n - l,0,1,n) % MOD + MOD);

    if(n - l + 1 <= n - 1)ans = Mod(ans - query(root,n - l + 1,n - 1,2,1,n));

    return ans;

}

int main()

{

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

    for(register int i = 1;i <= n;++i)a[i] = rd();

    for(register int i = 1;i <= n;++i)sum[i] = Mod(sum[i - 1] + a[i]);

    build(root,1,n);

    register int opt,l,r,v;

    for(register int k = 1;k <= m;++k)

    {

        opt = rd();

        if(opt == 1)

        {

            l = rd();r = rd();v = rd();if(l > r)swap(l,r);

            add(root,l,r,v,Mod(v - 1ll * v * l % MOD),1,n);

            add(root,r + 1,n,0,1ll * (r - l + 1) * v % MOD,1,n);

        }

        else

        {

            l = rd();r = rd();

            printf("%d\n",Mod(calc(r) - calc(l - 1)));

        }

    }

    return 0;

}

In tag: 数据结构-线段树

wjh15101051