1008 数据结构 线段树 区间加法 区间乘法 区间平方和 区间和

本文主要是介绍1008 数据结构 线段树 区间加法 区间乘法 区间平方和 区间和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 链接：https://ac.nowcoder.com/acm/contest/26896/1008
来源：牛客网

题目描述

qn姐姐最好了~ qn姐姐给你了一个长度为n的序列还有m次操作让你玩， 1 l r 询问区间[l,r]内的元素和
2 l r 询问区间[l,r]内的元素的平方 和 3 l r x 将区间[l,r]内的每一个元素都乘上x
4 l r x 将区间[l,r]内的每一个元素都加上x

输入描述:

第一行两个数n,m

接下来一行n个数表示初始序列

就下来m行每行第一个数为操作方法opt，

若opt=1或者opt=2，则之后跟着两个数为l,r

若opt=3或者opt=4，则之后跟着三个数为l,r,x

操作意思为题目描述里说的

输出描述:

对于每一个操作1,2，输出一行表示答案

示例1

输入

复制 5 6 1 2 3 4 5 1 1 5 2 1 5 3 1 2 1 4 1 3 2 1 1 4 2 2 3

5 6
1 2 3 4 5
1 1 5
2 1 5
3 1 2 1
4 1 3 2
1 1 4
2 2 3

输出

复制 15 55 16 41

15
55
16
41

备注:

对于100%的数据 n=10000,m=200000 (注意是等于号)

保证所有询问的答案在long long 范围内

分析

平方和：x * x =》在区间里修改每一个元素之后的平方和： (x + a) ^ 2 = x * x + a * a + 2 * a * x  。累加 =>  E(x * x) + E(a * a) + 2 * a * E(x)  所以只需要知道前区间和 以及 区间平方和，根据每个元素的增量，就可以算出新的平方和。

如何使用lazy标记表示这个区间平方和？

直接表示成加法lazy 标记就行了

传递跟区间和 一样，用push_down传下去，只不过这个传的时候要写全并且用上区间和

怎么区间乘？

用第二个标记表示乘了多少。传递下去的时候根据方程直接乘 就可以了

区间乘和区间加怎么一起考虑？

对于方程ax + b ，考虑整体乘 k ，a* k * x + b * x 再加 v ，a * k * x + (b * x + v)

 所以只需要传递 lazy 标记的时候 ，  先乘再加 ，把 标记 改变，同时把值改变就可以了 

//-------------------------代码----------------------------

#define int ll
const int N = 1e4+10;
int n,m;

int a[N];
struct node {
    int l,r,s1,s2,la1,la2;//
    //区间 一次 二次 加 乘
} tr[4 * N];

void push_up(int p) {
    tr[p].s1 = tr[p<<1].s1 + tr[p<<1|1].s1;
    tr[p].s2 = tr[p<<1].s2 + tr[p<<1|1].s2;
}

void push_down(int p,int tot) {
    if(tr[p].l == tr[p].r) rt;
    if(tr[p].la1 == 0 && tr[p].la2 == 1) rt;
    //先乘后加
    int x = tr[p].la1,y = tr[p].la2;tr[p].la1 = 0,tr[p].la2 = 1;
    //先乘后加
    tr[pl].s1 *= y;tr[pl].s2 *= y * y;
    tr[pr].s1 *= y;tr[pr].s2 *= y * y;
    tr[pl].la1 *=y;tr[pr].la2 *=y;
    tr[pr].la1 *=y;tr[pr].la2 *=y;
    
    tr[pl].la1 +=x;tr[pr].la1 += x;
    tr[pl].s2 += len(pl) * x * x + 2 * x * tr[pl].s1;
    tr[pr].s2 += len(pr) * x * x + 2 * x * tr[pr].s1;
    tr[pl].s1 += len(pl) * x;
    tr[pr].s1 += len(pr) * x;
}

void build(int p,int l,int r) {
    if(l == r) {
        tr[p] = {l,r,a[l],a[l] * a[l],0,1};
        rt;
    }
    int mid = l + r >> 1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    tr[p] = {l,r,0,0,0,1};
    push_up(p);
}

int query1(int p,int l,int r) {
    if(l <= tr[p].l && tr[p].r <= r) {
        return tr[p].s1;
    }
    push_down(p,tr[p].r - tr[p].l);
    int mid = tr[p].l + tr[p].r >> 1,ans = 0;
    if(l <= mid) ans += query1(pl,l,r);
    if(mid < r) ans += query1(pr,l,r);
    return ans;
}

int query2(int p,int l,int r) {
    if(l <= tr[p].l && tr[p].r <= r) {
        return tr[p].s2;
    }
    push_down(p,tr[p].r - tr[p].l);
    int mid = tr[p].l + tr[p].r >> 1,ans = 0;
    if(l <= mid) ans += query2(pl,l,r);
    if(mid < r) ans += query2(pr,l,r);
    return ans;
}

void update1(int p,int l,int r,int c) {
    if(l <= tr[p].l && tr[p].r <= r) {
        tr[p].la1 += c;
        tr[p].s2 += 2 * c * tr[p].s1 + len(p) * c * c;
        tr[p].s1 += len(p) * c;
        rt;
    }
    push_down(p,len(p));int mid = tr[p].l + tr[p].r >> 1;
    if(l <= mid) update1(pl,l,r,c);
    if(mid < r ) update1(pr,l,r,c);
    push_up(p);
}

void update2(int p,int l,int r,int c) {
    if(l <= tr[p].l && tr[p].r <= r) {
        tr[p].la1 *= c; tr[p].la2 *= c;
        tr[p].s1 *= c;  tr[p].s2 *= c * c;
        rt;
    }
    push_down(p,len(p));int mid = tr[p].l + tr[p].r >> 1;
    if(l <= mid) update2(pl,l,r,c);
    if(mid < r ) update2(pr,l,r,c);
    push_up(p);
}

void solve()
{
    cin>>n>>m;
    fo(i,1,n) cin>>a[i];
    build(1,1,n);
    while(m -- ) {
        int op,l,r,x;cin>>op>>l>>r;
        if(op == 1) cout<<query1(1,l,r)<<endl;
        if(op == 2) cout<<query2(1,l,r)<<endl;
        if(op == 3) {cin>>x;update2(1,l,r,x);}
        if(op == 4) {cin>>x;update1(1,l,r,x);}
    }
    rt;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

这篇关于1008 数据结构 线段树 区间加法 区间乘法 区间平方和 区间和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！