توضیح الگوریتم:

رتبه ای که فرد $i$ام برای خودش تخمین میزند را با $r_i$ نشان میدهیم.

لم1: به ازای $i>k$ داریم: $r_i \le k+1$

اثبات: از آنجا که این مقادیر از ورودی گرفته نمیشوند، در نتیجه این افراد برای تخمین رتبه ی خود به $k$ نفر جلوی خود نگاه میکنند. واضح است که کوچکترین رتبه ی انتخاب نشده بین این $k$ نفر با توجه به اصل لانه کبوتری حداکثر $k+1$ است. پس $r_i \le k+1$.

لم2: در دنباله ی $r_{k+1}, r_{k+2}, r_{k+3}, ...$ به ازای هر زیر دنباله ی متوالی $k+1$ تایی تمام اعداد 1 تا $k+1$ دقیقا یکبار دیده میشوند.

اثبات: با برهان خلف حکم را اثبات میکنیم. فرض کنید اینگونه نباشد. پس یعنی دو عدد $i$ و $j$ یافت میشوند بطوریکه: $k < i < j$ و $j-i \le k$ همچنین $r_i=r_j$ . فرد $j$ام را در نظر بگیرید. این فرد هنگامی که میخواسته رتبه ی خود رو تخمین بزند رتبه ی تخمینی فرد $i$ ام را پرسیده. پس نباید رتبه ای برای خود تخمین میزند با آن برابر باشد. در نتیجه فرض خلف باطل و حکم ثابت میشود.

لم3: به ازای $2k+2 \le i$ داریم: $r_i=r_{(i) mod (k+1) + k+1}$

با استقرا حکم را ثابت میکنیم:

پایه ی استقرا: فرض کنید $i=2k+2$. در این صورت با توجه به لم2 میدانیم در دنباله ی $r_{i-k-1}, r_{i-k}, ... ,r_{i-2} r_{i-1}$ تمام اعداد 1 تا $k+1$ هر کدام دقیقا یکبار دیده شده اند. از طرفی باز هم با توجه به لم2 میدانیم در دنباله ی $r_{i-k}, r_{i-k+1}, ... ,r_{i-1} r_i$ نیز هر کدام از اعداد 1 تا $k+1$ دقیقا یکبار دیده شده اند. از این دو موضوع به راحتی نتیجه میشود که $r_i=r_{i-k-1}$ پس $r_{2k+2}=r_{k+1}$

فرض استقرا : به ازای هر $j$ بطوری که $2k+2 \le j$ و $j< i$ داریم: $r_i=r_{(i) mod (k+1) + k+1}$

حکم استقرا: با استدلالی شبیه پایه ی استقرا به این میرسیم که$r_i=r_{i-k-1}$ و با توجه به فرض استقرا به این میرسیم که $r_i=r_{(i) mod (k+1) + k+1}$ و حکم ثابت میشود.

حال با توجه به لم3 برای یافتن $r_n$ کافیست که به رتبه ی تخمینی فرد $k+1$ام تا $2k+1$ ام را بیابیم. برای یافتن آن از سگمنت تری استفاده میکنیم و درختی دودویی با $k+1$ برگ میسازیم.

درخت را به گونه ای میسازیم که کوچکترین عدد بازه ی دلخواه را به ما نشان بدهد. البته ما در این سوال فقط از کوچکترین عدد کل برگ ها استفاده میکنیم. بهمین دلیل نیازی به تابع $query$ نداریم. ساخت درخت به این صورت است که در ابتدا $k$ عدد را از ورودی میگیریم. حال روی برگ $i$ ام عدد $j$ را به این صورت مینویسیم:

1. اگر عددی از ورودی هایمان $i$ بود $j=i$

2. در غیر اینصورت $j=\infty$

همچینین فرض کنید در هنگام گرفتن ورودی $i$ام اگر مقدار ورودیمان کوچکتر یا مساوی $k$ بود به مقدار $h_i$ یک واحد اضافه کنیم. (در ابتدا تمام $h_i$ ها را مساوی 0 قرار میدهیم.)

حال الگوریتم زیر را انجام میدهیم: (فرض کنید مقدار راس $i$ام درخت را با $t_i$ نشان دهیم)

1_ به ازای $i=k+1$ تا زمانی که $i \le 2k+1$ کار های زیر را انجام بده و به مقدار $i$ یک واحد اضافه کن:

1_1_مقدار $r_i=t_1$ ($t_1 $ ریشه ی درخت است و عدد روی آن کوچکترین عدد کل بازه است)

1_2_ به مقدار $h_{t_1}$ یک واحد اضافه کن و عدد برگ $t_1$ ام را برابر $\infty$ قرار بده.

1_3_ اگر $i-k$ امین ورودی ای که گرفتیم برابر $j$ باشد از مقدار $h_j$ یک واحد کم کن.

1_4_ اگر $h_j=0$ شد مقدار برگ $j$ام درخت را برابر $j$ قرار بده.

میبینید که به وسیله ی الگوریتم بالا میتوانیم به خواسته مان برسیم. چون هر بار که فردی از افراد $k+1$ ام تا $2k+1$ ام بخواهد رتبه اش را تخمین بزند کوچکترین برگ را میابد و آن را به عنوان رتبه میپذیرد. در ادامه مقادیر درخت آپدیت میشوند و اگر رتبه ای بین $k$ نفر جلوی فردی که میخواهیم رتبه اش را تخمین بزنیم باشد مقدار برگ متناظر آن را برابر $\infty$ قرار میدهیم. و در صورتی هم که رتبه ای انتخاب نشده باشد مقدار برگ متناظرش را برابر خودش قرار میدهیم.

در نهایت الگوریتم با پیچیدگی زمانی $O(klgk)$ ما را به جواب میرساند.

توضیحات کد:

در کد توابع build و update به ترتیب درخت را میساند و آپدیت میکنند.درون آرایه ی b مقادیر رتبه های تخمینی را قرار میدهیم. همچنین با توجه به لم1 مقادیر بزگ تر از $k+1$ در ورودی ها بدرد ما نمخوند و آنها را آپدیت نمکنیم.

مشاهده ی کد (C++)

من اینو با سگمنت تری نزدم

در واقع کاری که باید بکنی اینه که بیای و k+1 نفر بعد از k نفر اول رو حدس بزنی

بعد اثبات میشه کرد که این k+1 تا هی تکرار میشند. و این k+1 تا هم تخمینشون عددی بین 1 و k است.