搜索
题目链接https://wwwlydsycom/JudgeOnline/problemphp?id5379题解显然,换根操作只需要记录,树实际上的根始终都是。对于修改操作,a,brolepresent
2022-12-02
题目链接https://wwwlydsycom/JudgeOnline/problemphp?id2212思路显然,一棵子树内的交换情况,并不会影响这个子树与其他子树之间的逆序对个数。对每个点建一棵权
2022-12-02
题目链接https://wwwlydsycom/JudgeOnline/problemphp?id4695思路恶心题……思路请见2016年国家候选队论文《区间最值操作与历史最值问题——吉如一》代码in
2022-11-21
题目链接https://wwwlydsycom/JudgeOnline/problemphp?id3932题解将每个进程拆成两个操作:开始进程和结束进程,离散化优先级,然后按时间排序。建一棵主席树,区
2022-11-07
P4556[Vani有约会]雨天的尾巴题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房
2022-09-19
一个知识点不在一道题里说是没有灵魂的线段树是用来处理区间信息的咯但是往往因为需要4倍空间让许多人退却,而动态开点的线段树就非常棒仿佛只用2倍就可以咯指针保存位置,即节点信息,是很舒适的,所以用指针动态
2022-09-19
目录一、问题引入二、线段树的构建三、线段树的单点修改与查询1、修改2、查询四、线段树的区间修改与查询1、修改2、查询一、问题引入对于一般的区间问题,比如RMQ(区间的最值)、区间的和,如果使用朴素算法
2022-09-15
LegendLink\(\textrm{toCodeforces}\)。给定\(n\)个点,\(m\)条边的无向图,每个点有点权,互不相同。需要支持两种操作共\(q\)次:询问从\(x\)点出发能到达
2022-09-14
LegendLinktoLOJ。请维护一个高精二进制数\(s\),支持操作\(n\(0\len\le10^6)\)次:加或减\(a\times2^{b}\)。\((|a|\le10^9,0\leb\l
2022-09-14
LegendLinktoLOJ。维护两个二元组集合\(A,B\),支持操作\(Q\(1\leQ\le2\times10^6)\)次:向其中某个集合插入一个二元组\((t,e)\(1\let\le2\t
2022-09-14
LegendLink\(\textrm{toLOJ}\)。一个可重复数字集合\(S\)的神秘数定义为最小的不能被\(S\)的子集的和表示的正整数。给定长\(n\)的正整数序列\(a_i\),\(q\)
2022-09-14
LegendLink\(\textrm{toLuogu}\)。小Z有一片森林,含有\(N\(1\leN\le8\times10^4)\)个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有
2022-09-14
LegendLink\(\textrm{toCodeforces}\)给定长度为\(n\(4\len\le200\000)\)的数字串,\(q\(1\leq\le200\000)\)次询问,每次询问一
2022-09-14
还是老规矩,传送门hdu1828依然不做过多解释,给出n个矩形,求这些矩形组合而成的图形的周长(中间镂空的部分也算)还是像扫面线(一)一样,自下而上扫描,我们先只考虑横线,发现只要每次加上被覆盖的区间
2022-09-07
还是老规矩,传送门hdu1542不做过多解释了,就是给出n个矩形,求出这些矩形所覆盖的面积和。由于n很小,因而这道题不是必须用线段树先想想怎么办,先来一个例图(稍微有点复杂)根据数学知识,我们可以像这
2022-09-07
求动态区间最大子段和,并支持单点修改。\(n\leq5\times10^5,m\leq10^5\)。用线段树处理。对于每一个节点维护以下变量:\(ans\)表示区间内最大子段和,\(sum\)表示区间
2022-08-31
给定数列,维护区间平均数和区间方差,并支持区间修改。\(n\leq10^5,m\leq10^5\)。线段树维护平均数比较简单,重点在于如何维护方差。具体公式参考了这篇题解,就不详细展开,推出来以后就变
2022-08-30
题目链接:https://codeforcescom/contest/718/problem/C题意:给出一个序列,有两种操作,操作一:将序列中lr部分的值加上某个数,操作二:计算Σrilf(i)的值
2022-08-16
'Q'ab查询(a,b)区间的最大值'C'ab讲a处值改为b与query不同的是if(x<mid)maxmmax(maxm,query(i<<1,l,mid,x,y));if(y&g
2022-08-16
毕竟是写给自己看的还是写好看一点吧一、最简单的传送门HDOJ1754题意~给出N个数,两种操作:1、Uxy:修改第x个数的值为y;2、Qxy:求第x到第y个的最大值,注:x未必比y小标准的线段树对不对
2022-08-16