摆书

C++(g++ 7.5.0) 解法, 执行用时: 702ms, 内存消耗: 14612K, 提交时间: 2023-05-05 22:12:13

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const ll INF=1e13;
vector<ll> pos[N],sum[N];
int sz[N];
ll fun(int l, int cnt) {
	return (l+l+cnt-1ll)*cnt/2;
}
ll cal(int col, int l, int r, int idx, int tem) {
	if (l>r) return 0;
	if (tem==0) {
		int L=1,R=l-1,ans=0;
		while (L<=R) {
			int m=L+(R-L+1)/2;
			if (idx-pos[col][m]>=r-m+1) ans=m,L=m+1;
			else R=m-1;
		}
		int cnt=idx-pos[col][ans]-(r-ans+1);
		if (cnt<0) return INF*(-cnt);
		idx=pos[col][ans]+cnt+1;
		l=ans+1;
		return sum[col][r]-sum[col][l-1]-fun(idx,r-l+1);
	} else {
		int L=r+1,R=sz[col],ans=R+1;
		while (L<=R) {
			int m=L+(R-L+1)/2;
			if (pos[col][m]-idx>=m-l+1) ans=m,R=m-1;
			else L=m+1;
		}
		int cnt=pos[col][ans]-idx-(ans-l+1);
		if (cnt<0) return INF*(-cnt);
		idx=pos[col][ans]-cnt-1;
		r=ans-1;
		return fun(idx-(r-l),r-l+1)-sum[col][r]+sum[col][l-1];
	}
}
ll f(int x, int mid, int l, int r, int L, int R) {
//	if (x==3&&l==2&&mid==2) cout<<cal(x,l,mid,L,0)<<" "<<l<<" "<<mid<<" "<<r<<endl;
	return cal(x,l,mid,L,0)+cal(x,mid+1,r,R,1);
}
ll bin3(int x, int l, int r, int L, int R)
{
    if(l>r) return 0;
    ll res=min(f(x,l,l,r,L,R),f(x,r,l,r,L,R));
    res=min(res,cal(x,l,r,L,0)); res=min(res,cal(x,l,r,R,1));
    ll sl=l,sr=r;
    while(sl<=sr){
        ll m=(sl+sr)>>1;
		ll m1=(sl+m)>>1;
		ll m2=(m+1+sr)>>1;
        ll fm=f(x,m1,l,r,L,R),fmm=f(x,m2,l,r,L,R);
 //       cout<<m2<<" "<<fmm<<endl;
        if(fm>=fmm) sl=m1+1;
        else sr=m2-1;
        res=min(res,min(fm,fmm));
    }
    return res>=INF?-1:res;
} 
int main() {
	int n,q; scanf("%d%d",&n,&q);
	for (int i=1; i<=n; i++) {
		sum[i].push_back(0);
		pos[i].push_back(0);
	}
	for (int i=1; i<=n; i++) {
		int num; scanf("%d",&num);
		pos[num].push_back(i);
		sz[num]++;
		sum[num].push_back(i);
		sum[num][sz[num]]+=sum[num][sz[num]-1];
	}
	for (int i=1; i<=n; i++) {
		pos[i].push_back(n+1);
		ll num=sum[i][sz[i]];
		sum[i].push_back(num+n+1);
	}
	while (q--) {
		int L,R,x; scanf("%d%d%d",&L,&R,&x);
		int r=upper_bound(pos[x].begin(),pos[x].end(),R)-pos[x].begin()-1;
		int l=lower_bound(pos[x].begin(),pos[x].end(),L)-pos[x].begin();
		printf("%lld\n",bin3(x,l,r,L,R));
	}
	
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 349ms, 内存消耗: 15144K, 提交时间: 2023-05-06 21:39:59

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define pb push_back
#define mid ((l+r)>>1)
#define lch (rt<<1)
#define rch (rt<<1|1)

using namespace std;
const int N=100005;
typedef long long LL;
int n,m,a[N];
vector <int> vt[N];
vector <LL> s[N];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

int get(vector <int> &vt,int x)
{
	int l=0,r=vt.size()-1;
	while(l<=r) vt[mid]<=x?l=mid+1:r=mid-1;
	return l-1;
}

int get(int l,int r,int x)
{
	return get(vt[x],r)-get(vt[x],l-1);
}

LL calc(int ql,int qr,int x,int cnt,int y)
{
	int z=cnt-y;
	LL ret=(LL)y*y+(LL)(cnt-y)*(cnt-y);
	int l=get(vt[x],ql-1);
	ret+=(s[x][l+y]-s[x][l])-(LL)(ql+ql+y-1)*y/2;
	int r=get(vt[x],qr);
	ret+=(LL)(qr+qr-z+1)*z/2-(s[x][r]-s[x][r-z]);

	ret+=(LL)(ql-1+ql-y)*y/2;
	ret-=(LL)(qr+1+qr+z)*z/2;

	int L=l,R=r;
	l=0,r=L;
	while(l<=r)
		if(ql-vt[x][mid]-(L-mid+1)<y) r=mid-1;
		else l=mid+1;
	++r;
	int p=ql-y-(L-r+1);
	ret-=(LL)(p+ql-1)*(ql-p)/2-(s[x][L]-s[x][r-1]);
	
	l=R+1,r=vt[x].size()-1;
	while(l<=r)
		if(vt[x][mid]-qr-(mid-R)<z) l=mid+1;
		else r=mid-1;
	--l;
	p=qr+z+(l-R);
	ret+=(LL)(p+qr+1)*(p-qr)/2-(s[x][l]-s[x][R]);
	return ret;
}

int main()
{
	n=getint(),m=getint();
	rep(i,1,n) vt[i].pb(0),s[i].pb(0);
	rep(i,1,n)
		a[i]=getint(),vt[a[i]].pb(i),s[a[i]].pb(i+s[a[i]].back());
	while(m--)
	{
		int ql=getint(),qr=getint(),x=getint();
		int cnt=get(ql,qr,x);
		int L=min(cnt,ql-1-get(vt[x],ql-1));
		int R=min(cnt,n-qr-((int)vt[x].size()-1-get(vt[x],qr)));
		int l=cnt-R,r=L-1;
		if(L+R<cnt)
		{
			puts("-1");
			continue;
		}
		while(l<=r)
			if(calc(ql,qr,x,cnt,mid)>=calc(ql,qr,x,cnt,mid+1))
				l=mid+1;
			else r=mid-1;
		printf("%lld\n",calc(ql,qr,x,cnt,l));
	}
	return 0;
}

详情