省选讲课-文档资料

1、1杭州学军中学 李超23关于线段树的基础问题 单点修改，单点询问 单点修改(+)，区间询问(sum) 区间修改，单点询问 区间修改，区间询问 打标记！ 标记下传4Lucky Queries 给定一个长度为N的01串 要求支持以下两种操作： 1.将一个区间的每个数异或1 2.求给定区间的最长不下降子序列长度 N=106 操作数M=3*105Source: CF145E5 线段树 维护每个节点的最长0-0 , 0-1 , 1-0 , 1-1串的长度 对于修改操作，只需要分别交换0-0与1-1 , 0-1与1-0的信息即可 O(N+MlogN)6 如果将2操作改为： 求给定区间的最长不下降子串长度

2、怎么办？ 维护：段内最长0-0,0-1,1-0,1-1子串 包含左、右端点的最长0-0,0-1,1-0,1-1子串 复杂度仍为O(N+MlogN)7大都市 给定一棵N个点的树，每条边边权均为1 共N+M-1次操作 把一条边边权从1变为0 询问根节点到一个点所经过的边的权和 N=250000 M 将一棵子树的答案均减少1 由于子树的节点在DFS序列上连续 维护DFS序即可 O(N+M)logN)9堵塞的交通 给定一个2*N的矩形网格 要求支持以下操作： 1.加入一条边 2.删除一条边 3.询问两个点是否连通 加入和删除的边一定在矩形网格上 N=100000 操作数M=100000Source:

3、SHOI200810 由于删除操作的存在，并查集不可行 维护区间内四个角之间的连通性 考虑两个点可能的连接方式 询问分两种情况 直接从中间经过 先往外侧再往中间 O(N+MlogN)11Sum of Medians 维护以下三种操作： 1.加入一个数 2.删除一个数 3.设当前集合为S=A1,A2,A3,.,Ak， (A1=A2=A3=.=Ak) 求sigma(Ai) (i=k) AND (i MOD 5=3) 总操作次数N=100000，加入与删除的数均为正整数且不超过109Source: CF85D12 这里只讨论线段树的做法 离散化 对于每个区间，维护以前5个数为开头的，隔5个数的和 例

4、如，若区间含7个数B1,B2,B3,B4,B5,B6,B7，我们需要记录B1+B6,B2+B7,B3,B4,B5。 显然父节点可以由子节点合并得到 O(NlogN)13GSS4 给定一个包含N个正整数的序列 N个数的和SUM不超过1018 要求支持以下操作： 1.对于一个区间的每个数X，令它变为floor(sqrt(X) 2.求一个区间的总和 N=10000014 一个数到1之后就不会再变了 每个数最多被更新loglogSUM次！ 暴力更新，维护区间和即可 O(NlogNloglogSUM)15Blue Mary开公司 维护一个数据结构支持以下操作: 1.插入一条直线y=kx+b 2.求所有直

5、线在某个x处的y最大值 0k100,-1e6=b=1e6, k,b为实数 1=x=50000 x为整数 总操作次数不超过100000Source: JSOI200816 平衡树！ 维护交点横坐标(斜率) 插入直线： 找到斜率比它大且最小的直线，判断并删除 找到斜率比它小且最大的直线，判断并删除 加入该直线 O(NlogN)17题目改编 维护一个数据结构支持以下操作: 1.插入一条线段y=kx+b L=x=R 2.求所有线段在某个x处的y最大值18 线段树做法 每次相当于对线段树的一个区间打上标记 合并标记 线段存在优势区间 将优势区间较小的线段下传到它占优势的区间 每次询问只需自底向上遍历一遍

6、 O(Nlog2N)19 对于插入直线的情况(Blue Mary开公司) 每次只在根节点打上标记 O(NlogN) 代码非常短20Flights 给N条抛物线(只考虑在第一象限的情况) 询问是一个四元组(i,j,l,r)，表示问第i到第j条抛物线在l,r的x坐标区间上的y坐标最大值 抛物线条数N=50000 询问个数M=20000Source: NEERC201121 答案出现的位置有三种情况 在L处所有抛物线中y值的最大值 在R处所有抛物线中y值的最大值 最值在L,R中的抛物线的最值 对N条抛物线建线段树 每个节点记录这些抛物线组成的上边界 每个节点可以由两个子节点合并得到 解决前两种情况22 对于第三种情况 RMQ 总复杂度为O(NlogN+Mlog2N) 完美解决23 zkw线段树 函数式线段树 ChairTree Trie 树套树 树链剖分 ZJOI2011 道观之战 ZJOI2007 树的统计24区间第K大 给一个长度为N的整数序列 要求维护两种操作 1.修改一个数 2.求一个区间中第K大的元素Source: 经典问题25 二分答案 转化为询问比一个数小的数有几个 线段树套平衡树 O(NlogN+Mlog3N) 线段树套字母树 O(N+M)log2N)26树的统计 给定一个N个节点的树 每个节点有一个权值 要求支持以下操作： 1.修改一个点的权值 2.询问两点