自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:07:04，当前版本为作者最后更新于2024-12-20 17:58:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

不是很会卡空间……

显然，线段只有可能的 $O(n)$ 个，且右端点互不相同。

设 $f(u)$ 为左端点大于 $u$ 的所有线段中，右端点的最小值。

显然对 $l$ 和 $r$ 处理询问时，令 $x = l-1$，不断 $x \leftarrow f(x)$ 直到 $f(x) > r$。

显然 $(x,f(x))$ 形成了一棵树。如果不卡空间，可以倍增。还有一种做法是从左往右扫描，维护目前所有联通块（使用并查集）

后者时空都是 $O(n)$ 的（但是找线段部分实际上是 $O(n \log n)$ 的），精细实现即可通过。

一些可能的卡空间方法：

1. 重复利用数组。
2. 尽量别开 long long，不用 STL。

在公开代码的人中，斩获了时间空间最优解（2024.12.20 之前）

#include<bits/stdc++.h>
#define llx long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=4e5+10;
int tot,n,q,fa[MAXN],anc[MAXN],ans[MAXN],hd[MAXN],nxt[MAXN],l[MAXN],r[MAXN],c[MAXN];
int find(int k) {return (anc[k]==k)?k:(anc[k]=find(anc[k]));}
void add(int u,int id) {return nxt[id]=hd[u],hd[u]=id,void();}
llx lsh[MAXN];
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) cin>>c[i];
	llx pre=0;
	memset(fa,0x3f,sizeof(fa)),memset(ans,-1,sizeof(ans));
	ffor(i,0,n) pre+=c[i],lsh[++tot]=pre;
	sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1,pre=0;
	ffor(i,0,n) {
		pre+=c[i];
		int id=lower_bound(lsh+1,lsh+tot+1,pre)-lsh;
		if(ans[id]!=-1) fa[ans[id]]=i;
		ans[id]=i;
	}
	tot=0;
	fa[n]=n+1;
	roff(i,n,0) fa[i]=min(fa[i],fa[i+1]);
	ffor(i,0,n+1) l[i]=n+2,r[i]=-1;
	ffor(i,0,n) l[fa[i]]=min(l[fa[i]],i),r[fa[i]]=max(r[fa[i]],i);
	fa[n+1]=0;
	roff(i,n,0) fa[i]=fa[fa[i]]+1;
	ffor(i,0,n) anc[i]=i;
	cin>>q;
	ffor(i,1,q) {
		int l,r;
		cin>>l>>r;
		c[i]=l-1,add(r,i),ans[i]=fa[l-1];
	}
	ffor(i,0,n) {
		ffor(j,l[i],r[i]) anc[j]=i;
		for(int id=hd[i];id;id=nxt[id]) ans[id]-=fa[find(c[id])];
	}
	ffor(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}