luogu P4887 模板莫队二次离线莫队离线

LINK：模板莫队二次离线

很早以前学的知识点不过很久了忘了。

考虑暴力 :每次莫队更新的时候尝试更新一个点到一个区间的答案可以枚举二进制下位数为k的数字看一下区间内的这种数字有多少个。

不过这样每次移动的复杂度为 C(14,k)的。

考虑将每次移动操作进行离线答案进行差分。

那么只需要求出指针移动的变换量即可由于左端点和右端点的变换量都是nsqrt(n)的

如果直接开空间这么存空间复杂度nsqrt(n).吃不消。

考虑将一个f(L,[L+1,R])的这种形式的贡献进行前后差分 f(L,1~R)-f(L,[1,L-1]).

这样每次存的都是连续的一堆离线下来的东西也可以前缀和的时候做前一步nsqrt(n)。

后一步进行扫描线 nk+nsqrt(n).

很妙的算法。

const int MAXN=100010;

int n,m,k,B,maxx;

int a[MAXN],sum[MAXN],pre[MAXN],v[MAXN];ll ans[MAXN],cc[MAXN];

struct wy{int l,r,id;}t[MAXN];

vector<wy>g[MAXN];

vector<int>p;

inline int cmp(wy a,wy b){return v[a.l]==v[b.l]?a.r<b.r:a.l<b.l;}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);get(k);

	if(k>14)

	{

		rep(1,m,i)puts("0");

		return 0;

	}

	maxx=16383;

	rep(0,maxx,i)

	{

		sum[i]=sum[i>>1]+(i&1);

		if(sum[i]==k)p.pb(i);

	}

	rep(0,maxx,i)sum[i]=0;

	B=(int)sqrt(n*1.0);

	rep(1,n,i)

	{

		get(a[i]);v[i]=(i-1)/B+1;

		pre[i-1]=sum[a[i]];

		vep(0,p.size(),j)++sum[a[i]^p[j]];

	}

	rep(1,m,i)t[i]=(wy){read(),read(),i};

	sort(t+1,t+1+m,cmp);

	int L=1,R=0;

	rep(1,m,i)

	{

		if(L<t[i].l)g[R].pb((wy){L,t[i].l-1,-i});

		while(L<t[i].l){ans[i]+=pre[L-1];++L;}

		if(L>t[i].l)g[R].pb((wy){t[i].l,L-1,i});

		while(L>t[i].l){--L;ans[i]-=pre[L-1];}

		if(R<t[i].r)g[L-1].pb((wy){R+1,t[i].r,-i});

		while(R<t[i].r){ans[i]+=pre[R];++R;}

		if(R>t[i].r)g[L-1].pb((wy){t[i].r+1,R,i});

		while(R>t[i].r){ans[i]-=pre[R-1];--R;}

	}

	rep(0,maxx,i)sum[i]=0;

	rep(1,n,i)

	{

		vep(0,p.size(),j)++sum[a[i]^p[j]];

		vep(0,g[i].size(),j)

		{

			int l=g[i][j].l;int r=g[i][j].r;

			int id=g[i][j].id;

			rep(l,r,w)

			{

				int ww=sum[a[w]];

				if(k==0&&w<=i)--ww;

				if(id<0)ans[-id]-=ww;

				else ans[id]+=ww;

			}

		}

	}

	rep(1,m,i)ans[i]+=ans[i-1],cc[t[i].id]=ans[i];

	rep(1,m,i)putl(cc[i]);

	return 0;

}

巴特西

luogu P4887 模板莫队二次离线莫队离线

最新文章

热门文章

巴特西

luogu P4887 模板 莫队二次离线 莫队 离线

最新文章

热门文章

luogu P4887 模板莫队二次离线莫队离线