企业官网建设流程全解析

保定网站建设方案报价,江苏省住房城乡建设部网站,百度地图推广一年多少钱,宁波核心关键词seo收费简介 本篇介绍一道单调栈的模板题#xff0c;为洛谷黄题目#xff0c;希望读者阅读完本篇之后可以阅读一下刷题日记day10(单调队列)配合食用效果更佳 前置知识 异或运算的性质 本题的运算中只运用到了这三种性质#xff0c;剩余的性质我们放在该篇的末尾 题目描述 …简介本篇介绍一道单调栈的模板题为洛谷黄题目希望读者阅读完本篇之后可以阅读一下刷题日记day10(单调队列)配合食用效果更佳前置知识异或运算的性质本题的运算中只运用到了这三种性质剩余的性质我们放在该篇的末尾题目描述B3666 求数列所有后缀最大值的位置B3666 求数列所有后缀最大值的位置题目描述给定一个数列a aa初始为空。有n nn次操作每次在a aa的末尾添加一个正整数x xx。每次操作结束后请你找到当前a aa所有的后缀最大值的下标下标从 1 开始。一个下标i ii是当前a aa的后缀最大值下标当且仅当对于所有的i j ≤ ∣ a ∣ i j \leq |a|ij≤∣a∣都有a i a j a_i a_jai​aj​其中∣ a ∣ |a|∣a∣表示当前a aa的元素个数。为了避免输出过大请你每次操作结束后都输出一个整数表示当前数列所有后缀最大值的下标的按位异或和。输入格式第一行是一个整数表示操作次数n nn。第二行有n nn个整数依次表示n nn次操作所添加的整数x i x_ixi​。输出格式每次操作后请输出一行一个整数表示当前数列所有后缀最大值下标的按位异或和。输入输出样例 #1输入 #15 2 1 3 5 4输出 #11 3 3 4 1说明/提示数据规模与约定对于全部的测试点保证1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^61≤n≤1061 ≤ x i 2 64 1 \leq x_i \lt 2^{64}1≤xi​264。请注意大规模数据输入输出对程序效率产生的影响。思路分析由题意可知我们要维护这样一个单调递减的序列并存储它的下标进行异或运算需要注意的是我们每一个输出的ans都是在考虑完第i个元素后当前栈中下标的异或总和有些数字可能后续会被弹出栈中为了简化运算避免每次都要将栈中的元素计算一遍(这样就会超时)所以我们采用如下计算方法。异或和的计算我们在弹出元素前进行一次异或操作在加入元素后进行一次异或操作。为了保持单调栈的结构我们后续会将一些之前压入栈的元素弹出此时为了保证我们要输出的答案是考虑第i个元素后完整的单调栈元素的异或和我们就要进行ans^stk.top();这个操作请大家仔细想想这个元素是不是第二次乘到ans当中(这个非常重要)联系到我们前面的性质这个stk.top()的下标是不是就从异或总和中剔除了讲到这里大家应该就明白了通过这个操作我们每次只需要o(1)就能算出答案。代码展示#includeiostream#includealgorithm#includestackusingnamespacestd;typedefunsignedlonglongll;constintN1e610;intn,ans;stackintstk;ll a[N];intmain(){scanf(%d,n);for(inti1;in;i)scanf(%llu,a[i]);for(inti1;in;i){while(!stk.empty()a[stk.top()]a[i]){ans^stk.top();stk.pop();}stk.push(i);ans^i;printf(%d\n,ans);}return0;}细节问题注意严格单调递减与B3667的联系(在简介提到的那篇题解当中)在P3667中我们是需要保证区间的长度恒定为k所以在后续我们不断加入元素的过程中假设我们此时已经把第i个元素加入容器当中且容器的首元素值小于i-k1(即小于左边界)(B3666为栈B3667为队列)我们需要把超出容器长度的部分删掉但是我们的栈是没有弹出容器头部元素操作的所以我们采用双端队列deque。我感觉这样的解释其实更符合B3667题目的思路AI注释后的代码#includeiostream#includealgorithm#includestackusingnamespacestd;typedefunsignedlonglongll;// 重定义无符号长整型存储输入的大数x避免溢出constintN1e610;// 数组最大长度适配1e6次操作intn,ans;// n操作次数ans当前后缀最大值下标的异或和初始默认为0异或的单位元stackintstk;// 单调栈存储后缀最大值下标栈内下标对应a值严格递减ll a[N];// 存储每次添加的正整数xintmain(){// 输入操作次数nscanf(%d,n);// 输入n次操作的x值存入数组a下标从1开始for(inti1;in;i)scanf(%llu,a[i]);// 遍历每次操作维护单调栈并计算异或和for(inti1;in;i){// 维护单调栈移除不再是后缀最大值的下标// 若栈顶下标对应的值 ≤ 当前值a[i]则栈顶下标失去后缀最大值资格while(!stk.empty()a[stk.top()]a[i]){ans^stk.top();// 异或自反性x^x0将栈顶下标从异或和中移除stk.pop();// 弹出栈顶无效下标}stk.push(i);// 新下标i加入栈i一定是后缀最大值下标ans^i;// 将i加入异或和0^ii非0则累加printf(%d\n,ans);// 输出当前所有后缀最大值下标的异或和}return0;}异或运算的性质后续的多个性质其实都和第一个性质有着密切联系