jzoj5260题解

Jan 9, 2018 14:41 · 229 words · 2 minutes read 题解 jzoj 分块 莫队

首先不管强制在线,不管数据范围,只考虑设计一个亚二次的算法,显然可以用莫队+值域线段树在$O(n\sqrt{n}\log n)$的时间内解决。但是这个做法会爆0+卡爆机房的奔腾cpu电脑……

注意到在莫队算法中,因端点改变对值域线段树造成的修改有$O(n\sqrt{n})$次,但是对值域线段树的询问只有$O(n)$次,所以可以考虑牺牲询问来加速修改。

考虑对值域也分块,维护每个块里面出现次数<=w的数的总出现次数,以及每个数具体的出现次数,就可以做到$O(n\sqrt{n})$。

最后再把莫队改成强制在线的莫队,预处理出f[i][j][k]表示第i块到第j块中,值在第k块中的,出现次数<=w的数的出现次数,以及g[i][j]表示前i块中j的出现次数。

写的时候因为一个sb错误debug了很久,以后要注意,为了代码简单把几种情况归成一种情况写的时候,需要仔细研究几种情况的不同点。比方说,l,r在同一块的时候,就不要写出g[r/S-1][j]这样优秀的潜在未定义行为(因为r可能在第0块)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ele int
using namespace std;
#define maxn 100010
#define maxb 320
ele n;
struct arr{
	ele t,a[maxn],b[maxn];
	arr(){
		t=0; memset(b,0,sizeof(b));
	}
	inline ele& operator[](ele i){
		if (b[i]<t) b[i]=t,a[i]=0;
		return a[i];
	}
};
ele w,q,ty,S,bcnt,a[maxn],f[maxb][maxb][maxb],g[maxb][maxn],tmp[maxb];
arr cnt;
inline ele calc(ele l,ele r,ele x){
	if (l/S<r/S) return cnt[x]+g[r/S-1][x]-g[l/S][x];
	else return cnt[x];
}
int main(){
	scanf("%d%d%d%d",&n,&w,&q,&ty);
	for (int i=0; i<n; ++i) scanf("%d",a+i);
	S=sqrt(n); bcnt=0;
	for (int i=0; i<n; i+=S,++bcnt)
		for (int j=i; j<n && j<i+S; ++j) ++g[bcnt][a[j]];
	for (int i=1; i<bcnt; ++i)
		for (int j=0; j<n; ++j) g[i][j]+=g[i-1][j];
	memset(f,0,sizeof(f));
	for (int i=0; i<bcnt; ++i){
		++cnt.t;
		memset(tmp,0,sizeof(tmp));
		for (int j=i*S; j<n; ++j){
			if (cnt[a[j]]==w) tmp[a[j]/S]-=w;
			else if (cnt[a[j]]<w) ++tmp[a[j]/S];
			++cnt[a[j]];
			if ((j+1)%S==0 || j==n-1) memcpy(f[i][j/S],tmp,sizeof(tmp));
		}
	}
	ele ans=0;
	while (q--){
		ele l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		l^=ty*ans; r^=ty*ans; k^=ty*ans;
		--l,--r;
		if (l/S==r/S){
			++cnt.t; memset(tmp,0,sizeof(tmp));
			for (int i=l; i<=r; ++i){
				if (cnt[a[i]]==w) tmp[a[i]/S]-=w;
				else if (cnt[a[i]]<w) ++tmp[a[i]/S];
				++cnt[a[i]];
			}
		}
		else{
			++cnt.t; memcpy(tmp,f[l/S+1][r/S-1],sizeof(tmp));
			for (int i=l; i<(l/S+1)*S; ++i){
				ele t=calc(l,r,a[i]);
				if (t==w) tmp[a[i]/S]-=w;
				else if (t<w) ++tmp[a[i]/S];
				++cnt[a[i]];
			}
			for (int i=r/S*S; i<=r; ++i){
				ele t=calc(l,r,a[i]);
				if (t==w) tmp[a[i]/S]-=w;
				else if (t<w) ++tmp[a[i]/S];
				++cnt[a[i]];
			}
		}
		ele i=0;
		while (i<bcnt && k>tmp[i]) k-=tmp[i],++i;
		if (i==bcnt) ans=n;
		else{
			i*=S;
			for (; i<n; ++i){
				ele t=calc(l,r,i);
				if (t>w) continue;
				if (k>t) k-=t; else break;
			}
			ans=i;
		}
		printf("%d\n",ans);
	}
	return 0;
}