【Ynoi2015】我回来了
线段树，树状数组。
qwq
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩
题目大意：
给定一个数列，初始为空。
令 $a_i$ 表示那个数列中的数除以 $i$ 下取整后的 $\mathrm{mex}$。
有两个操作：
- 给数列中插入一个数。
- 对 $a_i$ 求区间和。
题解：
转化一下题意，伤害值为 $d$ 时的答案就是那些随从的血量 $-1$ 后再整除 $d$ 然后取 $\mathrm{mex}$。
对于 $d=1\sim n$ 时，这个 $\mathrm{mex}$ 最大的值分别为 $n,\frac n 2,\frac n 3,\cdots,1$。
可以发现它们加起来是 $O(n\log n)$ 级别的。
所以我们考虑每次插入一个数后，找到哪些 $\mathrm{mex}$ 会变化，然后暴力给它加。加的次数不超过 $O(n\log n)$。
并且显然插入同一个数是没意义的，所以有效果的插入只有 $n$ 次。
那么我们需要较为精确地找出，每次插入后，哪些位置的 $\mathrm{mex}$ 会变化。
对于一个 $d$，它当前的 $\mathrm{mex}$ 是 $k$，那么让它的 $\mathrm{mex}$ 变化需要插入 $[dk+1,dk+k]$ 中的任何一个数。
对于每个 $d$ 都有这么一个对应的区间，且一个 $d$ 对应的不同区间个数为 $\frac n d$。也就是说这样的区间总数也是 $O(n\log n)$ 的。
我们考虑弄一个东西，使得插入 $h$ 时，能找到需求区间包含 $h$ 的所有 $d$。
用类似线段树分治的搞法，考虑把每个区间拆成不超过 $\log n$ 个线段树上的子区间，将 $d$ 插入这些线段树结点，然后查询 $h$ 的时候，把所有包含 $h$ 的线段树结点上的 $d$ 拿出来即可。
这样做可能会找到不合法的 $d$，然而此时这个 $d$ 的 $\mathrm{mex}$ 必然比 $h$ 贡献的要大，所以可以判断一下然后直接丢掉。
显然这样的拆出来的区间总数不超过 $O(n\log^2 n)$，于是这里的时间复杂度是 $O(n\log^2 n)$ 的。
至于查询，弄个树状数组就好了。
时间复杂度 $O(n\log^2 n+m\log n)$。
空间复杂度大概是 $O(n\log^2 n)$，不满。
Code：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
int n,m,a[N],sta[N],top;
bool vis[N],vs[N];
struct BiT{
int B[N];
inline void add(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
}V,C;
vector<int>vec[N<<2];
void insert(int l,int r,int o,const int&L,const int&R,const int&v){
if(L<=l&&r<=R)vec[o].push_back(v);else{
const int mid=l+r>>1;
if(L<=mid)insert(l,mid,o<<1,L,R,v);
if(mid<R)insert(mid+1,r,o<<1|1,L,R,v);
}
}
void get(int l,int r,int o,const int&v){
for(int i:vec[o])if(!vs[i])vs[i]=1,sta[++top]=i;
vec[o].clear();
if(l<r){
const int mid=l+r>>1;
if(v<=mid)get(l,mid,o<<1,v);else get(mid+1,r,o<<1|1,v);
}
}
inline void run(int x){
int l,r;
do{
++a[x];
C.add(x,1);
l=a[x]*x,r=min(a[x]*x+x,n)-1;
}while(l<=n-1&&V.ask(r+1)>V.ask(l));
if(l<=n-1)
insert(0,n-1,1,l,r,x);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)insert(0,n-1,1,0,i-1,i),C.add(i,1);
while(m--){
int op;
cin>>op;
if(op==1){
int h;
cin>>h;
if(!vis[--h]){
vis[h]=1;
V.add(h+1,1);
top=0;
get(0,n-1,1,h);
for(int i=1;i<=top;++i){
const int&x=sta[i];
if(a[x]==h/x)run(x);
vs[x]=0;
}
}
}else{
int l,r;
cin>>l>>r;
cout<<C.ask(r)-C.ask(l-1)<<'\n';
}
}
return 0;
}