题解 P5068 【[Ynoi2015]我回来了】
Froggy
·
·
题解
发一个不需要线段树并且常数超小 （吊打其他题解） 的离线做法？
---
容易发现对于一个的伤害值 $d$， 我们只需要依次关注是否有血量在 $[1,d],[d+1,2d],\cdots,\left[d\cdot\lfloor\frac{n}{d}\rfloor+1,n\right]$ 这个区间中的随从（不妨用一个二元组 $(d,i)$ 表示伤害值为 $d$ 的第 $i$ 个区间）。也就是说，亵渎最多会被触发 $\left\lceil\frac{n}{d}\right\rceil$ 次。那么所有 $d\in [1,n]$，区间总数一共不超过 $\mathcal{O}(n\log n)$ 个（是个调和级数）。
可以考虑把询问离线下来，然后分别求出每个区间最早存在随从时是在第几次操作。不妨假设伤害值为 $d$ 的第 $i$ 个区间在 $t_{d,i}$ 个操作时最早有随从了。
设 $a_i$ 表示最早在第几个操作存在血量为 $i$ 的随从（如果自始至终不存在就设为 $m+1$）。
根据定义可知：
$$t_{d,i}=\min\limits_{(i-1)d+1\leq j\leq\min \{id,n\}} a_j$$
这个可以通过 ST 表解决，不再多说。这部分复杂度为 $\mathcal{O}(n\log n)$，因为 ST 表可以做到 $\mathcal{O}(1)$ 查询区间最小值。
再设 $g_{d,i}$ 表示伤害值为 $d$ 的亵渎被触发至少 $i$ 次最早在第几次操作。显然 $g_{d,i}=\max \{g_{d,i-1},t_{d,i}\}$。
仔细观察会发现，对于一个区间 $(d,i)$ ，它会对在 $g_{d,i}$ 之后并且询问区间包含 $i$ 的询问操作产生 $1$ 的贡献。
这是一个简单的二维偏序问题，可以把所有 $g_{d,i}$ 相同的区间放到一起然后用树状数组简单维护。
这部分时间复杂度：$\mathcal{O}(n\log^2 n+m\log n)$。（$n\log^2n$ 部分带个树状数组以及调和级数的小常数）
总的时间复杂度：$\mathcal{O}(n\log^2n+m\log n)$。
---
***code:*** （超短）
```cpp
typedef pair<int,int> pii;
typedef long long ll;
#define N 100010
#define M 1000100
int n,a[N],m,f[N][20],lg[N];
pii q[M];
vector<int> vec[M];
inline int Query(int l,int r){
int k=lg[r-l+1];
return min(f[l][k],f[r-(1<<k)+1][k]);
}
struct BIT{
int b[N];
inline int lowbit(int x){
return x&(-x);
}
inline void Add(int x){
while(x<=n){
++b[x];
x+=lowbit(x);
}
}
inline int Ask(int x){
int ans=0;
while(x){
ans+=b[x];
x-=lowbit(x);
}
return ans;
}
}B;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i]=m+1;
}
for(int i=1;i<=m;++i){
int opt=read();
q[i]={-1,-1};
if(opt==1){
int x=read();
a[x]=min(a[x],i);
}
else{
q[i].first=read(),q[i].second=read();
}
}
for(int i=2;i<=n;++i){
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=n;++i){
f[i][0]=a[i];
}
for(int j=1;j<=18;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1;i<=n;++i){
B.Add(i);
int las=0;
for(int j=1;j<=n;j+=i){
vec[las=max(las,Query(j,min(j+i-1,n)))].push_back(i);
}
}
for(int i=1;i<=m;++i){
for(auto x:vec[i]){
B.Add(x);
}
if(~q[i].first){
printf("%d\n",B.Ask(q[i].second)-B.Ask(q[i].first-1));
}
}
return 0;
}
```
---
[***Froggy's blog***](https://www.luogu.com.cn/blog/froggy/)
呱！