首页 > 其他 > 详细

外挂 线段树

时间:2019-06-16 00:22:57      阅读:134      评论:0      收藏:0      [点我收藏+]

  https://ac.nowcoder.com/acm/contest/917/J

 

两种操作 区间加

还有就是求区间 两两乘积和

作者:water201809070940881
链接:https://ac.nowcoder.com/discuss/198506?tdsourcetag=s_pcqq_aiomsg
来源:牛客网

首先,我们发现

ri=l(ai×rj=i+1aj)=ri=lrj=i+1ai×aj∑i=lr(ai×∑j=i+1raj)=∑i=lr∑j=i+1rai×aj

有没有觉得后面这个东西很熟?其实这个询问就是求区间的数两两相乘的和。

但是好像还是没法算啊!

我们再观察这个东西,又可以发现

ri=lrj=i+1ai×aj=12×((ri=lai)2ri=la2i)∑i=lr∑j=i+1rai×aj=12×((∑i=lrai)2−∑i=lrai2)

其实就是区间和的平方减掉区间平方和的1212。

对于区间加,线段树维护一下和与平方和就好了,时间复杂度小到爆炸O(Qlogn)O(Qlog?n)(实际的话因为数据随机,后面77个点每个点标程跑的不到100ms100ms,开1000ms1000ms都是出题人良心了)。

这个公式的来源其实就是

(a1+a2+...+an)2=a21+a22+...+a2n+2ni=1nj=i+1ai×aj(a1+a2+...+an)2=a12+a22+...+an2+2∑i=1n∑j=i+1nai×aj

然后移项一下,提个式子,分解一下就是这道题了。

 

其实就是维护区间平方和 和普通的区间和

 

技术分享图片
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1
//////////////////////////////////
const int N=1e6+5;
ll sum1[N<<2],col[N<<2],sum2[N<<2];
int n,m,op,a,b,c,v;

void up(int pos)
{
    sum1[pos]=sum1[pos<<1]+sum1[pos<<1|1];
    sum2[pos]=sum2[pos<<1]+sum2[pos<<1|1];
}
void down(int pos,int m)
{
    if(col[pos])
    {
        sum2[pos<<1]+=(m-(m>>1))*col[pos]*col[pos]+2*sum1[pos<<1]*col[pos];
        sum2[pos<<1|1]+=(m>>1)*col[pos]*col[pos]+2*sum1[pos<<1|1]*col[pos];

        sum1[pos<<1]+=(m-(m>>1))*col[pos];
        sum1[pos<<1|1]+=(m>>1)*col[pos];

        col[pos<<1]+=col[pos];col[pos<<1|1]+=col[pos];
        col[pos]=0;
    }
}

void build(int l,int r,int pos)
{
    col[pos]=0;
    if(r==l)
    {
        scanf("%lld",&sum1[pos]);
        sum2[pos]=sum1[pos]*sum1[pos];
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    up(pos);
}

void update(int L,int R,ll v,int l,int r,int pos)
{
    if(L<=l&&r<=R)
    {
        int len=(r-l+1);
        sum2[pos]+=len*v*v+sum1[pos]*2*v;
        sum1[pos]+=len*v;
        col[pos]+=v;
        return ;
    }
    int m=(r+l)>>1;
    down(pos,r-l+1);
    if(L<=m)update(L,R,v,lson);
    if(R>m)update(L,R,v,rson);
    up(pos);
}
ll query(int L,int R,int flag,int l,int r,int pos)
{
    ll ans=0;
    if(L<=l&&r<=R)
    {
        if(flag==1)return sum1[pos];
        if(flag==2)return sum2[pos];
    }
    int m=(l+r)>>1;
    down(pos,r-l+1);

    if(L<=m)ans+=query(L,R,flag,lson);
    if(R>m)ans+=query(L,R,flag,rson);
    up(pos);
    return ans;
}
int main()
{
    RII(n,m);
    build(1,n,1);

    rep(i,1,m)
    {
        RI(op);
        if(op==1)
        {
            RII(a,b);ll c;scanf("%lld",&c);
            update(a,b,c,1,n,1);
        }
        else
        {
            RII(a,b);
            ll temp1=query(a,b,1,1,n,1);
            ll temp2=query(a,b,2,1,n,1);
            cout<< (temp1*temp1-temp2)/2<<endl;
        }
    }
    return 0;
}
View Code

 

外挂 线段树

原文:https://www.cnblogs.com/bxd123/p/11029243.html

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