today i attended the codeforces division 2 169 and came across this question.. http://mirror.codeforces.com/contest/276/problem/C I saw most of the red and yellow coder used the logic..
for(int i=0;i<k;i++){ cin>>x1>>x2; arr[x1-1]++; arr[x2]--; } for(int i=0;i<n;i++) arr[i]+=arr[i-1];
I was really shocked and I am unable to understand how so many of people knew this technique.. Is this any standard algorihtm or something??..
Well, it is called delta encoding.
Thank you so much friend.. :) good to learn new concepts in this competition.. hope i wont forget..
dude is it also called binary indexed trees.?..i tried looking for delta encoding...but didnt get anything relevant
No, it's not.
How couldn't you find anything?! He even gave you a link
Кто-нибудь знает материал об этом на русском языке?
Нормального материала по применению таких техник в СП вроде как и нет. До них либо додумываются самостоятельно, либо узнают у более опытных товарищей.
В-общем, чтобы понять подобные вещи, просто решай побольше задач. Проверено на собственном опыте :).
UPD. И читай чужие решения.
Second cycle starts from 0, but index i — 1 uses. Here's might be problems. I guess it better starts from 1.