自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:33:56，当前版本为作者最后更新于2022-07-28 22:20:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考虑转化为求 $\sum\limits_{x}x\sum\limits_{[l,r]\subset[L,R]}[\text{Mode}(l,r)=x]$。

首先我们将 $[\text{Mode}(l,r)=x]$ 转化一手。

$$f_{i,x}=\begin{cases}1&(a_i=x)\\-1&(a_i\neq x)\\\end{cases} $$$$\left[\text{Mode}(l,r)=x\right]=[\sum\limits_{i=l}^rf_{i,x}>0] $$

考虑将序列从左向右扫一遍，可以扫出若干满足 $\sum\limits_{i=l}^rf_{i,x}>0$ 的极长区间。

不难发现对于所有 $x$ 的所有极长区间，它们的长度和不会超过 $2n$。

注意到如果一个区间比较小，我们直接枚举出合法的区间进行二维数点即可，时间复杂度 $O(nB+m\sqrt n)$。

考虑区间较大的情况，问题可以直接转化为区间逆序对，时间复杂度 $O((\sum n)\sqrt m+m\sqrt n)$。

直接阈值分治就行了，总时间复杂度 $O(n\sqrt m+m\sqrt n)$，注意二次离线莫队的时间复杂度一定要写成 $O(n\sqrt m+m\sqrt n)$，写出 $O(m\sqrt m)$ 就寄了。

因为心情好就给个代码吧。

// Problem: P7882 [Ynoi2006] rsrams
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7882
// Memory Limit: 512 MB
// Time Limit: 8000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//gzjrr,ddjcc
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define ll long long
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<25],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void print(ll x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') s*=10,s+=ch^48,ch=getchar();
	return s;
}
const int B=3000;
int A[1000003];
vector<int> v[1000003];
struct node{int l,r;}Q[1000003];
vector<node> z[1000003];
ll pre0[1000003],pre1[1003];
struct node3{int l,r,x;};
vector<node3> R;
struct node4{int l,r,id,op;};
vector<node4> f[1000003];
ll ans[1000003];
int n=read(),m=read();
inline void ins(int x,int k)
{
	pre0[x]+=k,pre1[x>>10]+=k;
	return ;
}
inline ll query(int x)
{
	ll res=0;
	for(int i=(x>>10)<<10; i<=x; ++i) res+=pre0[i];
	for(int i=0; i<(x>>10); ++i) res+=pre1[i];
	return res;
}
struct Mo
{
	int N,M,B,L;
	struct mq
	{
		int l,r,bl,id;
		bool operator<(const mq&t)const
		{
			return bl<t.bl||(bl==t.bl&&((bl&1)?r<t.r:r>t.r));
		}
	}q[1000003],tmp[1000003];
	struct oq{int l,r,id,op;};
	vector<oq> vp[1000003],vs[1000003];
	ll tans[1000003],pre[1000003],suf[1000003];
	int a[1000003],tree[1000003],pre0[1100003],pre1[1003];
	inline void add(int x)
	{
		while(x<=N) ++tree[x],x+=x&(-x);
		return ;
	}
	inline int find(int x)
	{
		int res=0;
		while(x) res+=tree[x],x-=x&(-x);
		return res;
	}
	inline void ins(int x)
	{
		for(int i=x,r=((x>>L)+1)<<L; i<r; ++i) ++pre0[i];
		for(int i=(x>>L)+1; (i<<L)<=N; ++i) ++pre1[i];
	}
	inline int query(int x)
	{
		return pre1[x>>L]+pre0[x];
	}
	int lsh[1000003];
	void main(int tl,int tr,int mul)
	{
		N=0,M=m,L=0;
		for(int i=tl,s=0; i<=tr; ++i) 
			++N,lsh[N]=a[N]=((s+=(A[i]==mul?1:-1)));
		while((1<<(L<<1))<=N) ++L;
		for(int i=1,o=0; o<m; ++i)
			q[i].l=max(Q[++o].l-1,tl)-tl+1,
			q[i].r=min(Q[o].r,tr)-tl+1,q[i].id=o,tans[i]=0,
			(q[i].l>=q[i].r)&&(--i,--M);
		if(!M) return ;
		B=N/sqrt(M*2/3+1)+1,sort(lsh+1,lsh+N+1);
		int L=unique(lsh+1,lsh+N+1)-lsh-1;
		for(int i=0; i<=N+1; ++i)
			vector<oq>().swap(vp[i]),
			vector<oq>().swap(vs[i]);
		for(int i=1; i<=N; ++i) 
			a[i]=lower_bound(lsh+1,lsh+L+1,a[i])-lsh;	
		memset(lsh,0,(N+1)<<2);
		for(int i=1; i<=M; ++i) 
			q[i].bl=q[i].l/B,++lsh[q[i].r];
		for(int i=1; i<=N; ++i) lsh[i]+=lsh[i-1];
		for(int i=1; i<=M; ++i) tmp[lsh[q[i].r]--]=q[i];
		memset(lsh,0,(N+1)<<2);
		for(int i=1; i<=M; ++i) ++lsh[q[i].bl];
		for(int i=1; i<=N; ++i) lsh[i]+=lsh[i-1];
		for(int i=1; i<=N; ++i,++i) lsh[i]=lsh[i-1];
		for(int i=1; i<=M; ++i) 
			if(tmp[i].bl&1) q[++lsh[tmp[i].bl]]=tmp[i];
			else q[lsh[tmp[i].bl]--]=tmp[i];
		memset(tree,0,(N+1)<<2);
		for(int i=1; i<=N; ++i)
			pre[i]=pre[i-1]+find(a[i]-1),add(a[i]);
		memset(tree,0,(N+1)<<2),suf[N+1]=0;
		for(int i=N; i>=1; --i)
			suf[i]=suf[i+1]+N-i-find(a[i]),add(a[i]);
		for(int i=1,l=1,r=0; i<=M; ++i)
		{
			if(r<q[i].r) 
				tans[i]+=pre[q[i].r]-pre[r],
				vp[l-1].push_back((oq){r+1,q[i].r,i,-1}),r=q[i].r;
			if(l>q[i].l)
				tans[i]+=suf[q[i].l]-suf[l],
				vs[r+1].push_back((oq){q[i].l,l-1,i,-1}),l=q[i].l;
			if(r>q[i].r) 
				tans[i]-=pre[r]-pre[q[i].r],
				vp[l-1].push_back((oq){q[i].r+1,r,i,1}),r=q[i].r;
			if(l<q[i].l)
				tans[i]-=suf[l]-suf[q[i].l],
				vs[r+1].push_back((oq){l,q[i].l-1,i,1}),l=q[i].l;
		}
		memset(pre0,0,((N>>10)+1)<<12),memset(pre1,0,sizeof(pre1));
		for(int i=1; i<=N; ++i)
		{
			ins(a[i]);
			for(oq j:vp[i])
				for(int k=j.l; k<=j.r; ++k)
					tans[j.id]+=query(a[k]-1)*j.op;
		}
		memset(pre0,0,((N>>10)+1)<<12),memset(pre1,0,sizeof(pre1));
		for(int i=N; i>=1; --i)
		{
			ins(a[i]);
			for(oq j:vs[i])
				for(int k=j.l; k<=j.r; ++k)
					tans[j.id]+=(N-i+1-query(a[k]))*j.op;
		}
		for(int i=1; i<=M; ++i) tans[i]+=tans[i-1];
		for(int i=1; i<=M; ++i) ans[q[i].id]+=tans[i]*mul;
		return ;
	}
}T;
int tmp[1000003],smx[1000003];
signed main()
{
	for(int i=1; i<=n; ++i) 
		A[i]=read(),v[A[i]].push_back(i);
	for(int i=1,l,r; i<=m; ++i) 
		Q[i].l=l=read(),Q[i].r=r=read(),
		f[l-1].push_back((node4){l,r,i,-1}),
		f[r].push_back((node4){l,r,i,1});
	for(int i=1,sz=v[1].size(); i<=n; ++i,sz=v[i].size()) if(sz)
	{
		for(int j=0; j<sz; ++j) tmp[j]=(j<<1)-v[i][j];
		smx[sz]=0xc0c0c0c0;
		for(int j=sz-1; j>=0; --j) smx[j]=max(smx[j+1],tmp[j]);
		for(int j=0,k,l,r,mn=tmp[j],mx=tmp[j]; 
		j<sz; j=k+1,mn=tmp[j],mx=tmp[j])
		{
			for(k=j; mn<=smx[k+1]; 
				++k,mn=min(mn,tmp[k]),mx=max(mx,tmp[k]));
			l=max(v[i][j]-mx+tmp[j],1),
			r=min(v[i][k]+tmp[k]-mn,n);
			if(r-l<B)
				for(int k=l; k<=r; ++k) 
					z[k].push_back((node){l,i});
			else R.push_back((node3){l-1,r,i});
		}
	}
	for(node3 i:R)
		T.main(i.l,i.r,i.x);
	for(int i=1; i<=n; ++i)
	{
		for(node j:z[i])
			for(int k=i,s=0; k>=j.l; --k)
				((s+=(A[k]==j.r?1:-1))>0)&&(ins(k,j.r),0);
		for(node4 j:f[i])
			ans[j.id]+=(query(j.r)-query(j.l-1))*j.op;
	}
	for(int i=1; i<=m; ++i) print(ans[i]),*O++='\n';
	fwrite(obuf,O-obuf,1,stdout);
	return 0;
}