自动搬运

查看原文

来自洛谷，原作者为

	Froggy 最初的一步，泪水之后再一次，雕刻的风景线，消逝在黄昏中的风，直到梦的最后。—— Clannad

搬运于2025-08-24 22:06:46，当前版本为作者最后更新于2020-12-02 20:51:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发一个不需要线段树并且常数超小 （吊打其他题解） 的离线做法？

---

$\mathrm{update}\ 2020.12.18:$ 修了个小锅。

---

容易发现对于一个的伤害值 $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: （超短）

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

呱！