[luogu*] P1198 [JSOI2008]最大数 二分+单调栈 || ST表

前言

因为前两场cf二分打的很烂,特来补一下。没想到单调栈也很烂

传送门 :

思路

既然是二分搜索到这题的,那么这题一开始就是二分的了

但是你发现,我不可能直接使用STL COPY每段吧,然后对于每一段都排序吗

但是排序的意义完全就不要二分了而且会T

所以我们会想到一个非常美妙的结构,单调栈

我们用两个单调栈维护下标和数值的时候

我们就可以通过下标进行二分 然后直接输出答案即可

Seach-Code

int n,m,t;
ll ans;
ll stk[2][N],top,cnt;
int mod;

void add(int k)
{
	cnt++;
	while(k>stk[1][top] && top>0)
	top--;
	stk[0][++top] = cnt;
	stk[1][top] = k;
}
void query(int e,int l,int r)
{
	while(l>1;
		if(stk[0][mid]>op;
		if(*op !='A' && *op!='Q')
		getchar();
		if(*op == 'A')
		{
			int x;cin>>x;
			add((ans+x)%mod);	
		}else
		{
			int x;cin>>x;
			query(cnt-x+1,1,top);
		}
	}

}