You have an array A containing N integers. You are also given Q updates, of the following form:
L \ \ R: add 1 to A_L, -1 to A_{L+1}, 1 to A_{L+2}, and so on
Find the sum of A after all Q updates.
EXPLANATION:
Directly performing an update takes \mathcal{O}(N) time, so performing every update would be \mathcal{O}(NQ), which is too slow.
Instead, let’s make a couple of observations about the process.
Let S denote the sum of A. How does S change after an update?
If the length of the segment we update is even, then S changes by 1 + (-1) + 1 + (-1) + \ldots + 1 + (-1) = 0
If the segment has odd length, S changes by 1 + (-1) + \ldots + 1 + (-1) + 1 = 1
This gives us a rather simple solution that runs in \mathcal{O}(N+Q):
Compute S, the initial sum of array A.
Then, for each update:
If the length of the segment [L, R] is even, S doesn’t change.
Otherwise, S increases by 1.
Finally, print the value of S.
Note that there are ways to actually simulate all the updates fast enough using lazy segment trees or sweeplines, but they are completely unnecessary to solve this task.
TIME COMPLEXITY
\mathcal{O}(N + Q) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
while q > 0:
l, r = map(int, input().split())
s += l%2 == r%2
q -= 1
print(s)
sorry to bother u guys but can u find the logical error in my code i m not able to code my thinking i guess. #include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n=0,q=0;
cin>>n>>q;
int a[n];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
while(q–)
{ int l=0,r=0;
cin>>l>>r;
for(int j=l;j<=r;j++)
{
if(j%2==0)
{
a[j]=a[j]-1;
}
else if(j%2!=0)
{
a[j]=a[j]+1;
}
}
}
long long int sum=0;
for(int k=1;k<=n;k++)
{
sum=sum+a[k];
}
cout<<sum<<endl;
}
The length of subarray [L, R] is R-L+1. If this number is odd, then R-L must be even, i.e, L and R must have the same parity. So it’s enough to compare the parities of L and R, which is what that line of code does.
Your code seems to be a plain bruteforce, which for each query changes every element from L to R.
While this approach is logically correct, please do read the first line of the editorial: “Directly performing an update takes \mathcal{O}(N) time, so performing every update would be \mathcal{O}(NQ), which is too slow.”
The crux of solving this problem is finding a way to optimize this approach.
they aren’t not neede — find the sum of the array and since in the subarray ur add +1 and sub -1 alternatively so if even queries +=0 at the end but if queries (l==r) or are odd then +1 at the end