正题
题目大意
有\(n\)个数字开始都是\(0\),要求有\(q\)次操作。
- 新建一个观测员,观测其中的\(k\)个数,当这\(k\)个数从此刻开始变化量不小于\(t\)时观测结束。
- 将第\(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<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<cmath>
#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<ll> ans,q[N],c[N];
set<pair<ll,ll> >s[N];
void update(ll x){
ll sum=0;
for(ll i=0;i<q[x].size();i++){
ll y=q[x][i];sum+=a[y];
s[y].erase(mp(c[x][i],x));
}
if(sum>=t[x])ans.push_back(x);
else{
for(ll i=0;i<q[x].size();i++){
ll y=q[x][i];
c[x][i]=a[y]+ceil((double)(t[x]-sum)/q[x].size());
s[y].insert(mp(c[x][i],x));
}
}
return;
}
signed main()
{
// freopen("obs.in","r",stdin);
// freopen("obs.out","w",stdout);
scanf("%lld%lld",&n,&m);
ll las=0;
while(m--){
ll op;
scanf("%lld",&op);
if(op==1){
ll k,sum=0;++cnt;
scanf("%lld%lld",&t[cnt],&k);t[cnt]^=las;
for(ll i=0,x;i<k;i++){
scanf("%lld",&x);x^=las;
q[cnt].push_back(x);sum+=a[x];
c[cnt].push_back(a[x]+ceil((double)t[cnt]/k));
s[x].insert(mp(c[cnt][i],cnt));
}
t[cnt]+=sum;
}
else{
ans.clear();
ll p,w;
scanf("%lld%lld",&p,&w);
p^=las;w^=las;a[p]+=w;
while(!s[p].empty()){
pair<ll,ll> 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<ans.size();i++)
printf(" %lld",ans[i]);
putchar('\n');
}
}
return 0;
}