3161这个肯定用不了线段树至少用不了朴素的线段树因为区间是无限的这个题就是在不断修改这个数轴区间然后每次查询就是在查询0.x区间之内是否长度超过sz的区间可以先记录操作1所插的最远的那个地方为curMax然后维护当前所存在的最大区间长度max然后每次执行操作1的时候然后和curMax比较如果超过了之前保存的max不受影响但会产生一个新的区间即cur-curMax的区间长度那么尝试去更新max但如果没超过就会对已有的区间造成影响即会拆掉一个已有的大区间获得两个更小区间然后在查询的时候也是要和curMax去比较如果没超过没超过也比较麻烦因为此时的这个max可能就用不上了如果超过了max还能用上但也会产生一个新区间即query-curMax不过这个处理比较简单那还是很麻烦dp也不行因为不是最优子问题这个恰恰是线段树的题就是说叶子节点表示当前位置是否有障碍物然后就是要维护从左端开始向右的最长长度从右端开始向左的最长长度如果这个区间内的最长长度在中间也没关系因为往下递归时下面的区间也会拼好以及整个区间也会维护一个max_len即这个区间内部的最长连续长度在维护max_len时就是此区间的left_len和right_len以及左孩子的右区间开始最长长度和左区间开始的最长长度这三者之间的最大值但是左右区间最长长度这个怎么维护在查询时如果ql和qr,完全包含q和l那么就返回max_len如果只是部分包含怎么办如果只在左区间不过拆到最后一定会是要么全部包含要么左右都露出一部分的那种不过该怎么归纳从而划出代码形式这个线段树不涉及到区间修改没有懒修改没有Push_down的写法了取而代之的是push_up即单点修改向上提的写法就维护三个值leftright和max当到点更新时点上的这三个值为0然后Push_up所谓Push_up其实就是大区间内的小区间更新后对大区间所造成的影响小区间更新后大区间的left左边小区间的left如果长度等于左区间长度了还要再加上右区间的left关键在于查询在查询时返回的不再是一个数值而是三个数值即一个节点node然后节点即区间的合并就用push_up最后就返回合并好的节点最后由查询者来取节点当中的max不过push_down的参数是cur,l和r没问题因为就是向下找区间但push_up的参数还是只有cur,l和r吗因为cur相当于是一个小区间然后要往上去找其对应的更大区间这怎么知道自己的大区间总不能i/2找吧class Solution { public: vectorbool getResults(vectorvectorint queries) { int maxLen5e4,treeLenmaxLen*45; vectorinttree(treeLen),lmax(treeLen),rmax(treeLen); vectorboolfinalRes; auto merge[](int cur,int l,int r){ int mid(lr)1,lenmid-l1,rlenr-mid; lmax[cur]lmax[cur*2]; if(lmax[cur*2]len){ lmax[cur]lmax[cur*21]; } rmax[cur]rmax[cur*21]; if(rmax[cur*21]rlen){ rmax[cur]rmax[cur*2]; } tree[cur]max(lmax[cur],rmax[cur]); tree[cur]max(tree[cur],rmax[cur*2]lmax[cur*21]); }; auto build[](autoself,int cur,int l,int r){ if(lr){ tree[cur]1; lmax[cur]1; rmax[cur]1; return; } int mid(lr)1; self(self,cur*2,l,mid); self(self,cur*21,mid1,r); merge(cur,l,r); }; build(build,1,0,maxLen);//该是从1开始还是从0开始 auto update[](autoself,int cur,int l,int r,int q){ if(lr){ tree[cur]0; lmax[cur]0; rmax[cur]0; return; } int mid(lr)1; if(qmid){ self(self,cur*2,l,mid,q); } else{ self(self,cur*21,mid1,r,q); } merge(cur,l,r); }; struct Node { int len, left, right, maxv; }; functionNode(int, int, int, int, int) query[](int cur,int l,int r,int ql,int qr){ //if(lqr||rql){return;} if (ql l r qr) return Node{r - l 1, lmax[cur], rmax[cur], tree[cur]}; Node leftNode, rightNode; bool hasLeft false, hasRight false; int mid(lr)1; if(qlmid){//得到左边的 leftNode query(cur * 2, l, mid, ql, qr); hasLeft true; } if(qrmid){//得到右边的 rightNode query(cur * 2 1, mid 1, r, ql, qr); hasRight true; } //合并一下得到结果然后返回这个的三元组 if (hasLeft hasRight) { Node res; res.len leftNode.len rightNode.len; res.left leftNode.left; if (leftNode.left leftNode.len) res.left rightNode.left; res.right rightNode.right; if (rightNode.right rightNode.len) res.right leftNode.right; res.maxv max({leftNode.maxv, rightNode.maxv, leftNode.right rightNode.left}); return res; } else if (hasLeft) { return leftNode; } else { return rightNode; } }; for(auto question:queries){ int opquestion[0]; if(op1){ update(update,1,0,maxLen,question[1]); }else{ Node res query(1, 0, maxLen, 0, question[1]); finalRes.push_back(res.maxv1 question[2]); } } return finalRes; } };P2842 纸币问题 1dp[i]表示凑出i所用的最少纸币数量在确定每个dp[i]时是贪心吗即优先用大的大的不够用了用小的不是贪心那怎么状态转移呢就是说dp[i]状态由哪些状态转移过来呢就是去减num吧这样是状态转移过来的方式但是正确性如何证明即dp[i]min(dp[i],dp[i-a[i]]),ia[i]dd爱科学2.0这也没说x变成y那y的范围是多少就一个要求要求非递减难道二分搜索验证没什么思路P1012 [NOIP 1998 提高组] 拼数就是把数字按字典序来排然后把字典序高的放前面就行了就算不行由于n的范围小也可以dfs遍历解决vivado测试、时序指标流水线CPU开发板
