P1198 [JSOI2008] 最大数https://www.luogu.com.cn/problem/P1198

牵制芝士：单调队列

思路：

我们的任务是找出一个区间最大值的

因为插入的数与上一次的答案有关 所以它是强制在线的（真无语了）

我们可以在每次插入时整一个叫做控制区间的东西

用来表示这个数在这一个连续的区间中是最大值

比如 经过处理后输入数列是

那么它们的控制区间就如下表

序号	1	2	3	4	5
值	3	5	4	1	2
控制区间	无	1~2	3~3	无	4~5

其中 第1个数会被第2个数“控制”

其中 第4个数会被第5个数“控制”

所以它们的区间被“吞并”了

在查询操作时

我们可以对控制区间进行二分 找出它所对应的值

那如何快速得到控制区间呢？

let us梳理一下过程

首先我们将第1个数存入 

在将第2个数存入 发现它之前的数小于它 就往前冲

将第1个数干掉

看到这 你是不是感觉到不太对劲 这不就是我们熟悉的单调队列吗？

之后便豁然开朗了吧

注：记得取模！

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,mod,sum,q[210000],t,cnt,p[210000];
signed main()
{
	scanf("%lld%lld",&m,&mod);
	while(m--)
	{
		char ch;
		int x;
		cin>>ch>>x;
		if(ch=='A')
		{
			x+=sum;
			x%=mod;
			while(t>0&&q[t]<=x)
			{
				t--;
			}
			q[++t]=x;
			p[t]=++cnt;
		}
		else
		{
			int l=1,r=t,st=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(p[mid]>=cnt-x+1)
				{
					st=mid;
					r=mid-1;
				}
				else
				{
					l=mid+1;
				}
			}
			sum=q[st];
			printf("%lld\n",q[st]);
		}
	}
	return 0;
}