搜索结果
查询Tags标签： 区间，共有 281条记录-
D K匹配 kmp 区间匹配计算贡献
链接：https://ac.nowcoder.com/acm/problem/213329来源：牛客网 题目描述牛牛是赫赫有名的字符串高手，现在牛牛发现了一种新的匹配方式。给定一个字符串SSS和一个字符串TTT，如果SSS存在一个长度为kkk的子串Sl1,l1+k−1S_{l_1, l_1 + k - 1}Sl1,l1+k−1和TTT的某个…
2022/9/12 23:23:15 人评论 次浏览 -
线段树上状压（位运算）
洛谷P1558 分析： 颜色类型只有 \(30\) 种,可以利用二进制进行状压。 线段树维护一个二进制数表示区间的颜色为哪一种，将这个区间的颜色进行状压，每一种颜色对应二进制数的某一位。合并区间时将两个子节点的数按位或即可，题目区间修改为直接覆盖，统计答案时只需统计对…
2022/9/8 23:56:10 人评论 次浏览 -
可持久化线段树
现想现写的，没有借鉴别人的任何东西。 可持久化线段树1 考虑不会变得太多，每次该值操作只会改变一个位置的值，其它位置是可以继承的。如果用数组，那就是下标继承。如果把数组分成 \(2\) 半，那改一个值，就一半继承，另一半重新赋值。而用线段树，就可以做到区间继承 …
2022/9/6 23:24:12 人评论 次浏览 -
[算法]区间归并
问题分析 有的时候,会遇到给定一系列的区间,求交集or并集,或者合并的题. 这些题的解题方式比较通用个,做一个总结. 会用到集合和归并排序的相关知识. 两个区间的关系有六种,如果我们首先对区间按照区间左边界进行排序,那么就会编程3中关系: A 包含 B ==> A[0] <= B…
2022/8/26 14:23:06 人评论 次浏览 -
[NOIP2001 提高组] 一元三次方程求解
题目链接：https://www.luogu.com.cn/problem/P1024 试题分析： 三个答案都在[-100,100]范围内，两个根的差的绝对值>=1,保证了每一个大小为1的区间里至多有1个解，也就是说当区间的两个端点的函数值异号时区间内一定有一个解，同号时一定没有解。那么我们可以枚举互相…
2022/8/22 23:22:45 人评论 次浏览 -
一元三次方程
根的绝对值>=1,可知在区间[i,i+1]内最多只有一个解。将（-100,100）for 循环分成若干区间令l=i,r=i+1;判断f(l)是否为0，再判断f(r)是否为0，如果为0，直接跳过。当左右点都不为0时走到下一步利用二分，判断。 当f(mid)*(r)>0 那么可知根一定在左边区间 即r=mid,否则…
2022/8/22 23:22:45 人评论 次浏览 -
Maximum Segment Sum After Removals
Maximum Segment Sum After Removals You are given two 0-indexed integer arrays $nums$ and $removeQueries$, both of length $n$. For the $i^{th}$ query, the element in $nums$ at the index $removeQueries[i]$ is removed, splitting $nums$ into different seg…
2022/8/21 23:54:27 人评论 次浏览 -
洛谷 P6242 【模板】线段树 3 吉司机线段树 区间取最小值 维护历史最大值和区间和
题目背景本题是线段树维护区间最值操作与区间历史最值的模板。题目描述给出一个长度为 nn 的数列 AA，同时定义一个辅助数组 BB，BB 开始与 AA 完全相同。接下来进行了 mm 次操作，操作有五种类型，按以下格式给出：1 l r k：对于所有的 i\in[l,r]i∈[l,r]，将 A_iAi 加…
2022/8/16 6:23:25 人评论 次浏览 -
IOI 2022 题解 & 锐评
IOI 2022 D1T1 Fish 题目大意： 有一个 \(N\times N\) 的网格，其中的 \(M\) 个位置有垒球，第 \(i\) 个垒球的位置为 \((x_i,y_i)\)，重量为 \(w_i\)。 你可以为每一列 \(c\) 选择一个前缀的行 \(1,2,\ldots,\ldots,r_c\) 修建长堤，这样 \((1,c),(2,c),\ldots,(r_c,c)\)…
2022/8/13 23:24:51 人评论 次浏览 -
1032 换个角度思考 树状数组 离线算法 区间有多少小于等于k的数
链接：https://ac.nowcoder.com/acm/contest/26896/1032来源：牛客网 题目描述给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数 即对于询问 (l,r,x)，你需要输出 ∑i=lr[ai≤x]\sum_{i=l}^{r}[a_i \le x]∑i=lr[ai≤x] 的值 其中 [exp] 是一个函…
2022/8/13 14:23:37 人评论 次浏览 -
1033 [SDOI2009]HH的项链 树状数组 离线操作 每个区间出现多少种不同的数
链接：https://ac.nowcoder.com/acm/contest/26896/1033来源：牛客网 题目描述HH有一串由各种漂亮的贝壳组成的项链。 HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一 段贝壳，思考它们所表达的含义。 HH不断地收集新的贝壳，因此他的项链变得越…
2022/8/13 6:23:40 人评论 次浏览 -
1008 数据结构 线段树 区间加法 区间乘法 区间平方和 区间和
链接：https://ac.nowcoder.com/acm/contest/26896/1008来源：牛客网 题目描述qn姐姐最好了~ qn姐姐给你了一个长度为n的序列还有m次操作让你玩， 1 l r 询问区间[l,r]内的元素和 2 l r 询问区间[l,r]内的元素的平方 和3 l r x 将区间[l,r]内的每一个元素都乘上x 4 l r x …
2022/8/8 23:25:43 人评论 次浏览 -
二分算法
二分的本质不是单调性。 （有单调性一定可以二分，但是二分可以做的题，不一定需要满足单调性。） 二分的本质是二段性 就是有一个分界点，分界点左边都是状态x，分界点右边都是状态y。通过二分就可以找到红色区域的右边界值或者绿色区域的左边界值 当想找不满足性质的边界…
2022/8/7 1:22:56 人评论 次浏览 -
题解 CF1684F Diverse Segments
vp 的时候写了一个比较愚蠢的做法过了。 首先选择一个区间修改等价于删掉这个区间。那么考虑它给定的 \(m\) 个区间会有什么影响。假设给定的某个区间是 \([l,r]\)，那么假设颜色 \(col\) 在这个区间出现 \(k\) 次，下标是 \(c_1,c_2,...,c_k\)。那么：\(0\le k\le 1\)：没…
2022/8/4 6:25:37 人评论 次浏览 -
莫队算法学习记录
什么是莫队：莫队是一种用于处理询问区间值的暴力离线算法，思路是通过移动两个指针到对应的区间来计算结果，精华是合理分块并依次处理。 什么时候用莫队：离线，暴力，1e5 原版莫队：建立区间（x1/2）:ll size=sqrt(n),bnum=ceil((double)n/size);for(ll i = 1; i <=…
2022/7/27 1:24:57 人评论 次浏览
