Toph: Another Update-Query Problem

Problem Link : https://toph.co/p/another-update-query-problem

Solution Idea:

    The main idea behind the solution of this problem is simplifying the equation. For a query operation we need the answer of this equation-
    1A_l + (1+d)A_l+1 + (1+2d)A_l+2 + (1+3d)A_l+3 + … + (1+(r-l)d)A_r
    Now let the query range l r is 1 3. and the given array is A=[a1,a2,a3,a4,…]

    So our quation will be-
    1*a1 + (1+d)*a2 + (1+2d)*a3 + (1+3d)*a4
    = a1 + a2 + d*a2 + a3 + 2d*a3 + a4 + 3d*a4
    = (a1+a2+a3+a4) + d*(a2+ 2*a3 + 3*a4)

    Now We can see that first part of this equation is only sum query which can be done using a segment tree and for 2nd part we can use a trick. We can pree calculate the sequence like this-
    1*a1 + 2*a2 + 3*a3 + 4*a4 + 5*a5 + 6*a6 + 7*a7 + ……
    When we need the 2nd part of the equation we can use this equation. We can get the 2nd part of the equation from this equation by this way-
    (2*a2 + 3*a3 + 4*a4)-(a2+a3+a4) = (a2+ 2*a3 + 3*a4).

    Now the above equation is also only a sum equation. We can apply any range sum query or range sum update on this equation and the the first sum equation.

    So if we store this two equation in two segment tree then we can perform range update or query on the segment tree and get any range sum query from the segment tree and using the equation we can answer each query of the problem correctly.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
    ll sum, ssum, prop;
    data()
    {
        sum=0,ssum=0,prop=0;
    }
};

data tree[3*mx];

ll ara[mx];

ll interval_sum(ll b, ll e)
{
    ll x=(e*(e+1))/2;
    ll y=(b*(b-1))/2;
    return (x-y+MOD)%MOD;
}

void push_down(int n, int b, int e)
{
    if(tree[n].prop)
    {
        segment_tree;
        tree[l].sum+=((mid-b+1)*tree[n].prop)%MOD;
        tree[r].sum+=((e-mid)*tree[n].prop)%MOD;
        tree[l].ssum+=(interval_sum(b,mid)*tree[n].prop)%MOD;
        tree[r].ssum+=(interval_sum(mid+1,e)*tree[n].prop)%MOD;
        tree[l].prop+=tree[n].prop%MOD;
        tree[r].prop+=tree[n].prop%MOD;
        tree[l].sum%=MOD;
        tree[l].ssum%=MOD;
        tree[l].prop%=MOD;
        tree[r].sum%=MOD;
        tree[r].ssum%=MOD;
        tree[r].prop%=MOD;
        tree[n].prop=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].sum=ara[b]%MOD;
        tree[n].ssum=((ll)b*ara[b])%MOD;
        tree[n].prop=0;
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
    tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
    tree[n].prop=0;
}

void update(int n, int b, int e, int i, int j, ll val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].sum+=((ll)(e-b+1)*val)%MOD;
        tree[n].ssum+=(interval_sum(b,e)*val)%MOD;
        tree[n].prop+=val;
        tree[n].sum%=MOD;
        tree[n].ssum%=MOD;
        tree[n].prop%=MOD;
        return;
    }
    push_down(n,b,e);
    segment_tree;
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
    tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
}

data query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return data();
    if(b>=i && e<=j)
        return tree[n];
    push_down(n,b,e);
    segment_tree;
    data p=query(l,b,mid,i,j);
    data q=query(r,mid+1,e,i,j);
    data ret;
    ret.ssum=(p.ssum+q.ssum)%MOD;
    ret.sum=(p.sum+q.sum)%MOD;
    return ret;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,q;
        sff(n,q);
        loop1(i,n) sfl(ara[i]);
        init(1,1,n);
        LINE_PRINT_CASE;
        while(q--)
        {
            int a,b,c,d;
            sfff(a,b,c);
            sf(d);
            if(a==1)
            {
                update(1,1,n,b,c,d);
            }
            else
            {
                data ret=query(1,1,n,b,c);
                ll sum=ret.sum;
                ret=query(1,1,n,b+1,c);
                ll ssum=(ret.ssum-(((ll)(b)*ret.sum)%MOD)+MOD)%MOD;
                ssum*=(ll)d%MOD;
                ssum%=MOD;
                ll ans=(sum+ssum)%MOD;
                printf("%lld\n",ans);
            }
        }

    }

    return 0;
}

Advertisements