ComplexPug

未归档

做题记录(1)

/ 注册

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

luogu1975 [国家集训队]排队

思路序列中 |i | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| |----|--|--|--|--|--|--|--|--|--|--| |a[i]| a| b| c| L| d| e| f| R| g| h| 现逆序对为ans,要交换L,R 则\([1,3],[9,10]\...

树套树

2018-12-14

0 387

luogu P2713 罗马游戏

思路模拟就好左偏树合并并查集寻找代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int maxn=1000005; int ...

左偏树并查集

2018-12-13

0 472

luogu P3521 [POI2011]ROT-Tree Rotations

思路合并时候统计逆序对贡献代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define ll long long using namespace std; const int ma...

线段树线段树合并

2018-12-13

0 544

luogu P3168 [CQOI2015]任务查询系统

思路又是强制在线--主席树每一次操作建一棵树但实际用的的rt只有n个所以实际内存是n230 我见到只开n*30的,不会，错误 debug 以为每一秒建立一颗树第一次 query没有递归第二、三次权值线段树的查询处理,就是到叶子节点的处理代码 // luogu-judger...

数据结构-主席树

2018-12-12

0 467

luogu P2633 Count on a tree

思路强制在线--主席树以1为root建主席树 (就是在树上建树，差不多) rt[i]就是1到i的路径上的一棵树的root 其实我感觉，主席树之间的运算差不多于加减类似lca的运算 root(1到x)+root(1到y)-root(lca）-root(fa[lca]) 查询他们的第k小就OK ...

数据结构-主席树 lca

2018-12-12

0 462

P3567 [POI2014]KUR-Couriers

思路区间内x出现次数大于一半区间内排序，则x一定会在(一半+1)的位置上出现找到那个数，再检查一下就好错误快读写错了、、，又浪费了1h 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b...

数据结构-主席树

2018-12-12

0 529

luogu P2617 Dynamic Rankings

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

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

2018-12-11

0 502

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

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

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

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

2018-12-10

0 464

luogu P3605 [USACO17JAN]Promotion Counting晋升者计数

题目链接 luogu 思路可以说是线段树合并的练手题目吧也没啥说的，就是dfs，然后合并、、、看代码吧错误和写主席树错的差不多都是变量写错、、、、代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=...

线段树线段树合并

2018-12-10

0 390