【洛谷P1198】最大数【分块】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P1198
现在请求你维护一个数列，要求提供以下两种操作：

1. 查询操作。
   语法：$Q\ L$Q L
   功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
   限制：$L$L不超过当前数列的长度。$(L>0)$(L>0)
2. 插入操作。
   语法：$A\ n$A n
   功能：将$n$n加上$t$t，其中$t$t是最近一次查询操作的答案（如果还未执行过查询操作，则$t=0$t=0)，并将所得结果对一个固定的常数$D$D取模，将所得答案插入到数列的末尾。
   限制：$n$n是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

思路：

$M\leq200000$M≤200000
分块啊。
由于确定了最终数字不会超过$2\times 10^5$2×105，所以就可以直接确定分成$\sqrt{2\times 10^5}$2×105​个块，使用计算器得

那就将一个块设置成$448$448就好了。
对于一个插入操作，判断是否需要建立一个新的块。然后将数据储存进去。
对于一个查询操作，按照朴素的分块求法求$[n-x+1,n)$[n−x+1,n)的最大值即可。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=200010;
const int T=448;
int n,m,MOD,x,t,a[N],L[T],R[T],maxn[T],pos[N],ans;
char c;

int find_max(int l,int r)  //暴力求l到r的最大值
{
	int Maxn=-2147483648;
	for (int i=l;i<=r;i++)
		Maxn=max(Maxn,a[i]);
	return Maxn;
}

int ask(int l,int r)
{
	int q=pos[l],p=pos[r];
	if (q==p) return ans=find_max(l,r);  //直接暴力求
	int Maxn=max(find_max(l,R[q]),find_max(L[p],r));  //两边暴力求
	for (int i=q+1;i<p;i++)
		Maxn=max(Maxn,maxn[i]);
	return ans=Maxn;
}

int main()
{
	scanf("%d%d",&m,&MOD);
	while (m--)
	{
		c=getchar();
		while (c!='A'&&c!='Q') c=getchar();
		scanf("%d",&x);
		if (c=='A')
		{
			a[++n]=(int)(((ll)x+(ll)ans)%MOD);  //此处会炸int，切记用long long！
			if (n%T==1)  //建立新块
			{
				t++;
				L[t]=R[t]=R[t-1]+1;
			}
			else R[t]++;
			pos[n]=t;
			maxn[t]=max(maxn[t],a[n]);
		}
		else printf("%d\n",ask(n-x+1,n));
	}
	return 0;
}

题外话

$论随意使用cin的后果$论随意使用cin的后果