首页 > 其他 > 详细

BZOJ5291 BJOI2018链上二次求和(线段树)

时间:2018-12-12 23:25:54      阅读:190      评论:0      收藏:0      [点我收藏+]

  用线段树对每种长度的区间维护权值和。

  考虑区间[l,r]+1对长度为k的区间的贡献,显然其为Σk-max(0,k-i)-max(0,k-(n-i+1)) (i=l~r)。

  大力展开讨论。首先变成Σk-Σmax(0,k-i)-Σmax(0,k-(n-i+1)) (i=l~r)。

  第一部分是一个常数,线段树上是加了一个等差数列。打上标记即可。

  后面两部分本质相同,现考虑Σmax(0,k-i) (i=l~r)。去掉max,即Σk-i (i=l~min(r,k))。根据r和k的大小关系讨论。若r<=k,线段树上加了一个一次函数;若r>k,线段树上加了一个二次函数。三种标记即可。

  常数巨大,下传标记时判一下是否有标记需要传可以快至少一倍。读入序列直接当做修改就能跑过。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define P 1000000007
#define inv 500000004
char getc(){char c=getchar();while ((c<A||c>Z)&&(c<a||c>z)&&(c<0||c>9)) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<0||c>9) {if (c==-) f=-1;c=getchar();}
    while (c>=0&&c<=9) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,a[N],s[3][N];
struct data{int l,r,sum,lazy[3];
}tree[N<<2];
inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
inline void up(int k){tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;if (tree[k].sum>=P) tree[k].sum-=P;}
inline void update(int k,int x,int op)
{
    inc(tree[k].sum,1ll*x*(s[op][tree[k].r]-s[op][tree[k].l-1]+P)%P);
    inc(tree[k].lazy[op],x);
}
inline void down(int k,int i)
{
    update(k<<1,tree[k].lazy[i],i),
    update(k<<1|1,tree[k].lazy[i],i),
    tree[k].lazy[i]=0;
}
void build(int k,int l,int r)
{
    tree[k].l=l,tree[k].r=r;
    if (l==r) return;
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void add(int k,int l,int r,int x,int op)
{
    if (l>r) return;
    if (tree[k].l==l&&tree[k].r==r) {update(k,x,op);return;}
    if (tree[k].lazy[0]) down(k,0);
    if (tree[k].lazy[1]) down(k,1);
    if (tree[k].lazy[2]) down(k,2);
    int mid=tree[k].l+tree[k].r>>1;
    if (r<=mid) add(k<<1,l,r,x,op);
    else if (l>mid) add(k<<1|1,l,r,x,op);
    else add(k<<1,l,mid,x,op),add(k<<1|1,mid+1,r,x,op);
    up(k);
}
int query(int k,int l,int r)
{
    if (tree[k].l==l&&tree[k].r==r) return tree[k].sum;
    if (tree[k].lazy[0]) down(k,0);
    if (tree[k].lazy[1]) down(k,1);
    if (tree[k].lazy[2]) down(k,2);
    int mid=tree[k].l+tree[k].r>>1;
    if (r<=mid) return query(k<<1,l,r);
    else if (l>mid) return query(k<<1|1,l,r);
    else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%P;
}
void modify(int l,int r,int x)
{
    add(1,r,n,1ll*(r-l+1)*x%P,1),add(1,r,n,P-1ll*(s[1][r]-s[1][l-1]+P)*x%P,0);
    add(1,l,r-1,1ll*x*inv%P,2),add(1,l,r-1,1ll*x*(P+1-l-inv)%P,1),add(1,l,r-1,1ll*l*(l-1)%P*inv%P*x%P,0);
}
void change(int l,int r,int x)
{
    add(1,1,n,1ll*(r-l+1)*x%P,1);
    modify(l,r,P-x),modify(n-r+1,n-l+1,P-x);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj5291.in","r",stdin);
    freopen("bzoj5291.out","w",stdout);
    const char LL[]="%I64d\n";
#else
    const char LL[]="%lld\n";
#endif
    n=read(),m=read();
    build(1,1,n);
    for (int i=1;i<=n;i++) s[0][i]=s[0][i-1]+1,s[1][i]=(s[1][i-1]+i)%P,s[2][i]=(s[2][i-1]+1ll*i*i)%P;
    for (int i=1;i<=n;i++) change(i,i,read());
    while (m--)
    {
        int op=read();
        if (op==1)
        {
            int l=read(),r=read(),x=read();
            if (l>r) swap(l,r);
            change(l,r,x);
        }
        else
        {
            int l=read(),r=read();
            printf("%d\n",query(1,l,r));
        }
    }
    return 0;
}

 

BZOJ5291 BJOI2018链上二次求和(线段树)

原文:https://www.cnblogs.com/Gloid/p/10111186.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!