公众号链接网站都是怎么做的,赚钱做网站,营销型网站建设应该注意什么,黄冈智能网站建设平台P1198 [JSOI2008]最大数 267通过1.2K提交题目提供者该用户不存在标签线段树各省省选难度提高/省选-提交该题 讨论 题解 记录 最新讨论 WA80的戳这QwQBZOJ都过了#xff0c;洛谷竟然过不了…为什么过不了 我想说这题加优读会WA#xff1f;…谁说pascal只能80#xff0c;要换c… P1198 [JSOI2008]最大数 267通过1.2K提交题目提供者该用户不存在标签线段树各省省选难度提高/省选- 提交该题 讨论 题解 记录 最新讨论 WA80的戳这QwQBZOJ都过了洛谷竟然过不了…为什么过不了 我想说这题加优读会WA…谁说pascal只能80要换c…线段树为什么是80 题目描述 现在请求你维护一个数列要求提供以下两种操作 1、 查询操作。 语法Q L 功能查询当前数列中末尾L个数中的最大的数并输出这个数的值。 限制L不超过当前数列的长度。 2、 插入操作。 语法A n 功能将n加上t其中t是最近一次查询操作的答案如果还未执行过查询操作则t0)并将所得结果对一个固定的常数D取模将所得答案插入到数列的末尾。 限制n是整数可能为负数并且在长整范围内。 注意初始时数列是空的没有一个数。 输入输出格式 输入格式 第一行两个整数M和D其中M表示操作的个数(M 200,000)D如上文中所述满足(0D2,000,000,000) 接下来的M行每行一个字符串描述一个具体的操作。语法如上文所述。 输出格式 对于每一个查询操作你应该按照顺序依次输出结果每个结果占一行。 输入输出样例 输入样例#15 100
A 96
Q 1
A 97
Q 1
Q 2输出样例#196
93
96说明 [JSOI2008] 分析这道题有很多种办法解决,首先可以发现数列中的数是递增的每次添加进去的数都比之前的大那么根据这个原理模拟一下就能做出来. 这道题可以用来练线段树为什么想到要用线段树呢注意区间二字在区间中查找最大值并且完成单点修改插入这不就是线段树的最基本的操作吗因为线段树可以全部赋值为-inf,所以插入操作可以理解为单点修改套用线段树的模板即可解决. 变量开成了全局变量查了一个晚上的错...... #include cstdio
#include cstring
#include iostream
#include algorithm#define le l,mid,o * 2
#define re mid 1,r,o * 2 1using namespace std;const int maxn 200001;int m, d,maxo[maxn 2],len,t;void build(int l,int r,int o)
{if (l r){maxo[o] -2147283647;return;}int mid (l r) 1;build(le);build(re);
}void charu(int l, int r, int o, int i, int j)
{if (l r) { maxo[o] j;return; }int mid (l r) 1;if (i mid)charu(le, i, j);else charu(re, i, j);maxo[o] max(maxo[o * 2], maxo[o * 2 1]);
}int query(int l, int r, int o, int x, int y)
{if (x l r y)return maxo[o];int mid (l r) 1;int temp -2147483647;if (x mid)temp max(temp,query(le, x, y));if (y mid)temp max(temp, query(re, x, y));return temp;
}int main()
{scanf(%d%d, m, d);build(1, maxn, 1);for (int b 1;b m;b){char c;int i;cin c;scanf(%d, i);if (c A) { len;charu(1, maxn, 1, len, (i t) % d); }else { t query(1, maxn, 1, len - i 1, len);printf(%d\n, t); }}return 0;
} 如果你还不会线段树那么可以参考一下下面这段文字(之前写的可能不是很好望体谅,可能也有一些不正确的只能当作参考): 线段树这个万能的树。 线段线段说白了就是一个区间,线段树主要的操作就是对区间进行修改查询效率非常高线段树的用途非常广单点更新、区间更新、最值询问、区间询问至于它具体能干哪些事取决于树里所储存的信息量。 这是一个线段树的图这个图只是能够帮我们理解线段树的大体形状并不能告诉我们更多信息其实线段树的更多功能都隐藏在每一个节点的信息背后为了能够更方便的做题我们给线段树的每一个节点标上序号。我们从上到下从左到右依次标号如果根节点的序号为k,那么它的左子树节点的序号则为2k,右子树节点的序号则为2k 1,每一个序号都对应着唯一一个节点所以我们可以用一个数组tree来表示这个节点背后所隐藏的信息。这个数组究竟开多大呢虽然在平常做题中我们不需要考虑的这么仔细但在一些内存限制非常紧的题目中这些都是要注意的。如果区间范围是[0,N-1],那么tree的大小M2*N 1,这个很好验证。 我们先来考虑如何建树一般来说只要到了叶子节点直接输入就好了但是我们怎么样才能够很快的到达叶子节点呢递归 int tree[2 * MAX_N 1]; /*建立以k为根节点[L,H]为操作区间的线段树*/ void built_tree(int k, int L, int H) { if (L H){ scanf(%d, tree[k]); return; } built_tree(k 1, L, (L H) 1); built_tree(k 1 | 1, (L H) 1 | 1, H); } 如果LH,证明当前区间的长度为1也就是此节点为叶节点可以直接赋值。 再来考虑一个经典问题求一个区间内的最小元素值。 这道题可以用暴力来做不过复杂度太高在一些题目中可能会TLE,我们可以看到区间二字那么这道题80%要用线段树来做当然也不是绝对只是效率高我们不断比较当前查询区间和目标区间如果当前查询区间在目标区间内那么当前深度所表示的节点便可以参与最小值计算如果不在区间内则返回无穷大否则则分别对当前树的左右子树进行相同运算可能术语话太强了. int read_tree(int k, int L, int H, int beg, int end) { if (beg H || end L) return -INT_MAX; if (beg L end H) return tree[k]; return min(read_tree(2 * k, L, (L H) / 2, beg, end), read_tree(2 * k 1, (L H) / 2 1, H, beg, end)); } 有查询就一定伴随着修改的存在如果是普通的数组修改很容易只需要对所需要操作的下标所对应的数据修改即可但是这是高效率数据结构修改就意味着要对许多量进行改变在线段树中我们对一个节点进行修改只需要对其及其所有的祖先进行修改即可其他量不变。 /*在根节点为k[L,H]为操作区间的线段树里对id处的值更新为key*/ int update_tree(int k, int L, int H, int id, int key) { if (L H){ tree[k] key; return; } if (id (L H) / 2) update(k * 2, L, (L H) / 2, id, key); else update(K * 2 1, (L H) / 2 1, H, id, key); tree[k] MAX(tree[k * 2], tree[2 * k 1]); } 这样便完成了修改操作. 然后是比较复杂的区间修改设计一个数据结构使它支持两种操作 Add(L,R,v)将AL,AL1…AR的值全部VQuery(L,R)计算子序列AL,AL1…AR的元素和最小值最大值。这里要维护三个查询值该怎么维护呢 首先这里的Add操作是区间修改并不是单点修改最糟糕的情况下可能整棵线段树的结点值都要被修改。我们知道线段树任意区间都能分解成不超过2h个不相交区间的并利用这个结论我们可以将每一个Add操作分解成不超过2h个的Add操作记录在线段树的结点中。每次执行完Add操作都要重新计算每个结点的附加信息递归访问到的结点全部都要重新计算并且是在递归返回后计算 下面给出计算的代码 void weihu(int o,int L,int R) { int lc o * 2, rc o * 2 1; sumv[o] minv[o] maxv[o] 0; if (R L) { sumv[o] sumv[lc] sumv[rc]; minv[o] min(minv[lc], minv[rc]); maxv[o] max(maxv[lc], maxv[rc]); } minv[o] addv[o]; maxv[o] addv[o]; sumv[o] addv[o] * (R - L 1); } 对于下面的代码来说,修改/查询的范围均为[y1,y2]. 这里的sumv数组要说一下为什么要用左右子结点相加得出呢首先父亲结点就包含了左右结点其次这样维护的时候就不需要修改全部的sumv数组的元素了。当然这里指的是特殊情况一般是那种极端数据的。 下面是Add操作的代码 void Add(int o, int L, int R) { int lc o * 2, rc o * 2 1; if (y1 L y2 R) addv[o] v; else { int M (L R) 1; if (y1 M) Add(lc, L, M); if (y2 M) Add(rc, M 1, R); } weihu(o, L, R); } 其中addv数组是累加边界的add值因为一棵线段树的子节点可能不知被修改一次所以有必要设立这个数组。 然后是查询操作话说用线段树步步都得谨慎感觉这句话没错啊每次进行操作都要考虑到结点对结点之间有没有影响我们查询一般都是从上往下递归查询既然一个结点的父结点执行了add操作而这个节点也被父节点包括在内所以这个节点的值肯定被改变了于是我们只能设3个全局变量来维护。 int _min, _max, _sum; void query(int o, int L, int R, int add) { if (y1 L y2 R) { _sum sumv[o] add * (R - L 1); \ _min min(_min, minv[o] add); _max max(_max, maxv[o] add); } else { int M (L R) 1; if (y1 M) query(o * 2, L, M, add addv[o]); if (y2 M) query(o * 2 1, M 1, R, add addv[o]); } } 看到很多人都弄混了好吧其实我也有点晕了。可能会有人问了为什么我们的weihu函数已经维护了现在还要维护呢因为weihu函数是从下到上的也就是从左右子节点维护的是相对于子节点所发生的变化而这里的全局变量是因为父节点进行了Add操作子节点包含在内所以要另开变量维护。如果还是搞不明白可以看到weihu函数最后只是修改了当前节点的值并没有维护到它的子节点所以要另开变量维护。 接下来是更加复杂的 Set(L,R,v)把AL,AL1...AR的值全部修改为v. Query(L,R)计算子序列AL,AL1...AR的三个值同上题. 可以看到这里变动的是Set操作我们说这道题比之前复杂为什么呢因为之前的Add操作不管操作次序如何都可以达到最后的结果前提是算法是对的代码没写错。然而Set操作则不同好比刷油漆最后刷的就是最终颜色。怎么办呢打标记这里的打标记则相当于对于被改变的特殊情况而做的变动是为了最后的求出三个值而打的那么怎么做呢如果当前区间完全被包含在我们需要修改/查询的区间内则直接修改标记为v,否则则标记下传。 void pushdown(int o) { int lc o * 2, rc o * 2 1; if (setv[o] 0) { setv[lc] setv[rc] setv[o]; setv[o] -1; } } 这里的setv数组即为标记注意到这个数组被初始化为-1这里不要搞错了那么问题来了为什么我们要清除父节点的标记呢 接下来Set操作代码 void Set(int o, int L, int R) { int lc o * 2, rc o * 2 1; if (y1 L y2 R) { setv[o] v; } else { pushdown(o); int M (L R) 1; if (y1 M) Set(lc, L, M); else maintain(lc, L, M); if (y2 M) Set(rc, M 1, R); else maintain(rc, M 1, R); } maintain(o, L, R); } 注意到3次maintain最后一次很好理解因为我们之前讲过每一次递归完后都必须要维护一次那么前两次又是为何呢因为标记一旦下传则该子树的附加信息需要改变当前区间内的子树在递归完后自然会进行维护不过另一个区间内的子树则没有被维护因此需要加上两次maintain函数的调用。 接下来是query操作的代码 void query(int o, int L, int R) { if (setv[o] 0) { _sum setv[o] * (min(R, y2) - max(L, y1) 1); _min min(_min, setv[o]); _max max(_max, setv[o]); } else if (y1 L y2 R) { _sum sumv[o]; _min min(_min, minv[o]); _max max(_max, maxv[o]); } else { int M (L R) 1; if (y1 M) query(o * 2, L, M); if (y2 M) query(o * 2 1, M 1, R); } } 对于有标记的区间我们要优先处理首先知道当前区间都被修改为setv[o],既然所有值都是一样的自然就是对其进行操作然后再考虑被所要查询的区间所完全包围。回到之前的问题上来为什么我们要清除父节点的标记呢我们将标记下传一般都是传到被所要查询的区间所完全包围的区间因为子节点的区间内的值就包含了大区间的值换句话说所求的结果就是几个小区间的并而这几个小区间则是分解到不能再分解为止自然我们将父节点的标记消除因为子节点才是影响到结果的根本我们求的值最终也在子节点进行所以要消除. 转载于:https://www.cnblogs.com/zbtrs/p/5851173.html
