In this HackerEarth A range function problem solution You are given an array A of N integer elements.
You are also given Q queries where each query is one of the following types:
1ival: Update value of element at i-th index to val i.e. A[i] = val
2LR: Find the value of function sigma(i=L,R)sigma(j=i,R)sigma(k=i,j)A[k].
HackerEarth A range function problem solution.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
string multiply(string num1, string num2)
{
int len1 = num1.size();
int len2 = num2.size();
if (len1 == 0 || len2 == 0)
return "0";
vector<int> result(len1 + len2, 0);
int i_n1 = 0;
int i_n2 = 0;
for (int i=len1-1; i>=0; i--)
{
int carry = 0;
int n1 = num1[i] - '0';
i_n2 = 0;
for (int j=len2-1; j>=0; j--)
{
int n2 = num2[j] - '0';
int sum = n1*n2 + result[i_n1 + i_n2] + carry;
carry = sum/10;
result[i_n1 + i_n2] = sum % 10;
i_n2++;
}
if (carry > 0)
result[i_n1 + i_n2] += carry;
i_n1++;
}
int i = result.size() - 1;
while (i>=0 && result[i] == 0)
i--;
if (i == -1)
return "0";
string s = "";
while (i >= 0)
s += std::to_string(result[i--]);
return s;
}
string add(string str1, string str2)
{
if (str1.length() > str2.length())
swap(str1, str2);
string str = "";
int n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
for (int i=0; i<n1; i++)
{
int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
for (int i=n1; i<n2; i++)
{
int sum = ((str2[i]-'0')+carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
if (carry)
str.push_back(carry+'0');
reverse(str.begin(), str.end());
return str;
}
string sub(string str1, string str2)
{
string str = "";
int n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
for (int i = 0; i < n2; i++) {
int sub
= ((str1[i] - '0') - (str2[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
for (int i = n2; i < n1; i++) {
int sub = ((str1[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
reverse(str.begin(), str.end());
return str;
}
string seg[400005][3];
string a[100000 + 1];
void build(int l, int r, int index, int ind)
{
if(l == r){
if(ind == 0)
seg[index][ind] = a[l];
else if(ind == 1)
{
seg[index][ind] = multiply(to_string(l), a[l]);
}
else if(ind == 2)
seg[index][ind] = multiply(to_string(l*l), a[l]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*index + 1, ind);
build(mid + 1, r, 2*index + 2, ind);
seg[index][ind] = add(seg[2*index + 1][ind], seg[2*index + 2][ind]);
}
void update(int l, int r, int index, int ind, int x)
{
if(r < x or x < l) return;
if(l == r and l == x){
if(ind == 0)
seg[index][ind] = a[l];
else if(ind == 1)
seg[index][ind] = multiply(to_string(l), a[l]);
else if(ind == 2)
seg[index][ind] = multiply(to_string(l*l), a[l]);
return;
}
int mid = (l + r) >> 1;
update(l, mid, 2*index + 1, ind, x);
update(mid + 1, r, 2*index + 2, ind, x);
seg[index][ind] = add(seg[2*index + 1][ind], seg[2*index + 2][ind]);
}
string query(int l, int r, int index, int ind, int ql, int qr)
{
if(r < ql or qr < l) return "0";
if(ql <= l and r <= qr) return seg[index][ind];
int mid = (l + r) >> 1;
string first = query(l, mid, 2*index + 1, ind, ql, qr);
string second = query(mid + 1, r, 2*index + 2, ind, ql, qr);
return add(first, second);
}
string cal(string temp)
{
int len = temp.size();
string answer = "";
if(temp[0] == '0')
{
int i = 0;
while(i < len and temp[i] == '0')
{
i++;
}
for(int j = i ; j < len ; j++)
{
answer += temp[j];
}
}
else{
answer = temp;
}
return answer;
}
void solve(){
int n;
cin >> n;
assert(1 <= n and n <= 100000);
for(int i = 1 ; i <= n ; i++){
int tot;
cin >> tot;
assert(1 <= tot and tot <= 1000000);
a[i] = to_string(tot);
}
for(int i = 0 ; i < 3 ; i++){
build(1, n, 1, i);
}
int q;
cin >> q;
assert(1 <= q and q <= 1000);
while(q--){
int type;
cin >> type;
assert(1 <= type and type <= 2);
if(type == 1){
int ind;
cin >> ind;
assert(1 <= ind and ind <= n);
int num;
cin >> num;
assert(1 <= num and num <= 1000000);
string val;
val = to_string(num);
a[ind] = val;
for(int i = 0 ; i < 3 ; i++){
update(1, n, 1, i, ind);
}
}
else if(type == 2){
int l;
int r;
cin >> l >> r;
assert(1 <= l and l <= r and r <= n);
string temp = multiply(to_string(r + l), query(1, n, 1, 1, l, r));
temp = add(temp, multiply(to_string(r + 1), query(1, n, 1, 0, l, r)));
temp = sub(temp, query(1, n, 1, 2, l, r));
temp = sub(temp, multiply(to_string(r*l + l), query(1, n, 1, 0, l, r)));
cout << cal(temp) << endl;
}
}
}
signed main(){
int t;
cin >> t;
assert(1 <= t and t <= 10);
while(t--){
solve();
}
}
0 Comments