LGP4587题解

遇到一道题，我们该做什么？

打暴力。

此题的暴力是什么？从小到大枚举答案。但这太慢了，需要一个结论来加速一下：

若 \([1,x]\) 都能够被表示出来，新加入一个数 \(y\)，若 \(y>x+1\)，那么新的答案仍然是 \([1,x]\)；若 \(y<=x+1\)，则新的答案为 \([1,x+y]\)。

不是很严谨，感性理解一下

有了这个结论，能够加速枚举答案。

对于一个可行的 \(ans\)，我们统计区间中不大于 \(ans\) 的数之和 \(sum\)。若 \(sum=ans\)，答案就是 \(ans\)，否则将 \(ans\) 替换为 \(sum\) 继续枚举。

至于统计数的个数可以使用主席树。

这复杂度咋一看是 \((\sum a)\log (\sum a)\) 的，其实不然。

假设上一次枚举的数为 \(lst\)，这一次枚举的数为 \(ans\)，很容易发现这一次的 \(sum\) 包含了大于 \(lst\) 且不大于 \(ans\) 的数废话。但第二部分的和一定大于 \(lst\)，也就是说 \(sum > 2lst\)，只需要 \(\log (\sum a)\) 次枚举即可。

复杂度就是 \(m\log n\log (\sum a)\) 的啦

喜闻乐见的代码：

#include<cstdio>

const int M=1e5+5,N=1e9;

int n,m,tot,root[M];

struct Node{

	int L,R,sum;

}t[M*35];

int Modify(int u,int x,int L=1,int R=N){

	int id=++tot;

	t[id]=t[u];t[id].sum+=x;

	if(L<R){

		int mid=L+R>>1;

		if(x<=mid)t[id].L=Modify(t[u].L,x,L,mid);

		else t[id].R=Modify(t[u].R,x,mid+1,R);

	}

	return id;

}

int Query(int q,int p,int x,int L=1,int R=N){

	if(L==R)return t[p].sum-t[q].sum;

	int mid=L+R>>1;

	if(x<=mid)return Query(t[q].L,t[p].L,x,L,mid);

	else return t[t[p].L].sum-t[t[q].L].sum+Query(t[q].R,t[p].R,x,mid+1,R);

}

signed main(){

	register int i,L,R,x,ans;

	scanf("%d",&n);

	for(i=1;i<=n;++i)scanf("%d",&ans),root[i]=Modify(root[i-1],ans);

	scanf("%d",&m);

	for(i=1;i<=m;++i){

		scanf("%d%d",&L,&R);ans=1;

		while((x=Query(root[L-1],root[R],ans))>=ans)ans=x+1;

		printf("%d\n",ans);

	}

}

巴特西

LGP4587题解

最新文章

热门文章