搜索结果
查询Tags标签： rson，共有 14条记录-
【考试总结】2022-05-01
a 观察能构成合法区间的条件就是奇数成对，同时每对奇数之间没有 \(0\) 使用一类线段树维护历史信息的手段来解决本题，为了规避麻烦的标记下放，可以将每个 “偶数个奇数” 的出现区间左右端点刻画出来并使用 \(r-l+1\) 来计算 同时在每个节点要支持 \(01\) 翻转的部分维…
2022/5/2 23:17:41 人评论 次浏览 -
CF380C Sereja and Brackets
洛谷题面 线段树模板题。 题目分析 给定一个括号串和 \(m\) 次操作，每次操作求区间 \([l,r]\) 内最长合法括号子序列的长度。 题目分析 我们可以在普通线段树上再记录两个变量 \(lnum,rnum\)，分别表示区间内未匹配的左括号的数量和未匹配的右括号的数量。 于是有： inli…
2022/4/3 23:19:29 人评论 次浏览 -
LeetCode 236二叉树的最近公共祖先
菜鸡学习记录 题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com) 这道题目是使用回溯的方法做的，感觉二叉树一般就是用回溯的方法去做。 找公共祖先，对于某一个节点来说，用lson和rson分别表示其左子树和右子树。 思路是先判断其左子树、右子树…
2022/1/11 23:07:14 人评论 次浏览 -
LeetCode 236二叉树的最近公共祖先
菜鸡学习记录 题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com) 这道题目是使用回溯的方法做的，感觉二叉树一般就是用回溯的方法去做。 找公共祖先，对于某一个节点来说，用lson和rson分别表示其左子树和右子树。 思路是先判断其左子树、右子树…
2022/1/11 23:07:14 人评论 次浏览 -
cf1010 D. Mars rover（树）
题意： 有一棵逻辑运算树，叶子节点为输入节点(IN)，取值0/1；其他节点有AND/OR/XOR/NOT四种类型，并根据儿子节点取不同的值。输出为根节点的值。 初始每个输入节点的值给定（因此所有节点的值确定）。问单独改变每个输入节点的值而保持其他输入节点不变，输出是多少思路…
2022/1/3 6:08:45 人评论 次浏览 -
cf1010 D. Mars rover（树）
题意： 有一棵逻辑运算树，叶子节点为输入节点(IN)，取值0/1；其他节点有AND/OR/XOR/NOT四种类型，并根据儿子节点取不同的值。输出为根节点的值。 初始每个输入节点的值给定（因此所有节点的值确定）。问单独改变每个输入节点的值而保持其他输入节点不变，输出是多少思路…
2022/1/3 6:08:45 人评论 次浏览 -
CF666E Forensic Examination（后缀自动机，可持久化线段树合并）
给你一个串\(S\)，以及一个字符串数组\(T_{1,2,...m}\)，\(q\)次询问，每次问\(S\)的子串\(S[p_l,...p_r]\)在\(T_{l...r}\)中的哪个串的出现次数最多，并输出出现次数。 做法： 对串\(S\)和数组\(T\)建立后缀自动机。 在后缀自动机上找到\(S[l,r]\)这个子串对应的节点u，…
2021/11/4 23:09:59 人评论 次浏览 -
CF666E Forensic Examination（后缀自动机，可持久化线段树合并）
给你一个串\(S\)，以及一个字符串数组\(T_{1,2,...m}\)，\(q\)次询问，每次问\(S\)的子串\(S[p_l,...p_r]\)在\(T_{l...r}\)中的哪个串的出现次数最多，并输出出现次数。 做法： 对串\(S\)和数组\(T\)建立后缀自动机。 在后缀自动机上找到\(S[l,r]\)这个子串对应的节点u，…
2021/11/4 23:09:59 人评论 次浏览 -
初学 笛卡尔树
表示之前没见过这种东西。 概念 Link构造 知乎 以下均假设原序列元素两两不相同。 从左至右依次加入元素，维护当前笛卡尔树的右耳子链 \[root\to rson\to rson.rson\to rson.rson.rson\dots \]至一个栈内。 设加入的节点为 \(x\)，\(t\) 为当前笛卡尔树。找到栈中最靠顶部…
2021/10/16 23:13:22 人评论 次浏览 -
初学 笛卡尔树
表示之前没见过这种东西。 概念 Link构造 知乎 以下均假设原序列元素两两不相同。 从左至右依次加入元素，维护当前笛卡尔树的右耳子链 \[root\to rson\to rson.rson\to rson.rson.rson\dots \]至一个栈内。 设加入的节点为 \(x\)，\(t\) 为当前笛卡尔树。找到栈中最靠顶部…
2021/10/16 23:13:22 人评论 次浏览 -
线段树代码模板 → 点更新、区间查询
【算法代码】 #include<bits/stdc++.h> using namespace std;const int maxn=100005; const int inf=0x3f3f3f3f; int a[maxn];struct node {int le,ri,mx; //mx represents the maximum value of interval [le,ri] } tree[maxn*4]; //Segment tree needs 4 times t…
2021/10/3 6:14:43 人评论 次浏览 -
线段树代码模板 → 点更新、区间查询
【算法代码】 #include<bits/stdc++.h> using namespace std;const int maxn=100005; const int inf=0x3f3f3f3f; int a[maxn];struct node {int le,ri,mx; //mx represents the maximum value of interval [le,ri] } tree[maxn*4]; //Segment tree needs 4 times t…
2021/10/3 6:14:43 人评论 次浏览 -
P3332 - K大数查询 题解
好像是经典题（？），那就写一波题解罢。 BIT 套动态开点线段树 考虑查询，集合里的元素每个有两个指标：所在集合编号和自身权值，那么查询容易想到二分，二分的 chk 其实就是个二维数点。是动态的（实际上这个修改比动态加点强），二分的 chk 这玩意可以看作半在线，就暂…
2021/8/27 23:36:19 人评论 次浏览 -
P3332 - K大数查询 题解
好像是经典题（？），那就写一波题解罢。 BIT 套动态开点线段树 考虑查询，集合里的元素每个有两个指标：所在集合编号和自身权值，那么查询容易想到二分，二分的 chk 其实就是个二维数点。是动态的（实际上这个修改比动态加点强），二分的 chk 这玩意可以看作半在线，就暂…
2021/8/27 23:36:19 人评论 次浏览
