自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:47:27，当前版本为作者最后更新于2023-05-09 20:45:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

阈值分治，对于 $a_i$ 出现次数 $\leq B$ 的直接求出每个 pair 的贡献然后做二维数点。

对于 $a_i$ 出现次数 $>B$ 的直接对于每种数做一遍回滚莫队维护连续段。

前半部分时间复杂度 $O(nB+m\sqrt n)$，后半部分时间复杂度 $O(\frac{nm}{B}+n\sqrt m)$。

代码懒得写了，退役人哪有空写代码。

写完了。

// Problem: P9337 [Ynoi2001] 冷たい部屋、一人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9337
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//And from now on, YOU are my GUIDING STAR.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[500003],c[500003];
int l2[500003],n=read(),m=read();
vector<int> v[500003];
int arr[2000003],L;
bool flg[2000003];
struct query{int l,r,id;}q[500003],q0[500003];
vector<pair<int,int>> vq[500003];
struct stmax
{
	int st[500003][19];
	inline void init(int l)
	{
		st[l][0]=a[l];
		for(int i=1; i<19; i++) 
			st[l][i]=max(st[l][i-1],
			st[min(l+(1<<(i-1)),n)][i-1]);
	}
	inline int query(int l,int r)
	{
		int L=l2[r-l+1];
		return max(st[l][L],st[min(r-(1<<L)+1,n)][L]);
	}
	void main()
	{
		for(int i=n; i; --i) init(i);
		return ;
	}
}S1;
struct stmin
{
	int st[500003][19];
	inline void init(int l)
	{
		st[l][0]=a[l];
		for(int i=1; i<19; i++) 
			st[l][i]=min(st[l][i-1],
			st[min(l+(1<<(i-1)),n)][i-1]);
	}
	inline int query(int l,int r)
	{
		int L=l2[r-l+1];
		return min(st[l][L],st[min(r-(1<<L)+1,n)][L]);
	}
	void main()
	{
		for(int i=n; i; --i) init(i);
		return ;
	}
}S0;
struct BIT
{
	int pre0[500003],pre1[503];
	inline void add(int x)
	{
		++pre0[x],++pre1[x>>10];
		return ;
	}
	inline int find(int x)
	{
		int 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;
	}
}T;
const int B=2000;
ll ans[500003];
vector<int> pos[500003];
int to_[500003],val_[500003],top;
int to[500003],val[500003],buc[500003];
int ta[500003],lsh[500003],inv[500003];
bool tf[500003];
struct range{int fi,se,id;}rg[500003],stk[1000003];
signed main()
{
	for(int i=2; i<=n; i++) l2[i]=l2[i>>1]+1;
	for(int i=1; i<=n; ++i) c[i]=read(),v[c[i]].push_back(i);
	for(int i=1; i<=n; ++i) a[i]=read();
	for(int i=1; i<=m; ++i)
		rg[i].fi=read(),rg[i].se=read(),rg[i].id=i,
		vq[rg[i].fi].emplace_back(rg[i].se,i);
	S0.main(),S1.main(),sort(rg+1,rg+m+1,
	[&](auto x,auto y){return x.se<y.se;});
	for(int i=1; i<=n; ++i)
	{
		int sz=v[i].size();
		if(sz>=B)
		{
			int N=0,M=0;
			memset(buc,0,sizeof(buc));
			for(int j=0; j<sz; ++j)
			{
				ta[++N]=a[v[i][j]],tf[N]=1;
				if(j+1<sz&&v[i][j]+1<v[i][j+1])
				{
					ta[++N]=S0.query(v[i][j]+1,v[i][j+1]-1),tf[N]=0;
					if(v[i][j]+2<v[i][j+1])
					ta[++N]=S1.query(v[i][j]+1,v[i][j+1]-1),tf[N]=0;
				}
			}
			for(int j=1; j<=N; ++j) lsh[j]=ta[j],++buc[ta[j]];
			for(int j=1; j<=n; ++j) buc[j]+=buc[j-1];
			sort(lsh+1,lsh+N+1);
			for(int j=1; j<=N; ++j)
				ta[j]=lower_bound(lsh+1,lsh+N+1,ta[j])-lsh,
				inv[ta[j]]=j;
			for(int j=1; j<=m; ++j)
			{
				++M,q0[M].l=buc[rg[j].fi-1]+1,
				q0[M].r=buc[rg[j].se],q0[M].id=rg[j].id;
				if(q0[M].l>q0[M].r) --M;
			}
			if(!M) continue;
			int C=.7*N/sqrt(M)+1;
			memset(buc,0,sizeof(buc));
			for(int j=1; j<=M; ++j) ++buc[q0[j].l/C];
			for(int j=1; j<=N; ++j) buc[j]+=buc[j-1];
			for(int j=M; j>=1; --j) q[buc[q0[j].l/C]--]=q0[j];
			ll sum=0;
			memset(to,0,(N+2)<<2),memset(val,0,(N+2)<<2);
			for(int j=1,tl=C,tr=C-1; j<=M; ++j)
			{
				if(q[j].l/C!=q[j-1].l/C)
					memset(to,0,(N+2)<<2),
					memset(val,0,(N+2)<<2),
					tl=(q[j].l/C+1)*C,tr=tl-1,sum=0;
				if(q[j].l/C==q[j].r/C)
				{
					ll sum_=0;
					for(int k=q[j].l; k<=q[j].r; ++k)
					{
						int l=inv[k],r=inv[k],sv=tf[inv[k]];
						if(to_[l-1])
							sum_-=1ll*val_[to_[l-1]]*
							(val_[to_[l-1]]-1),
							sv+=val_[to_[l-1]],l=to_[l-1];
						if(to_[r+1])
							sum_-=1ll*val_[r+1]
							*(val_[r+1]-1),
							sv+=val_[r+1],r=to_[r+1];
						sum_+=1ll*sv*(sv-1),
						to_[l]=r,to_[r]=l,val_[l]=sv;
					}
					for(int k=q[j].l; k<=q[j].r; ++k)
						to_[inv[k]]=val_[inv[k]]=0;
					ans[q[j].id]+=sum_>>1;
					continue;
				}
				while(tr<q[j].r)
				{
					int k=++tr,l=inv[k],r=inv[k],sv=tf[inv[k]];
					if(to[l-1])
						sum-=1ll*val[to[l-1]]*
						(val[to[l-1]]-1),
						sv+=val[to[l-1]],l=to[l-1];
					if(to[r+1])
						sum-=1ll*val[r+1]
						*(val[r+1]-1),
						sv+=val[r+1],r=to[r+1];
					sum+=1ll*sv*(sv-1),
					to[l]=r,to[r]=l,val[l]=sv;
				}
				ll tsum=sum;
				for(int k=tl-1; k>=q[j].l; --k)
				{
					int l=inv[k],r=inv[k],sv=tf[inv[k]];
					if(to[l-1])
						tsum-=1ll*val[to[l-1]]*
						(val[to[l-1]]-1),
						sv+=val[to[l-1]],l=to[l-1];
					if(to[r+1])
						tsum-=1ll*val[r+1]
						*(val[r+1]-1),
						sv+=val[r+1],r=to[r+1];
					tsum+=1ll*sv*(sv-1),
					stk[++top]={to[l],val[l],l},
					to[l]=r,val[l]=sv,
					stk[++top]={to[r],val[r],r},
					to[r]=l;
				}
				while(top)
					to[stk[top].id]=stk[top].fi,
					val[stk[top].id]=stk[top].se,--top;
				ans[q[j].id]+=tsum>>1;
			}
		}
		else
		{
			for(int j=0; j<sz; ++j)
			{
				arr[++L]=a[v[i][j]],flg[L]=1,
				pos[arr[L]].push_back(L);
				if(j+1<sz&&v[i][j]+1<v[i][j+1])
				{
					arr[++L]=S0.query(v[i][j]+1,v[i][j+1]-1),
					pos[arr[L]].push_back(L);
					if(v[i][j]+2<v[i][j+1])
						arr[++L]=S1.query(v[i][j]+1,v[i][j+1]-1),
						pos[arr[L]].push_back(L);
				}
			}
			arr[++L]=0;	
		}
	}
	for(int i=n; i>=1; --i)
	{
		for(int j:pos[i])
		{
			for(int l=j,v=arr[j]; arr[l]>=arr[j];
				v=max(v,arr[--l])) if(flg[l])
			for(int r=j,w=v; r==j||arr[r]>arr[j];
				w=max(w,arr[++r])) if(flg[r]&&l<r) T.add(w);
		}
		for(auto [j,k]:vq[i])
			ans[k]+=T.find(j);
	}
	for(int i=1; i<=m; ++i) printf("%lld\n",ans[i]);
	return 0;
}