ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共45篇）

P4556 [Vani有约会]雨天的尾巴

目录思路优化过程中的问题/疑问错误代码思路每个节点维护一课线段树(当然是动态开点) 线段树的作用是统计这个节点有多少种粮食型号，以及最多的粮食型号然后树上差分，u和v点 +1，lca(u,v)和f[lca(u...

线段树线段树合并数据结构 ST表 lca 差分

2018-12-10

0 464

P3380 【模板】二逼平衡树（树套树）

思路若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l...

线段树 fhqtreap 树套树

2018-12-11

0 579

luogu P2617 Dynamic Rankings

前置知识: 普通主席树，树状数组大概待修主席树和静态的一样只不过还要加一颗树来维护你修改的值这棵树就是是树状数组,每个节点上再维护一颗动态开点线段树 (就是所说的树套树，不过没啥可怕的，就是麻烦一丢丢) 查询的时候老样子不过要多加上树状数组中的值罢了代码还算好些，如果主席树，...

线段树离散化数据结构-主席树树套树可持久化

2018-12-11

0 502

[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 P5105 不强制在线的动态快速排序

前言考试的时候居然想错了区间贡献，mdzz 思路题目看着很方啊，难道要树套树？但数据范围提醒我们，是nlogn的复杂度 Sort(S)的定义是不是很鬼畜但我们不动脑子的打表容易发现连续区间[1，n]内\(a_i^2-a_{i-1}^2\)为连续的奇数（其实这里直接用初中的完全平方公...

线段树离散化

2018-12-17

0 619

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

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