ohEPse

D1T1 与或Description：对于一个长度为 $n$ 的序列，维护一下三个信息： 1 l r v ：将 $a_i,l\leq i \leq r$ 变为 $a_i \text{ and } v$ 2 l r v ：将 $a_i,l\leq i \leq r$ 变为 $a_i \text{ or } v$ 3 l r ：求 $a_i,l\leq i \leq r$ 的最大值 Solution:不会（逃 正解参考idx巨佬的文章 Code:这里使用的是暴力解法，可以过掉随机数据 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101#include<bits/stdc++.h>using namespace std;#define ll in ...

D3T3 ThreeDesciption:给定一颗 $n$ 个节点的无根树，在树上选三个互不相同的节点，使得三个节点两两之间距离相等，输出方案数。 Solution：首先，我不是很会 $dp$ 其次，我完全不会长链剖分优化 $dp$ 最后，我 其实 $dp$ 部分还是听懂了。 设 $f_{i,j}$ 表示以 $i$ 为根的子树中距离 $i$ 为 $j$ 的点数，$g_{i,j}$ 表示 $i$ 的子树中有多少两个点的 $lca$ 到 $i$ 的距离为 $d-j$ ，两个点到他们 $lca$ 的距离是 $d$ 。 很容易发现这两个状态可以互补（？ 因此对于一对父子 $(p,v)$ 有如下转移式： ans+=g_{v,i+1}*f_{p,i}+g_{p,i}*f_{v,i-1} g_{p,i}+=g_{v,i-1}+f_{v,i-1}*f_{p,i} f_{p,i}+=f_{v,i-1}但是代码就完全就看不懂了，什么指针转移力（哭 Code：1234567891011121314151617181920212223242526272829303132333435363738 ...

我是劳模 题目：题目描述在SSZX食堂，所有的座位是一行一行的排列。现在有 $N$ 个座位排成一行，依次编号 $1,2,\dots,N$ ，每个座位只能坐一个人，现在L想数一下有多少个人坐着，一个一个数太慢了，L决定只选择 $M$ 段连续的座位，对每段分别数出人数。由于食堂噪音十分嘈杂，L无法专心，可能有数错了。但是L认为没有数漏，最多是重复计数导致的。现在他把得到的数据给你，希望你帮他算出，一共最多有多少人。 输入格式第一行2个整数 $N,M$，分别是座位数量，和L分成 $M$ 段 接下来M行，每行3个整数，$l,r,k$，表示L数了 $l$ 到 $r$ 这一段的座位，他输出的数是 $k$。 输出格式输出一行一个整数表示答案 我们学校食堂没有这么大 数据规模20%数据, $N,M$ <=20 40%数据，$N,M$<=500 20%数据，L选的每段座位 不相交 100%数据，$1 \leq N,M,K \leq 100 000$ , $1 \leq l \leq r \leq N $ solution：（差分约束） 说白了就是有一个长度为 $n$ 的 01 串，每次告诉区 ...

0. 写在前面懒癌晚期患者，本来说毕业暑假找个时间写写，结果拖到现在 在外面漂泊了大半年，仍然还是很想xcsy 怎么说呢，已经算是一种精神寄托了属于是 1.大事祭1.1 初一之前1.1.1 2019.6以前的事最早关于xcsy还是在2018.9的样子。听说ljz被挖到xczx去了，后面才知道是xcsy，1w的奖学金，还有晚自习练魔方的权利，爽死了。心想我也身为一个cuber会不会也有这种待遇。后面才发现ljz是我永远无法企及的高度。 2019.1以及2019.6 ljz拿世界冠军、去上节目确实让xcsy好好吹了一把，感觉还能再宣传5年。 好了该是我自己的事了。 好怀念我们当时还没有全摇号的日子。 大概2019.1（记不太清了 tyc首先拿到了xcsy的offer，好像是小考进的，xhx整个六年级下大概都在外面补课，那个机构也有进xcsy的手段。我大概是2019.5小面试的时候拿到了减分的政策，7月的大面试不失常就肯定能进了。 当时还是很开心的立马停掉了奥数课然后2019.6还去打了桂林赛，属于保送了。 记得小考还拿到了tfqz的offer，区上摇号还有qzcz。因为那年xcsy风头太盛 ...

感觉这个也算是个知识点但是到处都没有教程捏 这里有一篇写的很好的关于dfs序的教程。 dfs序就是把树上问题转化为序列问题，从而通过树状数组或线段树进行维护。 dfs序本身不难理解，难的是与树状数组以及线段树结合，再加上巨大的码量。一下的四个例题码量平均100+。 多码预警 下面用一些例题讲解。 1.单点修改，子树查询在dfs序中，$x$ 的子树在两次 $x$ 出现的中间，且是连续的。 所以问题就转化为序列上单点修改，区间查询。树状数组维护即可。 code： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<bits/stdc++.h>using namespace std;#define in read()#define ll long longinline ll read(){ ll x=0,f=1;c ...

D2T1 [NOI2016]区间Desciption:有 $n$ 个闭区间 $[l_i,r_i]$ ，从中选出 $m$ 个区间，使得存在 $x$ ,使得每个被选择的区间都有 $l_i \leq x \leq r_i$。 选择一个合法的方案，它的花费为最长的区间长度减去最短区间长度，定义区间长度为 $r_i-l_i$。 求最小的花费，如果没有合法方案则输出 $-1$ 。 Solution:考虑先将区间按照花费从小到大排序，然后用尺取法加线段树维护即可。 Code：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include<bits/stdc++.h>using namespace std;const int maxn=5e5+10;#define in ...

传送门 Description:有一个长度为 $n$ 的序列，从中选出 $k$ 个长度为 $l \leq k \leq r$ 的不同的区间，使得区间和最大。 Solution：前缀和+堆+RMQ 首先前缀和优化区间和。 以区间最大值为关键字建立大根堆 ，枚举左端点，查找 $[l,r]$ 区间加入堆中。然后循环 $k$ 次，每次取出堆顶，累加贡献，间 $[l,pos-1]$ 和 $[pos+1,r]$ 加入堆， $pos$ 代表 $[l,r]$ 区间中最大值的位置。 Code:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=5e5+10;int n,k,l,r,logn[maxn],f[maxn][24];ll a[maxn];vo ...

题目传送门](https://www.luogu.com.cn/problem/P2680) ) 一道感觉不算很难的紫题 翻译一下 给定一棵有边权的树，和 $m$ 组点对，需要选择并清零一条边，使得 $m$ 条边之间的最长路最短。 solution最小化最大值，一眼二分。 然后考虑 $check$ 函数怎么写。很容易想到一个很暴力的解法：暴力枚举清零每一条边。一算时间复杂度肯定接受不了。 考虑优化。观察到枚举过程可以进行优化。先预处理出每条路径的长度， $check$ 时统计大于 $mid$ 的边有 $k$ 条，找出被经过 $k$ 次的边且边权最大的一条，判断最长路径 $maxlen$ 减去最长边 $maxd$ 是否小于 $mid$. 综上所述，先用树上差分+$LCA$ 预处理出每条路径的长度，二分答案，树上差分进行 $check$。 code细节都批注在代码里了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 ...

description传送门 丽洁还是很吊的 这道题我还尚未完全摸透做法，所以仅作为一道好题放在这里 代码难度不大，但是思维含量极高 但我是绝对不会说我的 $queryrmax$ 和 $querylaxm$ 函数因为是复制粘贴的所以 debug 了一个小时（逃 说不定几万年后我 AKIOI 之后再回来看就明白了呢 solution首先对于每一个询问可以进行二分答案。 然后考虑求中位数。一个小套路：==将所有大于等于 $mid$ 的设为 1，小于的设为 -1，当区间和为 0 的时候就 $mid$ 就是中位数==。为了选择更大的中位数，所以要尽可能多选择 1。（why？）那么就要维护一个最长子序列。 对于每一个询问都要开一个线段树，那么肯定选择主席树啦（why？）。每个节点维护一个区间和，区间最大前缀和区间最大后缀。 code： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...

D1T4 HotelDescription：对于一个01序列，维护两个值： 1 x 找出长度为 $x$ 的区间变为 1，并输出最左的一个左端点。 2 l r 将 $[l,r]$ 变成 0。 Solution：对于操作 1，用线段树维护最长子段和，在 query 函数里的查询操作改为 1234567int query(int l,int r,int p,int length){ pushdown(p); int mid=t[p].l+t[p].r>>1; if(t[p<<1].sum>=length) return query(l,r,p<<1,length); if(t[p<<1].rmax+t[p<<1|1].lmax>=length) return mid-t[p<<1].rmax+1; return query(l,r,p<<1|1,length);} 对于操作 2，区间赋值操作即可 Code：123456789101112131415161718192021222 ...