### I_love_Leyeli_Meredova's blog

By I_love_Leyeli_Meredova, history, 7 weeks ago,

Hello Codeforces!

Today I was solving one problem from codeforces edu

My code

Can someone tell me how I can solve this problem? (Sorry for my English)

Thanks!

 » 7 weeks ago, # | ← Rev. 2 →   0 Let's change the problem statement, find the prefix where the sum is k+1(since it starts counting from 0), now it's a famous problem with segment trees, and try to solve it for the general case(not 01) assuming there always exists a prefixbut for this problem in particular(I'm not going to solve the question above but give another approach(which is kinda similar)) Build logicmaintain a segment tree where seg[idx] = the sum of its range and it's obvious that where r-l < 1 seg[idx] = a[l] get logicI'm just assuming the counting starts from 1(increment k), you start from the root, if seg[left] <= k traverse to left otherwise right, and if (node.right — node.left) was less than 1 you've found the element.for the update function, it's like incrementing a[i] by 1,-1 which you should be able to do, but in case not: update logicstarting form the root, if that element was in the left child u traverse to that otherwise right, when (r — l < 1) you simply do a[i] ^= 1(toggle it), and rebuild the segment tree from the bottom.smth like this: void update(ll k, pii node = {0, n-1}, ll idx = 1){ // handle if k is not in range, not gonna code it. if (k <= node.first && k >= node.second){ // if we're at k a[k] ^= 1; seg[idx] = a[k]; return; } ll mid = (node.first + node.second) / 2; // run update for those 2 new ranges seg[idx] = seg[idx*2] + seg[idx*2+1]; } 
•  » » 7 weeks ago, # ^ |   0 thank you but everything you said I have already done in my program. codeforces output my outputyou can check it
•  » » » 7 weeks ago, # ^ |   +10 I corrected and got accepted with your code. Corrected Find Function int find(int k) { return find(k, 0, 0, size); } 
•  » » » » 7 weeks ago, # ^ |   0 Oh my God, thank you, but could you explain to me why this is the right
•  » » » » » 7 weeks ago, # ^ |   0 the since the big find function(the actual one) returns a number, in the second one you're calling it and it does it's job perfectly fine, but you're not returning it.take this: ll add(ll i, ll j) { return i + j; } add(10, 15); and expecting the code to output 25,instead you should've used cout << add(10, 15) << endl;
•  » » » » » » 7 weeks ago, # ^ |   0 thanks