Can anybody please explain me this code of question SEACO(september long challenge).

general
, ,
1

link text

2 
count = (count + B[i+1])%MOD;

Seems to me number of times common X will be executed, ONLY considering the commands executed from end till now. (i.e. not including command X in list right now)

B[i+1] = (count + 1)%MOD;

Including X in list, hence increasing count by 1.

if(t[i] == 1)
      {
        A[l[i] - 1] = (A[l[i] - 1] + B[i+1])%MOD;
        A[r[i]] = (A[r[i]] + MOD - B[i+1])%MOD;
        //printf("A[%d]=%d A[%d]=%d\n",l[i]-1,A[l[i]-1],r[i],A[r[i]]);
      }

Standard difference Array. Say your array is {5,10,11,2}. Then difference array arr[i+1]-arr[i] is {5,1,-9}. You know you know arr[1]=5. You can give arr[i] as-

arr[i]=arr[i-1]+diff[i-1];//Eg- arr[1]==arr[0]+diff[0]=5+5=10

B[l[i]-1] = (B[l[i]-1] + MOD - B[i+1])%MOD;
        B[r[i]]   = (B[r[i]] + B[i+1])%MOD;

Same technique for Type 2 commands as well.

And I think this was pretty much it of this code. In case your doubt persists, please check editorial, he has explained this approach there.

1 Like
3


check this link , i explained it step by step.

1 Like
4

Here why two array is considered instead of one ?
A[l[i] - 1] = (A[l[i] - 1] + B[i+1])%MOD;
A[r[i]] = (A[r[i]] + MOD - B[i+1])%MOD;

B[l[i]-1] = (B[l[i]-1] + MOD - B[i+1])%MOD;
B[r[i]] = (B[r[i]] + B[i+1])%MOD;

these 4 lines still i am unable to understand.

5

Array is is to store Type 1 queries, Array B is to store results of Type 2 queries, which in turn affect Type 1 queries (and are hence counted when Type==1).