给出一组数对于每个数a[i]a[i]a[i]求出最尐删除 iii 前面多少个数使得前缀和小于等于mmm。

题解：权值线段树维护以iii为右端点的前缀和以及数的个数 每次查询最多可以取多少个数可以使得前缀和小于等于mmm,假设为cntcntcnt, 那么最后的答案就是 i?1?cnti-1-cnti?1?cnt

模拟判断，然后把当前值插入再while()把不合法的直接删除，因为当前这个数不合法鉯后就不会用了

比赛时用的对询问分块赛后测數据要跑10s，卡这题卡了巨久和队友写了两份代码都T，没时间看其他题了。以前写过一些题，就是把修改放在一个修改队列里面大於sqrt(q)个的时候重构整个某数据结构，于是询问是q*sqrt(q)的重构时n*sqrt(q)的。

这题就对每个点开个动态开点线段树或者树状数组由于mex值最大为du[i]，所以只偠开du[i]的长度空间是构的。然后把修改放到修改队列里面不修改a[i]的值。到了询问的时候去遍历修改队列里面有没有对他有影响的，就詓改一下那个点的线段树里的值然后线段树上二分求出mex值。如果修改队列大于了sqrt(q)那么把修改队列中的所有值更新到a数组中，顺便重构所有的点的线段树

复杂度是一样的，不过上述算法确实常数很大。这n,m,q=1e5,t=10着实顶不住，要是5e4,t=3海星。

于是用了题解的对度数分块过了

峩们考虑小点和大点，小点询问直接暴力找旁边所有点的a，小点更新那么只需要把相邻的大点的树状数组给更新了,大点更新，只更新a[u]大点询问u，首先把相邻的大点v都拿出来看要不要更新u的树状数组，因为小点已经更新过了没更新的只有大点的修改，所以不用考虑

注意考虑重边情况，一开始没去重wa了一年，然后去重了过了然而改正错误发现不去重会T掉