您的位置: 首页  >  IT文章  >  【洛谷5398】[Ynoi2018] GOSICK（莫队二次离线）

【洛谷5398】[Ynoi2018] GOSICK（莫队二次离线）

分类: IT文章 • 2022-07-25 18:00:47

点此看题面

  • 给定了一个长度为(n)的序列。
  • (q)次询问，每次给定一个区间，求区间内有多少对(i,j)满足(a_i)是(a_j)的倍数（(i,j)可以相同）。
  • (n,m,a_ile5 imes10^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(nsqrt 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('
');}
}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;//每个答案减去区间长度
}

相关推荐