记录编号	273227	评测结果	AAAAA
题目名称	[HZOI 2015]QAQ的序列	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.378 s
提交时间	2016-06-20 08:50:21	内存使用	432.83 MiB

#define maxb 350ul
#define maxn 100010ul

#include <map>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

int n,q,bsiz,btot,tot,cnt,bet[maxn],seq[maxn],L[maxb],R[maxb],utot[maxb][maxn];
std::map<int,int> mp; int T,sta[maxn],mark[maxn],appear_time[maxn],ep[maxb][maxn],pr[maxb][maxb][maxb];

void read(int &x){
	x=0; register int c=getchar(); for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) x=(x*10)+(c^48); return;
}

int count_upper(int l,int r,int k){
	int ans=0;
	for(int i=1;i<=cnt;i++)
		if(utot[i][r]-utot[i][l-1]==k) ++ans;
	return ans;
}

void add(int x){
	if(mark[x]!=T) mark[x]=T,appear_time[x]=0;
	++appear_time[x]; return;
}

int violent(int l,int r,int k){
	static int rp[maxb]; ++T;
	for(int i=0;i<=bsiz;i++) rp[i]=0;
	for(int i=l,p,t;i<=r;i++){
		add(p=seq[i]),t=appear_time[p];
		if(t==1) ++rp[1];
		else --rp[t-1],++rp[t];
	} return rp[k];
}

int count_lower(int l,int r,int k){
	if(bet[l]==bet[r]) return violent(l,r,k);
	int u=bet[l],v=bet[r],top=0; int ans=pr[u+1][v-1][k];
	++T; for(int i=l,p;i<=R[u];i++){
		p=seq[i]; if(mark[p]!=T){
			sta[++top]=p,mark[p]=T,appear_time[p]=1; if(ep[v-1][p]-ep[u][p]==k) --ans;
		} else ++appear_time[p];
	} for(int i=L[v],p;i<=r;i++){
		p=seq[i]; if(mark[p]!=T){
			sta[++top]=p,mark[p]=T,appear_time[p]=1; if(ep[v-1][p]-ep[u][p]==k) --ans;
		} else ++appear_time[p];
	} for(int i=1,p;i<=top;i++){
		p=sta[i]; if(appear_time[p]+ep[v-1][p]-ep[u][p]==k) ++ans;
	} return ans;
}

void prepare(){
	for(int i=1;i<=n;i++) bet[i]=(i-1)/bsiz+1;
	for(int i=1;i<=n;i++){
		R[bet[i]]=i; if(!L[bet[i]]) L[bet[i]]=i;
	} btot=bet[n];
	for(int i=1;i<=n;i++) ++appear_time[seq[i]];
	for(int x=1;x<=tot;x++) if(appear_time[x]>bsiz){
		++cnt;
		for(int i=1;i<=n;i++) utot[cnt][i]=utot[cnt][i-1]+(seq[i]==x);
	} for(int i=1;i<=btot;i++){
		memcpy(ep[i],ep[i-1],sizeof(ep[i]));
		for(int j=L[i];j<=R[i];j++) ++ep[i][seq[j]];
	} for(int i=1;i<=btot;i++){
		memset(appear_time,0,sizeof(appear_time));
		for(int j=i;j<=btot;j++){
			memcpy(pr[i][j],pr[i][j-1],sizeof(pr[i][j]));
			for(int k=L[j];k<=R[j];k++){
				int p=seq[k]; ++appear_time[p];
				if(appear_time[p]==1) ++pr[i][j][1];
				else{
					--pr[i][j][appear_time[p]-1];
					if(appear_time[p]<=bsiz) ++pr[i][j][appear_time[p]];
				}
			}
		}
	} return;
}

int main(){
	freopen("QAQ_seq.in","r",stdin);
	freopen("QAQ_seq.out","w",stdout);
	read(n); bsiz=(int)(sqrt(n)+1);
	for(int i=1,x;i<=n;i++){
		read(x); if(!mp.count(x)) mp[x]=++tot;
		seq[i]=mp[x];
	} prepare(); read(q);
	for(int i=1,ans=0,l,r,k;i<=q;i++){
		read(l),read(r),read(k);
		l=(l+ans)%n+1,r=(r+ans)%n+1;
		if(l>r) std::swap(l,r);
		if(k>bsiz) printf("%d\n",ans=count_upper(l,r,k));
		else printf("%d\n",ans=count_lower(l,r,k));
	} return 0;
}