教科书般的亵渎
qwq 在玩炉石传说的时候总是打不出教科书般的亵渎，于是他重新写了一个『炉石传说』，并且将亵渎的描述改为：「等概率随机在 ([L,R]) 中选出一个整数作为伤害值 (d)，对所有随从造成 (d) 点伤害，如果有随从死亡，则再次施放该法术，但伤害值不重新随机；如果没有随从死亡，则停止释放」，还去掉了场面上随从上限和亵渎最多触发 (14) 次的限制。qwq 不知道这个改版亵渎的效果怎么样，于是他打算进行一些测试，其中共进行 (m) 次如下类型的操作：
-
在场面上加入一个血量为 (h) 的随从，这里随从的血量都不能超过 (n)；
-
给定 ([L,R])，询问亵渎期望触发多少次；qwq 只会做操作 (1)，于是他就把操作 (2) 交给你啦。
对于 (100\%) 的数据，保证：(1le nle 10^5)，每次 (1) 操作有 (1le hle n)，每次 (2) 操作有 (1le Lle Rle n, 1le mle 10^6)；以上所有数值均为整数。
题解
http://jklover.hs-blog.cf/2020/05/30/Loj-6723-教科书般的亵渎/
整除分块 + 树状数组.
先考虑给定一个伤害值 (d) ,如何计算施放了多少次亵渎.
将每个随从生命值 (x) 换成需要被攻击的次数,即 (lfloor frac{x-1}{d} floor +1) ,就可以把 (d) 看作 (1) ,即每次造成 (1) 点伤害.
那么施放的次数就是最大的 (x) ,使得 (1,2,3,dots, x) 作为生命值在随从中都出现过,再加上 (1) .
考虑对于每个 (d) 都直接维护出答案,询问时利用树状数组查询 ([L,R]) 内的区间和.
每加入一个数 (x) 的时候,对它整除分块,它对一段区间 ([L,R]) 的贡献都是加入了一个数 (k) .
对每个 (k) 用 set 维护它在哪些位置是作为最大的 (x) ,将 ([L,R]) 内 (k-1) 作为最大的 (x) 的位置全部更新一遍.答案.
由于只有增加数字的操作,所以对于每个位置 (d) ,更新次数不会超过 (frac {n}{d}) .
时间复杂度 (O(nlog^2n+nsqrt n)) .
CO int N=1e5+10;
int n,m,buc[N],ans[N];
struct BIT{
#define lowbit(x) (x&-x)
int sum[N];
void insert(int p,int v){
for(;p<=n;p+=lowbit(p)) sum[p]+=v;
}
int query(int p){
int ans=0;
for(;p;p-=lowbit(p)) ans+=sum[p];
return ans;
}
}Buc,Ans; // prefix sum
set<int> pos[N];
void solve(int d){
Ans.insert(d,-ans[d]);
while(1){
int l=d*ans[d]+1,r=l+d-1;
l=min(l,n+1),r=min(r,n);
if(Buc.query(r)-Buc.query(l-1)) ++ans[d];
else break;
}
Ans.insert(d,ans[d]);
pos[ans[d]].insert(d);
}
void update(int l,int r,int k){
set<int>::iterator begin=pos[k].lower_bound(l),end=pos[k].upper_bound(r);
for(set<int>::iterator i=begin;i!=end;i=pos[k].erase(i)) solve(*i);
}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i) pos[0].insert(i);
while(m--){
if(read<int>()==1){
int x=read<int>();
if(buc[x]) continue;
buc[x]=1,Buc.insert(x,1);
for(int l=1,r;l<=x-1;l=r+1){
r=(x-1)/((x-1)/l);
update(l,r,(x-1)/l);
}
update(x,n,0);
}
else{
int l=read<int>(),r=read<int>();
printf("%d
",Ans.query(r)-Ans.query(l-1)+r-l+1);
}
}
return 0;
}