0

这是 SPOJ“SEGSQRSS - 带段树的平方和”的问题，该问题的链接是http://www.spoj.com/problems/SEGSQRSS/我正在尝试使用惰性传播但找不到正确的解决方案，任何人都可以在我出错的地方提供帮助。

#include <map>
#include <set>
#include <math.h>
#include <string>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
#define mod 1000000007
#define ll long long int
#define all(c) c.begin(),c.end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
// it uses lazy propagation
struct seg
{
    ll x;// which stores the value of the 2*(sum of the elements of the segment)
    ll sum;// stores the sum of the square of the elements of the segment
};
seg tree[2000050];
ll arr[100005],lazyadd[2000050],lazycha[2000050];
ll query_tree(ll node,ll a,ll b,ll i,ll j);
void build_tree(ll node,ll a,ll b);
void build_tree(ll node,ll a,ll b)
{
    if(a>b)return ;
    if(a==b)
    {
        tree[node].x=2*arr[a];
        tree[node].sum=arr[a]*arr[a];
        return ;
    }
    build_tree(2*node,a,a+((b-a)/2));
    build_tree(2*node+1,1+a+((b-a)/2),b);

    tree[node].x=tree[2*node].x+tree[2*node+1].x;
    tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;
    return ;
    }

ll query_tree(ll node,ll a,ll b,ll i,ll j)
{
    if(a > b || a > j || b < i) return 0;
    ll ans;
    ll mid=(a+b)/2;
    if((lazyadd[node]!=0)||(lazycha[node]!=0))
    {
        // this is for type 0
        if(i!=j){
        if(lazycha[node]!=0){
        tree[2*node].sum=(mid-a+1)*lazycha[node]*lazycha[node];
        tree[2*node].x=(mid-a+1)*lazycha[node]*2;
        tree[2*node+1].sum=(b-mid)*lazycha[node]*lazycha[node];
        tree[2*node+1].x=(b-mid)*lazycha[node]*2;
        lazycha[2*node]=lazycha[2*node]+lazycha[node];
        lazycha[2*node+1]=lazycha[2*node+1]+lazycha[node];
        }

        // this is for type 1
        if(lazyadd[node]!=0){
        tree[2*node].sum=tree[2*node].sum+tree[2*node].x*lazyadd[node]+(mid-a+1)*lazyadd[node]*lazyadd[node];
        tree[2*node].x=tree[2*node].sum+(mid-a+1)*lazyadd[node]*2;
        tree[2*node+1].sum=tree[2*node+1].sum+tree[2*node+1].x*lazyadd[node]+(b-mid)*lazyadd[node]*lazyadd[node];
        tree[2*node+1].sum=tree[2*node+1].sum+(b-mid)*lazyadd[node]*2;

        lazyadd[2*node]=lazyadd[2*node]+lazyadd[node];
        lazyadd[2*node+1]=lazyadd[2*node+1]+lazyadd[node];

      }

        }
        lazyadd[node]=0;
        lazycha[node]=0;
    }

    if((i<=a)&&(b<=j))return tree[node].sum;

    ll ans1=query_tree(2*node,a,a+((b-a)/2),i,j);
    ll ans2=query_tree(2*node+1,a+((b-a)/2)+1,b,i,j);
    ans=ans1+ans2;
    return ans;
}

void update_tree(ll node,ll a,ll b,ll i,ll j,ll value,ll type)
{
    if(a > b || a > j || b < i) return ;

    ll mid=(a+b)/2;
    if((lazyadd[node]!=0)||(lazycha[node]!=0))
    {
        // this is for type 0
        if(i!=j){
        if(lazycha[node]!=0){
        tree[2*node].sum=(mid-a+1)*lazycha[node]*lazycha[node];
        tree[2*node].x=(mid-a+1)*lazycha[node]*2;
        tree[2*node+1].sum=(b-mid)*lazycha[node]*lazycha[node];
        tree[2*node+1].x=(b-mid)*lazycha[node]*2;
        lazycha[2*node]=lazycha[2*node]+lazycha[node];
        lazycha[2*node+1]=lazycha[2*node+1]+lazycha[node];
        }

        // this is for type 1
        if(lazyadd[node]!=0){
        tree[2*node].sum=tree[2*node].sum+tree[2*node].x*lazyadd[node]+(mid-a+1)*lazyadd[node]*lazyadd[node];
        tree[2*node].x=tree[2*node].sum+(mid-a+1)*lazyadd[node]*2;
        tree[2*node+1].sum=tree[2*node+1].sum+tree[2*node+1].x*lazyadd[node]+(b-mid)*lazyadd[node]*lazyadd[node];
        tree[2*node+1].sum=tree[2*node+1].sum+(b-mid)*lazyadd[node]*2;

        lazyadd[2*node]=lazyadd[2*node]+lazyadd[node];
        lazyadd[2*node+1]=lazyadd[2*node+1]+lazyadd[node];

      }

        }
        lazyadd[node]=0;
        lazycha[node]=0;
    }

    if((i<=a)&&(b<=j))
    {
        if(type==0)
        {
            tree[node].sum=(b-a+1)*value*value;
            tree[node].x=(b-a+1)*value*2;
            lazycha[node]+=value;
            return;
        }
        else if(type==1)
        {
            tree[node].sum=tree[node].sum+tree[node].x*value+(b-a+1)*value*value;
            tree[node].x+=(b-a+1)*value*2;
            lazyadd[node]+=value;
            return;
        }
    }



    update_tree(2*node,a,a+((b-a)/2),i,j,value,type);
    update_tree(2*node+1,1+a+((b-a)/2),b,i,j,value,type);
    tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;

    }

int main()
{
    ll t,x,n,c,i,j,v;
    cin>>t;
    for(x=1;x<=t;x++){
            memset(lazyadd,0,sizeof(lazyadd));
            memset(lazycha,0,sizeof(lazycha));
    ios_base::sync_with_stdio(0);//this is the boost :)
    scanf("%lld%lld",&n,&c);
    for(i=1;i<=n;i++)scanf("%lld",&arr[i]);//cin>>arr[i];
    build_tree(1,1,n);
    cout<<"Case "<<x<<endl;
    while(c--)
    {
        int type;
        scanf("%d",&type);
        if(type==2)
        {
            scanf("%lld%lld",&i,&j);
            printf("%lld\n",query_tree(1,1,n,i,j));
        }
        else
        {
            scanf("%lld%lld%lld",&i,&j,&v);
            update_tree(1,1,n,i,j,v,type);
        }
    }
  }
    return 0;
}

提前致谢。

4

0 回答 0