正题

题目大意

有\(n\)个数字开始都是\(0\)，要求有\(q\)次操作。

1. 新建一个观测员，观测其中的\(k\)个数，当这\(k\)个数从此刻开始变化量不小于\(t\)时观测结束。
2. 将第\(i\)个数加\(v\)，并输出此时观测结束的观测员编号。

强制在线

\(1\leq n,q\leq 2\times 10^5,1\leq k\leq 3,1\leq t,v\leq 10^6\)

解题思路

考虑从\(k\)入手，根据鸽笼原理，一个观测员观测结束当且仅当存在它观测的一个数字\(a\geq \lceil\frac{t}{k}\rceil\)，注意到此时已经至少填充了\(\lceil\frac{t}{k}\rceil\)。

所以我们可以对于每个它观测的数字以\(\lceil\frac{t}{k}\rceil\)为界，当到倒打这个界时，我们直接重新根据现在的数字再来一次，也就是把\(t\)剩余的部分再分成\(k\)份丢回去。

一直这样做知道合法为止，此时每次会至少令\(t=\frac{k-1}{k}t\)，所以这样的次数应该为\(\log_{\frac{k}{k-1}}t\)。

用个\(set\)维护就好了，时间复杂度：\(O(q\log_{\frac{k}{k-1}}tk\log q)\)

code

#include
#include
#include
#include
#include
#include
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=2e5+10;
ll n,m,cnt,a[N],t[N];
vector ans,q[N],c[N];
set >s[N];
void update(ll x){
	ll sum=0;
	for(ll i=0;i=t[x])ans.push_back(x);
	else{
		for(ll i=0;i k=*s[p].begin();
				if(a[p]>=k.first)update(k.second);
				else break;
			}
			printf("%lld",las=ans.size());
			sort(ans.begin(),ans.end());
			for(ll i=0;i