ComplexPug

分类

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

/ 注册

全部文章（共6篇）

区间内x的出现个数(主席树)

题目大概：求区间内x出现的次数出题人yjy Description ZJK 给你一个长度为 n 的数列和 m 次询问，每次询问从第 l 个到第 r 个数中，数 x 出现了多少次。Input第一行一个整数 n，第二行 n 个整数，表示这个数列。第三行一个整数 m，表示询问数。下面 m 行，每行...

数据结构-主席树

2018-07-08

1 711

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

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

luogu P3168 [CQOI2015]任务查询系统

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

数据结构-主席树

2018-12-12

0 467

CF1062E Company

CF1062E Company 链接 cf luogu 题目大意给定一颗树，有若干个询问，每个询问给出 l，r，要求编号为 ll~rr 的点任意删去一个之后剩余点的 LCA 深度最大，输出删去点的编号和 LCA 的最大深度思路一堆点的lca就是dfs序列的最大和最小的lca 因为只...

lca 数据结构-主席树线段树

2019-04-28

0 521