题目链接： 点击打开链接 Description You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j

题意；给定一个升序的数列（1-100000）， 比如 array[10] =  -1  -1  1  1  1  1  3  10  10  10， 求其中某段区间上相同的数字最多有几个。[ 2, 3 ] = 1, [ 1, 10 ] = 4, [ 5, 10 ] = 3。（下标从1开始）。 题解：先将连续相等的几个数合并为一个部分（part), 或者说一个点。每点包括了起始位置，终止位置，相等

第一步就死离散化，现在才开始接触。。乃琦神牛要我一定要做几题，我也就试试罗。 对于相同的数，记录起点和终点，记录出现的次数，缩成一个点。就可以建线段树。 还要注意如果给出的点不是起点，那么这个点连续的一段相同的要先算出来。。 而且这道题没有动态变化。个人觉得RMQ一样可以过。。。。下次有空试一下。 不过正在学线段树，就做一下线段树的吧。 #include<iostream> #inclu

e of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequen

线段树做法：详见 树状数组： 上面那个网址也说了，使用差分数组b[i]=a[i]-a[i-1]使b[1……i]=a[i],再用树状数组求出来。 代码 #include <cstdio>#include <cctype>#define ll long longusing namespace std;ll n,a[500001],m;ll lowbit(ll x){return

题意 如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数数加上x 2.求出某一个数的值 思路 用树状数组记录这个数列的差分数组，例如a[]={3,2,7,6,8}这个数列的差分数组为{3,-1,5,-1,2},我们可以从这个差分数组看出，第i个数的值就是差分数组的前i个的和。当我们进行修改，例如给2-4加上3，那么差分数组就会变成{3,2,5,-1,0},可以发现只是第2个和

http://poj.org/problem?id=3368 题意： #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <vector>#include <queue>#include <map>#include <algorithm>#in

Frequent values POJ - 3368 题目链接 题意：一个非递减序列，随机询问区间[l, r]中出现次数最多的数的出现次数； 思路：多次询问，首先就要想一下线段树；由题意可知数列中的数是连续的，既然是连续的就有合并的希望！！！那么就来一发线段树吧(RMQ也可以做，但是不会啊！！！还是蒟蒻)； 首先，要用线段树维护哪些值？ 题目要求区间内出现次数最多的数的出现次数，那

题目链接：http://poj.org/problem?id=3368 题目大意：不减数列，求出区间内频率最大数的频率。 思路：把相同的数合并，保留频率，放到线段树里面，求max； 对于给出的区间，先把两头去掉，再对中间部分用线段树查询max。 (有点边界还是略复杂的，比如给出的区间属于同一个区间，或者相邻区间) #include <stdio.h> #include <vector

一、题目大意 给定我们一个长度为n(n<=100000)的有序数组，进行q(q<=100000)次[L , R]的区间查询，对于每次查询返回 [L , R]区间内的出现次数最多的数字的出现次数。(1<=L<=R<=n) 二、解题思路 1、线段树 我们对于每个区间记录一个三元组 1、lVal代表这个区间内最左边的元素出现的次数 2、rVal代表这个区间内最右边的元素出现的次数 3、ma