您的位置: 首页  >  文章  >  【JZOJ A组】 Queue

【JZOJ A组】 Queue

分类: 文章 • 2024-02-15 17:38:48

Description

Hack 国的居民人人都是 OI 大师，Hometown 得知便赶紧来到 Hack 国学习。可想要进入 Hack 国并不是件容易的事情，首先就必须通过 Hack 国海关小 B 的考验。小 B 觉得 Hometown 比较菜，于是就扔了一道小水题给 Hometown。
给定一个长度为 n 的数列 a i ，接下来会对这个序列进行 m 次操作。操作类型分为以下两种：
• 1 l r，表示将区间 [l,r] 轮转一次，具体来说，a l ,a l+1 ,a l+2 ,··· ,a r−1 ,a r 经过一次轮转之后，会变为 a r ,a l ,a l+1 ,··· ,a r−1 ；
• 2 l r k，询问区间 [l,r] 内 a i = k 的个数。
可惜 Hometown 还是不会做，他只能期待你能解决这个问题了。
【JZOJ A组】 Queue

Input

从文件queue.in中读入数据。
第一行两个整数 n,m，表示序列的长度与操作的次数。
第二行 n 个整数 a i ，表示这个序列。
接下来的 m 行，每行先是一个整数 opt 表示操作的类型。对于 opt = 1 的操作，接下来两个整数 l,r 表示将区间 [l,r] 轮转；对于 opt = 2 的操作，接下来三个整数 l,r,k 表示求区间 [l,r] 内等于 k 的值的个数。

Output

输出到文件queue.out中。
对于每个 2 操作，一行一个整数，表示这次询问的答案。

Sample Input

7 6
1 2 2 3 2 1 3
2 3 6 2
1 1 6
2 2 4 1
1 3 6
2 6 7 3
2 3 5 2

Sample 2
见选手目录下的queue/queue2.in与queue/queue2.ans。
该组样例的数据范围同第 2 个测试点。

Sample 3
见选手目录下的queue/queue3.in与queue/queue3.ans。
该组样例的数据范围同第 13 个测试点。

Sample Output

2
1
2
3

Explanation
对于第一次询问，区间 [3,6] 中一共出现了 2 次 2。
随后进行修改，修改之后序列变为 1,1,2,2,3,2,3。
对于第二次询问，区间 [2,4] 中一共出现了 1 次 1。
随后再次修改，修改之后序列变为 1,1,2,2,2,3,3。
对于第三次询问，区间 [6,7] 中一共出现了 2 次 3。
对于第四次询问，区间 [3,5] 中一共出现了 3 次 2。

Data Constraint

对于 100% 的数据，满足 0 ≤ n,m ≤ 10^5 ,1 ≤ a i ≤ n,1 ≤ l i ≤ r i ≤ n。除此之外，对于每个数据点，还满足以下限制。

思路

数据范围只有 105，然后数据结构不那么好维护，怎么办？分块！
其实想到了分块应该就很简单了。你只需要维护每个块内，每种颜色的出现次数。然后轮转就可以在每个块内用链表修改一下，查询就可以暴力统计边角料，暴力将每个整块内的答案加上来。

代码

#include<cstdio> 
#include<iostream>
#include<cmath>
#define N 200010
using namespace std;
int n,m,num,l,a[N],le[N],ri[N],cnt[450][N],k[N],d[505],last[505];
int fin(int x)
{
	int y=last[k[x]],w=min(n,num*k[x]);
	while (w>x) y=le[y],w--;
	return y;
}
void del(int x,int y)
{
	if (!x) return;
	if (le[x]) ri[le[x]]=ri[x];
	if (ri[x]) le[ri[x]]=le[x];
	cnt[y][a[x]]--;
	if (!le[x]) d[y]=ri[x];
	if (!ri[x]) last[y]=le[x];
}
void add(int x,int y,int z)
{
	if (!x) return;
	ri[le[x]=le[y]]=x,le[ri[x]=y]=x;
	le[0]=ri[0]=0,cnt[z][a[x]]++;
	if (!le[x]) d[z]=x;
	if (!ri[x]) last[z]=x;
}
int main()
{
	freopen("queue.in","r",stdin),freopen("queue.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (n==0) return 0;
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	num=n/sqrt(n),k[0]=1;
	for(int i=1; i<=n; i++)
	{	
		le[i]=i-1,ri[i]=i+1,l++;
		if (l>num)
		{
			l=1;
			k[i]=k[i-1]+1,last[k[i-1]]=i-1;
			d[k[i]]=i,le[i]=ri[i-1]=0;
		}
		else k[i]=k[i-1];	
		cnt[k[i]][a[i]]++; 
	}	
	ri[n]=0,last[k[n]]=n,d[1]=1;
	for(int i=1,l,r,op,z; i<=m; i++)
	{
		scanf("%d%d%d",&op,&l,&r);
		if (l==r) continue;
		if (op==1)
		{
			int x=fin(l),y=fin(r);
			del(y,k[r]),add(y,x,k[l]);
			for(int j=k[l];j<=k[r]-1;j++) 
			{
				int p=last[j];
				del(p,j),add(p,d[j+1],j+1);
			}
		}
		else
		{
			scanf("%d",&z);
			int x=fin(l),y=fin(r),ans=0;
			while (x&&x!=y) ans+=(a[x]==z),x=ri[x];
			while (y&&x!=y) ans+=(a[y]==z),y=le[y];
			if (x==y&&x!=0) ans+=(a[x]==z); else for(int j=k[l]+1;j<=k[r]-1;j++) ans+=cnt[j][z];
			printf("%d\n",ans);
		}
	}
}

相关推荐