退役选手只能来补数据结构的题解。
我们设当前情况下伤害 (d) 会触发 (cnt[d]) 次，那么 (displaystyle ans=frac{displaystyle sum_{i=L}^{R}cnt[i]}{R-L+1})
如果我们能求出来维护好的 (cnt) 数组的话，用树状数组做前缀和就能询问了。
维护的方法很简单，我们建一颗线段树，对于伤害 (d) ，如果当前场上存在血量在 (1) ~ (d) ,(d+1) ~ (2d) 。。。各至少一只，但不存在血量在 (kd+1) ~ ((k+1)d) 的怪，那么就把 (d) 放到响度按书上相应的区间。
当新来一个怪，沿着线段树把先相应的 (d) 取出来更新就行了。
时间复杂度是 调和级数套上线段树套上set（或者其他的可以维护插入删除的数据结构）， (O(nlog^3n))
考场上sb了，刚考完就就会了QAQ
可以尝试看代码理解。
#include<iostream>
#include<cstdio>
#include<set>
#define LL long long
using namespace std;
int n,m,top;
LL ans;
const int N=100010,M=1000010;
int L[N],R[N],zhan[N];
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
struct SZSZ
{
LL tr[N];
int lowbit(int x){return x&(-x);}
void add(int pos,int v)
{
for(;pos<=n;pos+=lowbit(pos))tr[pos]+=v;
}
LL ask(int pos)
{
int res=0;
for(;pos;pos-=lowbit(pos))res+=tr[pos];
return res;
}
}Ans,tong;
namespace XDS
{
#define lson (k<<1)
#define rson ((k<<1)|1)
set<int>s[N<<2];
set<int>::iterator it;
void Insert(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&r<=y)
{
s[k].insert(v);
return;
}
int mid=(l+r)>>1;
if(x<=mid)Insert(lson,l,mid,x,y,v);
if(mid+1<=y)Insert(rson,mid+1,r,x,y,v);
}
void updata(int k,int l,int r,int pos)
{
for(it=s[k].begin();it!=s[k].end();++it)zhan[++top]=*it;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)updata(lson,l,mid,pos);
else updata(rson,mid+1,r,pos);
}
void shan(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&r<=y)
{
s[k].erase(v);
return;
}
int mid=(l+r)>>1;
if(x<=mid)shan(lson,l,mid,x,y,v);
if(mid+1<=y)shan(rson,mid+1,r,x,y,v);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)Ans.add(i,1),XDS::Insert(1,1,n,1,i,i),L[i]=1,R[i]=i;
while(m--)
{
int opt=read();
if(opt==1)
{
int h=read();top=0;XDS::updata(1,1,n,h);
tong.add(h,1);
for(int i=1,v,l,r;i<=top;++i)
{
v=zhan[i];XDS::shan(1,1,n,L[v],R[v],v);
l=L[v];r=R[v];
while(1)
{
if(tong.ask(r)-tong.ask(l-1))Ans.add(v,1);
else {L[v]=l;R[v]=r;XDS::Insert(1,1,n,l,r,v);break;}
l=r+1;r=min(n,l+v-1);
if(l==n+1)break;
}
}
}
else
{
int l=read(),r=read();
printf("%lld
",Ans.ask(r)-Ans.ask(l-1));
}
}
return 0;
}