【洛谷5398】[Ynoi2018] GOSICK(莫队二次离线)

点此看题面

  • 给定了一个长度为\(n\)的序列。
  • \(q\)次询问,每次给定一个区间,求区间内有多少对\(i,j\)满足\(a_i\)是\(a_j\)的倍数(\(i,j\)可以相同)。
  • \(n,m,a_i\le5\times10^5\)

莫队二次离线

可以看看模板题:【洛谷4887】【模板】莫队二次离线

不过个人感觉莫队二次离线的核心就是把指针的移动再次离线,而不同的题目在离线之后的操作还是千差万别,因此模板题似乎也没啥用。

对于这道题,这仅仅是基础中的基础,关键还是之后的操作。

设阈值分别处理

考虑我们设出一个分界值\(SN\)。

要给一个数的因数打标记,直接暴力\(\sqrt{a_i}\)枚举每个因数即可。

要给一个数的倍数打标记,如果它超过\(SN\)直接暴力,否则我们给这个因子打上另一种标记。

接下来处理某个前缀上二次离线后的询问,先枚举每个数统计标记和,然后枚举每个\(SN\)内的因子加上它的标记乘上区间内含这个因子的数的个数(这可以事先对每个因子前缀和预处理)。

注意,这里一个很妙的技巧,就是二次离线之后询问的个数仍然是\(O(m)\)级别的,因此我们依旧可以\(O(SN)\)枚举每个因子去处理每一个询问。

这样看起来很正确,但实际上会被卡内存。

因此我们想到去枚举每个小于等于\(SN\)的因数分别搞,这样就不用开\(SN\)个前缀和数组了。

但这样又会\(TLE\),因此我们考虑内存并没有卡得这么夸张,实际上还是可以绑一些约数一起跑的,也就是说实际上只要把小于等于\(SN\)的因数拆成若*分分别搞即可。

具体实现中注意细节,这里相同的两个数\(a_i,a_j\)会计算两次,而相同的\(a_i,a_i\)却只计算一次。方便起见可以先让\(a_i,a_i\)计算两次,最后再给答案减去区间长度。

代码:\(O(n\sqrt n)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500000
#define SN 128
#define P 32
#define LL long long
using namespace std;
int n,m,a[N+5],sz,w[N+5],s[N+5][P];LL g[N+5],ans[N+5];
struct Q {int p,l,r;I bool operator < (Con Q& o) Con {return w[l]^w[o.l]?l<o.l:(w[l]&1?r<o.r:r>o.r);}}q[N+5];//询问
struct Q2 {int p,l,r,op;I Q2(CI i=0,CI a=0,CI b=0,CI c=0):p(i),l(a),r(b),op(c){}};vector<Q2> v[N+5];//二次离线的询问
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int main()
{
	RI i,j;for(read(n,m),sz=sqrt(n),i=1;i<=n;++i) read(a[i]),w[i]=(i-1)/sz+1;
	for(i=1;i<=m;++i) read(q[i].l,q[i].r),q[i].p=i;
	RI L=1,R=0;for(sort(q+1,q+m+1),i=1;i<=m;++i)//莫队
		R<q[i].r&&(v[L-1].push_back(Q2(q[i].p,R+1,q[i].r,-1)),R=q[i].r),
		L>q[i].l&&(v[R].push_back(Q2(q[i].p,q[i].l,L-1,1)),L=q[i].l),
		R>q[i].r&&(v[L-1].push_back(Q2(q[i].p,q[i].r+1,R,1)),R=q[i].r),
		L<q[i].l&&(v[R].push_back(Q2(q[i].p,L,q[i].l-1,-1)),L=q[i].l);
	RI p,vs;for(i=1;i<=N;++i) w[i]=0;for(i=1;i<=n;++i)//处理大于SN的因数的贡献和倍数的贡献
	{
		if(g[i]=w[a[i]],a[i]>SN) for(j=a[i];j<=N;j+=a[i]) ++w[j];//g记录当前数的标记;给大于SN的数的倍数打标记
		for(j=1;j*j<=a[i];++j) !(a[i]%j)&&(++w[j],j^(a[i]/j)&&++w[a[i]/j]);//给约数打标记
		for(j=0,vs=v[i].size();j^vs;++j) for(p=v[i][j].l;p<=v[i][j].r;++p) ans[v[i][j].p]+=v[i][j].op*w[a[p]];//枚举询问中的每个点暴力求标记和
	}
	int c[P];for(RI o=1;o<=SN;o+=P)//枚举P个小于等于SN的因数一起搞
	{
		for(i=1;i<=n;++i) for(p=0;p^P;++p) s[i][p]=s[i-1][p]+!(a[i]%(o+p));//预处理前缀和
		for(p=0;p^P;++p) c[p]=0;for(i=1;i<=n;++i)
		{
			for(p=0;p^P;++p) !(a[i]%(o+p))&&(g[i]+=c[p]);for(p=0;p^P;++p) a[i]==o+p&&++c[p];//g加上因数的标记;给这些因数打标记
			for(j=0,vs=v[i].size();j^vs;++j) for(p=0;p^P;++p)//枚举询问
				ans[v[i][j].p]+=1LL*v[i][j].op*c[p]*(s[v[i][j].r][p]-s[v[i][j].l-1][p]);//区间询问更新贡献
		}
	}
	for(i=1;i<=n;++i) g[i]+=g[i-1];//前缀和
	for(L=1,R=0,i=1;i<=m;++i) ans[q[i].p]+=ans[q[i-1].p]+g[q[i].l-1]-g[L-1]+g[q[i].r]-g[R]+2*(q[i].r-R),L=q[i].l,R=q[i].r;//记得给求出的答案做前缀和
	for(i=1;i<=m;++i) ans[q[i].p]-=q[i].r-q[i].l+1;for(i=1;i<=m;++i) writeln(ans[i]);return clear(),0;//每个答案减去区间长度
}
上一篇:PHP 自己研究的一套 加密 解密 字符串的算法


下一篇:利用java 反射获取配置文件并将对应内容赋值给对应的类