题目链接 题意：长度为n的序列，单点更新，或者询问某一个区间中最长连续严格递增序列的长度是多少。（此处的连续为位置连续，并非数值连续，也就是3,5,7,9，这样的就是满足题意的长度为4的序列） 思路：线段树区间合并。维护三个域。 mx:区间中最长连续严格递增序列的长度 lm:包含区间左端点的最长连续严格递增序列的长度。 rm:包含区间右端点的最长连续严格递增序列的长度。 PushUp的时候，一个区间的答案显然可以从左右两个子区间的最大值得到。 还有一种可能是左右区间各取一部分，此时必须满足左区间的右端点值严格小于右区间的左端点值。 需要注意的是，如果某区间的最长连续严格递增子序列的长度等于区间长度，那么该区间可以向相应方向延伸。 查 …

题目连接 题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数） 思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西,这也是次题的突破口) mex(1,i)可以O(n)维护出 现在我们考虑左端点向右移动对答案的影响。 当i移动到i+1时，此时序列中少了a[i]，设r为最小的x，满足a[x]=a[i]，那么当右断点在区间[r+1,n]，mex值是没有改变的。 当右端点属于[i+1,r-1]时，mex大于a[i]的会变成a[i]。 由于我们知道从1到某区间的mex值是单调的，那么mex大于a[i]的点必然 …

题目链接 题意：给一个仅由小写字母组成的字符串，然后m个操作，每个操作一个区间，要求把区间中排列成字典序最小的回文串，如果不能形成回文串，就忽略该操作。 思路：和上一道线段树优化计数排序的题目很像，几乎是一样的。 同样的，26棵线段树，每种字母对应一棵。 每次统计询问区间中每种字母的个数。 然后先判断是否能形成回文（奇数长度只有一个个数为奇数的，偶数长度不能出现个数为奇数的） 能的话重置区间，然后前后分别覆盖。 注意如果是奇数长度的话，记得先覆盖中间点。 需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1 然而Tle 19....Tle了好久。。。 最后换了种线段树的写法就过了。。。 然而后面这种写法就 …

题目链接 题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。 思路：首先，最重要的一点是，由于只有26个字母，联想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 那么我们回顾计数排序，不妨考虑升序排列的情况，是怎么做的呢？ 做法是统计该区间中每种字符的个数，然后按照字符的大小，从小到大在区间上从左到右得放置每种字符。 大概是这样子： for(int j=x;j<=y;j++) cnt[s[j] - …

题目链接 题意：给出一串只由数字'4'和'7'组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的没个数反转，反转的定义为，4变成7,7变成4. 思路：线段树lazy标记。 线段树的域记录5个信息，c4,c7,c47,c74，flip,a分别表示4的个数,7的个数，非下降子序列的个数，非上升的子序列的个数，以及该区间是否被翻转。 纠结了很久PushUp操作。。。。 c4和c7倒是没什么疑问。。。。 一开始觉得c47是由三部分的最大值更新得到的。。。 left.c4+right.c47,left.c4+right.c7,left.c47+right.c7... 但是样例过不了。。。 纠结了 …

题目链接 题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。 思路：区间更新+区间询问的模板题.... 注意体会pushdown以及update的时候。。。 要同时更新tree数组和lazy数组。。。 读入的时候可以用sscanf判断操作类型。。。 /* *********************************************** Author :111qqz Created Time :Mon 26 Sep 2016 05:30:21 AM CST File Name :code/cf/problem/52C.cpp …

题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5​​ 个数（a[i] a​i​​≤1E4​​)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。 参考题解：茶姐的回答（下标好像搞错了，领会意思即可 官方题解 以及前置技能点是：斜率优化+线段树 思路：考虑一排数a[1]到a[n]，原问题可以转化成从a[y]走x-1步，每一步原地不动或者向左移动一个格子后的总的代价。 Function is calculated as follows: , k__i — how many times we …

题目链接 题意：给出一个由‘(’和‘）’组成的字符串。。。然后给出若干查询。。。每个查询一个区间，问区间中能匹配的括号数。。。 思路：考虑某一个区间中的括号匹配。。。其实是一个不断寻找'()'然后删去的过程。。。 因此对于某个区间的括号匹配数。。。等于左边区间和右边区间和合法匹配数之和，再加上左区间和右区间新的能匹配到一起的括号数。 （说“因此”是因为。。。只要左边有没匹配的左括号。。。右边有没匹配的右括号。。。因为他们中间有的都是匹配好的括号，会被删除。。。所以两边的括号总能匹配在一起） 具体做法是： 线段树的节点中有三个域，分别表示，合法的括号匹配数，没有被匹配的左括号数，和没有被匹配的右括号数。 query的时候要合并左右两个 …

poj 2886 题目链接 题意：n个人围成一圈，每个人身上由一个数，可正可负。从第k个人开始出圈，如果第k个人身上的数是X,X>0，就左边第x个没有出圈的人出圈，否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k)，f(x)表示x的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。 思路：看起来好像很麻烦。。其实可以分解成两个问题。 第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数，而取决与上一次出队的人。。。 终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。 类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。 然后每次update的时候优先查 …

题目链接 题意：n只青蛙，第i只位于x[i],舌头长度为t[i]。m只蚊子，第i只蚊子所在位置为p[i],蚊子的大小为b[i]。 蚊子按照出现顺序输入。 一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。 当多只青蛙可以吃到同一只蚊子的时候，最左边的那只青蛙来吃。 当一只青蛙吃掉一只蚊子以后，青蛙的舌头增加蚊子的大小。 当一只青蛙吃掉一只蚊子后，因为舌头边长而又能吃到其他蚊子的时候，这只青蛙会继续吃，只到当前没有蚊子可以被任何一只青蛙吃到，在这个过程之后才会飞来下一只蚊子。 思路：问题的关键在于，对于某只蚊子，我们如何找到能吃到该蚊子的青蛙中最左边的那只。 可以抽象成寻找区 …