Description: 给一个长度为n的序列a。1≤a[i]≤n。 m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。 Input: 第一行两个数n,m。…
标签:主席树
BZOJ 3932 [CQOI2015] 任务查询系统
Description: 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的 任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和E…
SPOJ 10628 Count on a tree
Description: 你得到一个带有N个节点的树。树节点从1编号到N,每个节点都有一个整数权重。 我们将要求您执行以下操作: u v k:询问从节点u到节点v的路径上的第k个最小权重 Input: 在第一行中有两个整数N和M.(N,M …
POJ 2104 K-th Number
Description: 您在数据结构部门为微硬公司工作。 您在关于键插入的上一个任务失败后,被要求写一个新的数据结构,以便能够在数组段中快速返回第k的数据。 也就是说,给定一个不同整数的数组a [1 ... n],你的程序必须回答一系列问…