ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共9篇）

[HEOI2016/TJOI2016]树

[HEOI2016/TJOI2016]树思路做的时候也是糊里糊涂的就是求最大值的线段树错误线段树写错了 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespa...

树链剖分线段树

2018-12-26

0 367

[SDOI2014]旅行

P3313 [SDOI2014]旅行思路有点恶心咯每个信仰开一颗线段树记录修改或者查询的时候去那一颗信仰线段树中查询就好必须动态开点线段树没有区间修改还算好写错误查询跳链写错了 #include <bits/stdc++.h> #define FOR(i,a,b...

线段树树链剖分

2018-12-26

0 430

luogu P2486 [SDOI2011]染色

树剖做法：就是两个dfs+一个线段树难度的取决基本==线段树的维护难度所以对有点线段树基础的，树剖也不难做吧这里操作有二一：两点间路径染***r> 线段树的区间赋值操作二：查询路径段的个数考虑线段树如何做我们发现两端区间的合并取决于他们相连接的那两个颜***r> 比如这张...

线段树树链剖分

2018-12-25

0 442

SP6779 GSS7

GSS7解题报告前言唔，有点恶心哪，废了两个多小时debug 思路很容易看出傻子都知道，这个是树链剖分+线段树的裸题，只不过是恶心了点，这里重点讲一下细节问题线段树做过GSS系列的都应该很熟悉了线段树维护的前缀最大子段和，后缀最大子段和，和区间最大子段和那么我们就可以很容易...

树链剖分线段树

2018-12-26

0 367

P3178 [HAOI2015]树上操作

P3178 [HAOI2015]树上操作思路板子嘛，其实我感觉树剖没啥脑子就是debug 代码 #include <bits/stdc++.h> #define int long long #define ll long long #define ls rt<<...

线段树树链剖分

2018-12-26

0 466

P3128 [USACO15DEC]最大流Max Flow

思路这个题哪里有那么费脑筋我们可以树链剖分嘛LCT昨天学的时候睡着了，不是太会两遍dfs+一个5行的BIT 其实树链剖分学好了对倍增和LCT理解上都有好处一条路径上的修改由于一条剖出来的链是连续的，我们要选择数据结构维护不过这里不用维护太多东西，只是区间+1 我们可以选择常数小，好写的...

树状数组树链剖分

2018-12-26

0 508

P3979 遥远的国度

P3979 遥远的国度思路一开始我用这个函数得到左端点 int get_l(int x,int y) { if(top[x]==top[y]) return son[x]; int last=top[x]; while(top[x]!=top[y]) { ...

线段树树链剖分

2018-12-26

0 445

[SDOI2016]游戏树剖+李超树

目录链接思路 update 代码链接 https://www.luogu.org/problemnew/show/P4069 思路树剖+超哥线段树我已经自毙了，自闭了！！！！ update 上次抄了没认真看，这次考...

线段树树链剖分超哥线段树

2019-02-09

0 638

#2718. 「NOI2018」归程 kruskal重构树

链接 https://loj.ac/problem/2718 思路我们希望x所在的连通块尽量的大，而且尽量走高处离线的话可以询问排序，kruskal过程中更新答案在线就要用kruskal重构树这kruskal重构树的话，看图就明白了叶子节点都是原树节点非叶子节点都是边按照从大到小...

kruskal重构树并查集树链剖分二分

2019-03-02

0 550