HYSBZ - 1012 最大数maxnumber-白红宇

HYSBZ - 1012 最大数maxnumber

阅读量：4144 次

发布时间：2019-05-25

本文共 2494 字，大约阅读时间需要 8 分钟。

题目:https://vjudge.net/problem/HYSBZ-1012

真的是一点点东西都搞不完....要么你就在这屋里搞四十分钟再出去玩一会儿要么就直接别搞

学不好也玩不痛快

"你不是明明也很喜欢这东西吗喜欢就去做啊"

7 100 97 98 96 102 4 2

//195 291 393 ???

C 最大数

【为什么是单调栈呢？】

因为，可以把排在这个元素前的比它小的数直接忽略了（因为查询的区间永远都是后L个数，所以…….）

【高效系列.. 大概吧】

while (top>0 && a[top] <= x)

top--;

a[++top] = x;//x给a[1]

b[top] = ++num;

下面代码里那些狗屁注释是以前写的完全可以不看,核心思想我懂了:

所谓单调栈,并不是说它就是一个单调栈,而是它的形式维护得就像是从小到大的单调栈,因为查询的时候是按照加入,A,的顺序来的,又从后面往前询问,他们不得不就像一个先进后出的栈一样排列。

此外，由于只需要查询到最大的，所以num记录了他们的总数，如果后面的是在递减没有关系，一旦后面出现一个大的，就满足了“在后多少个数里面我最大”的性质，有点像之前做过的那个区间最大值的题--两边各取最大值

参考题目：分成几个区间。

https://vjudge.net/contest/210103#problem/B

他是不得不就像单调栈一样啊。。。

else

{

x = num - x + 1;

//x这样,因为是从后往前的,数字这样倒替的话,通常都会+1

因为是从后往前的!!!!

printf("%d\n", ans = a[lower_bound(b + 1, b + top + 1, x) - b]);

}

//lower_bound是针对x找到一个位置,b里面存着的是++num只是序号罢了,b里面只需要找从开头到top那么多,假设只有3个,找从头开始第x个(也就是从后往前第x个,此时x已经被更新过了,一样的)

那么b仅仅只是一个下标而已

a对应那个下标,把值搞出来

这里面不对。数据是这样的，但序号不是

2. 和二分有什么关系?

3.线段树怎么做?

我不知道...能搜出来好多,掌握一种就好了,我妖去打阴阳师了

4.对这个题而言..特别要注意一下

其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0

【t不是时时更新的】

如下代码，然后里面ans在"A时是不管用的,"Q"了才重新初始化

5.沉迷代码,就像玩游戏一样啊!!!!!做到

单调栈代码

//能接触到的很优秀的人

#include
   
      #include
    
       #include
     
        #include
      
         #include
       
        using namespace std;typedef long long ll;#define maxn 200005  int a[maxn], b[maxn];int main(void){	char c;	int n, d, num = 0, x, top = 0, ans = 0;	scanf("%d%d", &n, &d);//  d　ｉｓ　how large it can b e?	for (int i = 1; i <= n; i++)	{		//cin >> c >> x;		scanf(" %c%d", &c, &x);		if (c == 'A')		{			x = (x + ans) % d;			//单调栈的维护.....			while (top>0 && a[top] <= x)				//如果首部大于0,..  并且x更大的话... 				//如果top==2   a[2]<=x 那么top'--				//一直到 a[2]>=x 要更大 				//也就是前面是大的  后面是小的 这个是为了维护单调				//???为什么要维护....//  a[2]<=x 就是要改嘛,要a[2]>=x才行,前面的大,后面的小,不过为什么呢								top--;			a[++top] = x;//x给a[1]			b[top] = ++num;//b[1]...他们是差不多的啊  num是什么		}		else//如果是Q 的话,看看后面要有多少个		{			x = num - x + 1;//  num-x+1 倒数几个啊...  用luwer_bound是找到他那个值,没错儿,而x是倒数第几个  又减一好像似曾相识			printf("%d\n", ans = a[lower_bound(b + 1, b + top + 1, x) - b]);//  因为要单调所以是top?不理解题意...太晚了		}	}	return 0;}