Given an array of integers A1,A2,…,AN and the initial value of all elements are 0. Now you are given M queries, each belongs to one of three following types:
0 x y: Find the sum of all elements from index x to index y modulo 109+7
1 x y: Add 1×2×3 to Ax, add 2×3×4 to Ax+1, …, add (i+1)×(i+2)×(i+3) to Ax+iand so on until Ay
2 x y: Subtract 1×2×3 from Ax, subtract 2×3×4 from Ax+1, …, subtract (i+1)×(i+2)×(i+3) from Ax+i and so on until Ay
Input
The first line contains two integers N and M (1≤N,M≤10^5) — the size of the array and the number of queries, respectively.
Each of the next M lines containts three integers t x y denotes type and range of the query.
Output
For each query of type 0, print the required answer in a single line.
Sample testcase:
Input
8 4
1 1 8
0 2 8
2 4 6
0 5 6
Ouput
1974
462
Sample Clarification
In the example below:
After the first query, the array is [6,24,60,120,210,336,504,720]
The answer for the second query is 24+60+120+210+336+504+720=1974
After the third query, the array is [6,24,60,114,186,276,504,720]
The answer for the last query is 186+276=462
The above is the subject and the bottom is my code. I don't understand why it wrong answer. Can you explain to me? Thank you!
#include <bits/stdc++.h> using namespace std;
define ll long long
define mod 1000000007
ll arr[100006]; ll t[262200]; ll lazy[262200];
void build(ll node, ll a, ll b) { if(a>b) return; if (a==b) { t[node]=arr[a]; return; }
build(node*2, a, (a+b)/2); build(node*2+1,(a+b)/2+1,b); t[node]=t[node*2]+t[node*2+1];
}
ll query(ll node, ll a, ll b, ll i, ll j) { if(a>b||a>j||b<i) return 0; if (lazy[node] !=0 ) { t[node]+= (lazy[node]*(b-a+1)); if (a!=b) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; }
if (a>=i && b<=j) return t[node]; ll q1=query(node*2, a, (a+b)/2, i, j); ll q2=query(node*2+1, (a+b)/2+1, b, i, j); return q1+q2;
}
void update(ll node, ll a, ll b, ll i, ll j, ll inc) { if(a>b) return; if (lazy[node]!=0) { t[node]+=lazy[node]*(b-a+1); if (a!=b) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; } if(a>b||a>j||b<i) return;
if (a>=i && b<=j) { t[node]+= (inc*(b-a+1)) % mod; if (a!=b) { lazy[node*2]+= (inc % mod); lazy[node*2+1]+= (inc % mod); } return; } update(node*2, a, (a+b)/2, i, j, inc); update(node*2+1, (a+b)/2+1, b,i, j, inc); t[node] = t[node*2] + t[node*2+1];
} int main(int argc, char const *argv[]) { ios_base::sync_with_stdio(0); ll t,n,m,q,p,a;
cin>>n>>m; build(1,0,n-1); memset(lazy, 0, sizeof(lazy)); while(m--) { cin>>a>>p>>q; if (a==0) { cout<< query(1,0,n-1,p-1,q-1) % mod<<endl; } else if(a == 1) { ll cnt = 0, res; for(int t = p-1; t <= q-1; t++){ res = ((cnt + 1) * (cnt + 2) * (cnt + 3)) % mod; update(1,0,n-1,t,t,res); cnt++; } } else if(a == 2) { ll cnt = 0, res; for(int t = p-1; t <= q-1; t++){ res = ((cnt + 1) * (cnt + 2) * (cnt + 3)) % mod; update(1,0,n-1,t,t, -res); cnt++; } } } return 0;
}