正题

题目链接:https://www.luogu.com.cn/problem/P5012

题目大意

\(n\)个数字的一个序列，\(T\)次询问给出\([l,r]\)要求

找出一个最大的\(x\)满足。提出所有的小于\(x\)的数，然后被提出的数的连续区间长度平方和除以\(x\)的值最大
要求分出来的区间个数在\([l,r]\)之间
强制在线

\(1\leq n\leq 10^6,1\leq T\leq 10^3,1\leq a_i\leq 10^6\)

解题思路

考虑到\(x\)的取值不会超过\([1,10^6]\)，所以暴力枚举\(x\)，然后用并查集合并区间计算出每个\(x\)的区间个数和长度平方和。

然后丢到对应位置跑\(RMQ\)就好了。

时间复杂度\(O(n\log n+Q)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

using namespace std;

const ll N=1e6+10;

ll n,T,lg[N/2],fa[N],siz[N],w[N];

ll ans,L,f[N/2][20],co[N];

vector<ll> v[N];bool k[N];

ll find(ll x)

{return (fa[x]==x)?x:(fa[x]=find(fa[x]));}

void Merge(ll x,ll y){

	x=find(x);y=find(y);

	ans-=siz[x]*siz[x]+siz[y]*siz[y];

	fa[y]=x;siz[x]+=siz[y];

	ans+=siz[x]*siz[x];

	return;

}

ll Ask(ll l,ll r){

	if(l>L)return 0;

	if(r>L)r=L;

	ll z=lg[r-l+1];

	ll x=f[l][z],y=f[r-(1<<z)+1][z];

	if(w[x]*co[y]>w[y]*co[x])return x;

	return y;

}

signed main()

{

	scanf("%lld%lld",&n,&T);

	for(ll i=1;i<=n;i++){

		ll x;scanf("%lld",&x);

		v[x].push_back(i);

		fa[i]=i;siz[i]=co[i]=1;

	}

	ll cnt=0;

	for(ll i=1;i<=1e6;i++){

		for(ll j=0;j<v[i].size();j++){

			ll x=v[i][j];k[x]=1;ans++;cnt++;

			if(k[x-1])Merge(x-1,x),cnt--;

			if(k[x+1])Merge(x,x+1),cnt--;

		}

		if(w[cnt]*i<=ans*co[cnt])w[cnt]=ans,co[cnt]=i;

		L=max(L,cnt);

	}

	for(ll i=1;i<=L;i++)f[i][0]=i;

	for(ll i=2;i<=L;i++)lg[i]=lg[i>>1]+1;

	for(ll j=1;(1<<j)<=L;j++)

		for(ll i=1;i+(1<<j)-1<=L;i++){

			ll x=f[i][j-1],y=f[i+(1<<j-1)][j-1];

			if(w[x]*co[y]>w[y]*co[x])f[i][j]=x;

			else f[i][j]=y;

		}

	ans=0;

	while(T--){

		ll a,b,x,y;

		scanf("%lld%lld%lld%lld",&a,&b,&x,&y);

		ll l=(a*ans+x-1)%n+1;

		ll r=(b*ans+y-1)%n+1;

		if(l>r)swap(l,r);

		ll p=Ask(l,r);

		if(!w[p])printf("-1 -1\n");

		else printf("%lld %lld\n",w[p],co[p]);

		printf("%lld %lld %lld\n",l,r,ans);

		ans=w[p]?(w[p]*co[p]%n):1;

	}

	return 0;

}

巴特西

P5012-水の数列【并查集,RMQ】

正题

题目大意

解题思路

code

最新文章

热门文章