有时候真羡慕在国外读书的高中生

1.前言: 以前初学者都会认为树链剖分是个很难的算法,其实很简单.大致思想就是把树分成链,然后用线段树进行一定操作即可.只是代码稍微有点长.  2.算法流程: 1.首先对于这颗树的每个点找到它的重儿子,树链剖分需要重构一下这颗树让重儿子的节点优先跑出,这里只需要一个dfs即可.2.重构完树了之后呢?就只要把这颗树按节点序号投影到线段树即可.然后用线段树的操作来对于树进行操作.3.对于模板题 一个很显然的结论,在树重构了之后,我对于子树u进行操作就是对于线段树区间(u,u+siz[u]-1)进行操作.然后对于树上路径是唯一的,我们可以采用倍增的思想对于u->v这条路径进行操作,这里我们需要...

今天做了一个可怕的噩梦，梦见我一直在抄实验报告，醒来的时候手都软了

A. Favorite Sequence 观察发现前一半大概是2i-1分布,后一半是n-2i分布.然后代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+50; int a[N],b[N]; int main() { int T; cin>>T; while(T--) { int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=(n+1)/2...

1.前言 这里专门写一篇动态开点,因为上次学习点分树的时候很难受,这里专门写一篇动态开点,来记录一下...所谓的动态开点,就是指你的线段树没必要建成满二叉树的形式,因为有些节点的访问根本用不到,类似lazy吧,但是lazy是时间上的节省,体现在后面查询时,而动态开点是在前面建树,对于空间的节省.  2.引例 CF915E Physical Education Lessons这个题很容易想到就是线段树的区间修改和区间查询,但是它的一个难点就是n<=1e9.这可咋办?但是我们可以注意到q<=3e5.也就是说它访问的区间还是不超过6e5个点.如此我们是不是可以在更新的时候建树,顺带查询答...

之前看日在校园的时候没看结局，以为就是一部简单的啥番...今天我又特意重新看了一下，真的震惊到我了...好喜欢桂言叶啊！

熬夜冠军，明天上海站+考试，可不能熬夜了，今天大概是我这周最后一次熬夜了，这周也就一天了2333

我到底多久才能睡呢...

将写一篇比较长的博客来系统的学习下线段树:群友Limit的线段树题单以及线段树分治的某些题单update:群友Limit的线段树题单two P3372 【模板】线段树 1  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; ll Tree[N<<4],w[N],lazy[N<<4]; //分别表示该节点的下的权值和是多少, void pushdown(int u,int l,int r) { int mid=(l+r)>>1...

待学习(树链剖分...\先学线段树和dfs序,好菜,呜呜呜)贴下不完整的代码: #include <bits/stdc++.h> using namespace std; const int N=3e5+50,M=20; const int base=131; typedef unsigned long long ull; ull w[N]; ull h[N],b[N];//h[i]假设根节点是1,统计1到i的hash值 b[i]表示(131^i) int fa[N][M]; int dep[N]; vector<int>v[N]; void dfs(int u,int...

1.算法:  二分+贪心2.思路: 首先我们二分出一个值x,对于这个值就行check...怎么check呢? 一个很显然的东西,假如我的开始值是x,且我x-a[i]*m>=h[i]这种值是不可能用到的. 其次我们假设我们的初始值是x,且都要用到,那么我肯定是选变成负数步数最少的优先,因为我想让我每次减少的p尽可能的多. 然后就可以直接用优先队列模拟维护了.3.代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+50; ll a[N],h[N]; ll n,...

 今天加到sun的微信了～

为什么让我知道atcoder这个比赛.很多题目我想不到,但是又没什么人写题解.主要是我菜,但是一次次的,都卡c/d我人也会崩溃的啊,还有那么多的作业,手抄48个代码,8个实验报告...不知道老师怎么想的,真的快崩溃了啊,还有算***的少,马上就上海站了,还有期末考试...啊,越想越烦,每次比赛,和补题的时候,想着这是别人几分钟就写完的东西...那种失落和反差,真的烦..

昨天给自己立的flag，今天就要倒了，感觉人生没意思...但是看很多人，他们似乎也和我一样唉