回复 @LadyLex :
渣渣辉太神啦

@Hzoi_Ivan 我那个斜率的找不到了……

板子题23333

回复 @LadyLex :
渣渣辉太神啦

5 4 2
3
5 1
5 5
4 4
4
1 1
2
1 3
2
12.07
12.07
好多代码都跑不过……

做个这题真的是把能踩的坑都踩了一遍，第一次权值没置成0，第二次分余数的时候忘了跳过自己。。。。
写个这么个水题用了半个小时。。可以回炉了。。
顺便粘一下代码
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
freopen("icow.in","r",stdin);
freopen("icow.out","w",stdout);
int n,m,q[1005],max=0,qwq,yu,zheng,k,aa[1005],nn=0;
cin>>n>>m;
k=n-1;
for(int i=1;i<=n;i++)
cin>>q[i];
for(int i=1;i<=m;i++)
{for(int i=1;i<=n;i++)
{if(q[i]>max)
{qwq=i;
max=q[i];}}
max=0;
nn++;
aa[nn]=qwq;
yu=q[qwq]%k;
zheng=q[qwq]/k;
q[qwq]=0;
for(int i=1;i<=n;i++)
{if(i!=qwq)
q[i]+=zheng;}
for(int i=1;i<=yu;i++)
{if(i!=qwq)
q[i]++;
else
yu++;
}
/*for(int i=1;i<=n;i++)
{cout<<q[i]<<' ';
if(i%n==0)cout<<endl;}*/}
for(int i=1;i<=m;i++)
cout<<aa[i];
return 0;
}

mdzz这数据……等差数列求和要手动爆long long，calc函数要传int

竟然跑得比我本地还慢

1
3 2
0.5000 2
0.3000 3
0.9000 1

论忽视题目条件的危害……

感谢 @3725

可能爆搜比带空串转移的DFA匹配快一点……

数据没传对，已修复

回复 @@@@ :
您真是个天才。1A.

记的用 multiset ，不能用set，实测WA3个点。

强行map

想到了严格 $O(n\log(n))$ 的解法:
首先我们用单调栈或者 $\text{std::set}$ 预处理出每个值 $a_l$ 右边第一个不大于它的值 $a_r$ 的位置, 这样的话区间 $(l,r)$ 就是以 $l$ 为左端点的合法区间的右端点的可能位置.
然后我们根据 $r$ 的大小升序排序, 同时使用一个树状数组维护 $a_i$ 后大于前面所有点的点值 $a_r$ 与位置 $r$ (若点值相等取下标更小的), 将点逐个加入树状数组, 在加入到某个 $(l,r)$ 的 $r-1$ 的位置的时候就可以查询 $l$ 得到最大的右端点.
总时间复杂度中, 预处理是 $O(n)$ 或者 $O(n\log(n))$ 的, 最后树状数组中每个点都至少要插入/查询一次, 树状数组部分总时间复杂度 $O(n\log(n))$, 整个程序时间复杂度为 $O(n\log(n))$.
最后注意特判 $ans=0$ 的情况就行了
可以参考标程理解一下

线段树分治
Q可能等于0

莫队要开O2才能过，我太蒟蒻了

BZOJ AC，COGS50分。。求神犇指错。。。（代码略丑