专栏文章

P14558 解题报告

HHoks
P14558题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3mr30
此快照首次捕获于
2025/12/01 20:01
3 个月前
此快照最后确认于
2025/12/01 20:01
3 个月前
查看原文

前言

神秘爷爷辈 ROI，1313 年题被 17 年出，21 年出，有点厉害的。

思路分析

根号啥的太无脑了吧，事实上 log⁡2\log^2 也不太需要动脑。
存在一种 log⁡\log 的分治做法，不过猫猫不是很喜欢，我们直接来一个发掘性质的 O(n)O(n) 做法。
众数，也太难了。
我们知道有一种算绝对众数的方法叫摩尔投票法。
但这个东西也太垃圾了，每次一个区间的都要扫一遍才能算，如果不存在还不一定算的对要 shuffle 区间再多算几遍来检验存在性。
做不了怎么办？手动添加限制条件。
我们不妨考虑拆贡献，计算数字 xx 为区间绝对众数的贡献。
那我们考虑类似摩尔投票的想法，令 ai=2[ai=x]−1a_i=2[a_i=x]-1，也就是相同赋 11，不同赋 −1-1。
那么一个区间以 xx 为绝对众数就当且仅当区间和为正的时候。
然后我们经典操作一下，前缀和之后区间 [l,r][l,r] 的和即为 sr−sl−1s_r-s_{l-1}。
然后这就是一个二维偏序嘛，sl−1<sr,l<rs_{l-1}<s_r,l<r。
但直接转成二维偏序掉性质，导致带 log⁡\log 也太丑了。
你考虑每次最多 ±1\pm1，画一下折线图。
然后你就知道，当你位于 (r,sr)(r,s_r) 的时候，你统计的事 l<r,sl−1<srl<r,s_{l-1}<s_r，但是每次 ±1\pm1 保证了你不会有 sl−1<srs_{l-1}<s_r 的点突然被插入。
也就是我们只需要再累一个和记录下当前小于的数量和就可以了。
比较抽象所以先给个代码看看：
CPP
for(int i=1,s=n,ss=0;i<=k;i++)
{
  if(c[i]==x) ss+=cnt[s++],cnt[s]++;
  else ss-=cnt[--s],cnt[s]++;ans+=ss;
}
其中 cc 是未累积前缀和的待统计数组，初值赋值为 nn 旨在防止负数下标。
然后这样我们就得到了 O(nV)O(nV) 做法，显然无法通过。
然后我们注意到什么？
你注意到如果有 ww 个数 xx，那么你所能取到的最大区间长度为 2w2w，这是一个极强的限制条件。
也就是说有很多很多的区间，他其实都是不可能取到的。
那我们怎样去掉大部分不合法的区间呢？
考虑从当前数字开始往右跑，一直累加和。
显然的是变成 −1-1 的时候就可以停下来了，到这里就没贡献了。
但现在有个问题就是形如这样的： x,x,0,0,0,x,x,xx,x,0,0,0,x,x,x 我们注意到右边那段可以把左边那段整个合并进去，所以光往右跑是有问题的。
那怎么办呢？
我们注意到假设向右跑出来的区间为 [l,r][l,r]，那么最远有贡献区间不会超过 [l−(r−l+1)+1,r][l-(r-l+1)+1,r]。
因为假设这个区间全是 xx 左边也只能移动到这里。
那不带脑一点，直接给这个整个区间整个扔进去就好了（记得合并一下重复了的部分）。
然后我们算一下复杂度。
有 ww 个 xx，得到的所有区间总长度为 2w2w。
而我们刚刚又用了一次对称，所以卡满就是 4w4w 的。
因为有 ∑w=n\sum w=n，所以总区间长度复杂度还是 O(n)O(n) 的。
这里处理出了可用的区间，搭配上前面那个 O(len)O(len) 计算贡献的方式就可以得到严格线性的做法了。

代码

比较好写。
CPP
#include<bits/stdc++.h>
namespace Hoks
{
	#define ls (p<<1)
	#define rs (ls|1)
	#define mid ((l+r)>>1)
	using namespace std;
	const int N=5e5+10,B=2010,M=50,V=1e6,mod=95542721,INF=3e18;
	int n,v,m,k,a[N],c[N],cnt[N<<1];long long ans;
	vector<int>e[N];pair<int,int>b[N];
	namespace Fast_IO
	{
		static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
		#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
		inline int read()
		{
			int x(0),t(1);char fc(getchar());
			while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
			while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
			return x*t;
		}
		inline void flush(){fwrite(out,1,length,stdout);length=0;}
		inline void put(char c){if(length==9999999) flush();out[length++]=c;}
		inline void put(string s){for(char c:s) put(c);}
		inline void print(long long x)
		{
			if(x<0) put('-'),x=-x;
			if(x>9) print(x/10);
			put(x%10+'0');
		}
		inline bool chk(char c) { return !(c=='.'||c=='#'||c=='('||c==')'||c==':'||c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
		inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
		inline void rd(char s[],int&n)
		{
			s[++n]=getchar();
			while(chk(s[n])) s[n]=getchar();
			while(ck(s[n])) s[++n]=getchar();
			n--;
		}
	}
	using namespace Fast_IO;
	inline void solve()
	{
		n=read();v=read();for(int i=1;i<=n;i++) e[a[i]=read()].emplace_back(i);
		for(int x=1;x<=v;x++)
		{
			m=0;int lst=0;
			for(auto i:e[x])
			{
				if(lst>=i) continue;int t=i,s=0;
				while(t<=n&&s>=0) s+=2*(a[t]==x)-1,t++;
				b[++m]={i,min(t+1,n)};lst=t-1;
			}if(!m) continue;reverse(b+1,b+1+m);
			int r=b[1].second,l=b[1].first*2-r-1;k=0;
			for(int i=2;i<=m;i++)
				if(l<=b[i].second) l=min(l,b[i].first-(r-b[i].first)-1);
				else
				{
					for(int j=r;j>=l&&j>=1;j--) c[++k]=a[j];
					r=b[i].second,l=b[i].first*2-r-1;
				}
			for(int j=r;j>=l&&j>=1;j--) c[++k]=a[j];cnt[n]=1;
			for(int i=1,s=n,ss=0;i<=k;i++)
			{
				if(c[i]==x) ss+=cnt[s++],cnt[s]++;
				else ss-=cnt[--s],cnt[s]++;ans+=ss;
			}
			for(int i=1,s=n;i<=k;i++)
				if(c[i]==x) cnt[++s]=0;
				else cnt[--s]=0;
		}print(ans);put('\n');
	}
	inline void main()
	{
		int T=1;
		// T=read();
		while(T--) solve();
		genshin:;flush();
	}
}
signed main()
{
	Hoks::main();return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...