关键词：
vjudge 上题目链接：UVA 11235
*******************************************************大白书上解释************************************************************
题目大意：给出一个非降序排列的整数数组 a1,a2,a3,...,an，你的任务是对于一系列询问 (i, j)，回答 ai,ai+1,...,aj 中出现次数最多的值所出现的次数。
输入格式：包含多组数据。每组数据第一行为两个整数 n 和 q（1 <= n, q <= 100000）。第二行包含 n 个非降序排列的整数 a1,a2,a3,...,an（-100000 <= ai <= 100000）。以下 q 行每行包含两个整数 i 和 j（1 <= i <= j <= n），输入结束标志为 n = 0。
输出格式：对于每个查询，输出查询结果。
分析：应注意到整个数组是非降序的，所有相等元素都会聚集到一起。这样就可以把整个数组进行游程编码（Run Length Encoding, RLE）。比如 -1,1,1,2,2,2,4 就可以编码成 (-1, 1), (1, 2), (2, 3), (4, 1)，其中 (a, b) 表示有 b 个连续的 a。用 value[i] 和 count[i] 分别表示第 i 段的数值和出现次数，num[p], left[p], right[p] 分别表示位置 p 所在段的编号和左右端点位置，则在下图的情况，每次查询（L，R）的结果为以下 3 个部分的最大值：从 L 到 L 所在段的结束处的元素个数（即 right[L] - L + 1）、从 R 所在段的开始处到 R 处的元素个数（即 R - left[R] + 1）、中间第 num[L] + 1 段到第 num[R] - 1 段的 count 的最大值，如图 3-8 所示。
*******************************************************大白书上解释结束************************************************************
我的理解：
预处理过程主要就 3 个数组：seq[] 就是上述提到的 count[] 数组，记录 seq[i] 第 i 段连续整数的出现次数；pos[i] 表示原数组的第 i 个元素在 seq[] 中处于第几段；preSum[] 则是 seq 数组的前缀和，用于快速求出第 L 段和第 R 段的元素个数。这 3 个数组准备好后，接下来就是求区间最值的问题而已，线段树或者 RMQ 都可以，二者复杂度一样，时间差异可以忽略不计，只不过我更熟悉线段树，感觉 RMQ 的边界有点不容易处理而已。
首先是线段树的代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> using namespace std; #define For(i,s,t) for(int i = (s); i < (t); ++i) #define root int rt, int l, int r #define ll(rt) ((rt) << 1) #define rr(rt) (ll(rt) | 1) #define makemid int mid = (l + r >> 1) #define lson ll(rt), l, mid #define rson rr(rt), mid + 1, r const int N = 100005; int c[N]; vector<int> seq, preSum; int pos[N] = {0,}; int Max[N << 2]; inline void pushup(int rt) { Max[rt] = max(Max[ll(rt)], Max[rr(rt)]); } void build(root) { if(l == r) { Max[rt] = seq[l - 1]; return; } makemid; build(lson); build(rson); pushup(rt); } int ql, qr; int query(root) { if(ql <= l && r <= qr) { return Max[rt]; } makemid; int ret = 0; if(ql <= mid) { ret = max(ret, query(lson)); } if(qr > mid) { ret = max(ret, query(rson)); } return ret; } int main() { int n,q; while(~scanf("%d",&n), n) { scanf("%d", &q); seq.clear(); scanf("%d", c); int curValue = c[0], curNum = 1; For(i, 1, n) { scanf("%d", c + i); if(c[i] == curValue) { ++curNum; pos[i] = pos[i - 1]; } else { seq.push_back(curNum); curValue = c[i]; curNum = 1; pos[i] = pos[i - 1] + 1; } } seq.push_back(curNum); preSum.clear(); preSum.push_back(seq[0]); int len = seq.size(); For(i, 1, len) { preSum.push_back(preSum[i - 1] + seq[i]); } build(1, 1, len); int x,y; while(q--) { scanf("%d %d",&x,&y); --x; --y; if(pos[x] == pos[y]) { printf("%d\n", y - x + 1); continue; } int lmax = preSum[pos[x]] - x; int rmax = y + 1 - preSum[pos[y] - 1]; int res = max(lmax, rmax); if(pos[y] == pos[x] + 1) { printf("%d\n", res); } else { ql = pos[x] + 1 + 1; qr = pos[y] - 1 + 1; printf("%d\n", max(res, query(1, 1, len))); } } } return 0; }
然后是 RMQ 的：
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> using namespace std; #define For(i,s,t) for(int i = (s); i < (t); ++i) const int N = 100005; int c[N]; vector<int> seq, preSum; int pos[N] = {0,}; int d[N][18]; inline void init(int n) { For(i, 0, n) { d[i][0] = seq[i]; } for(int j = 1; (1 << j) < n; ++j) { for(int i = 0; i + (1 << j) - 1 < n; ++i) { d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]); } } } inline int rmq(int L, int R) { int k = 0, len = R - L + 1; while((1 << (k + 1)) < len) ++k; return max(d[L][k], d[R - (1 << k) + 1][k]); } int main() { int n,q; while(~scanf("%d",&n), n) { scanf("%d", &q); seq.clear(); scanf("%d", c); int curValue = c[0], curNum = 1; For(i, 1, n) { scanf("%d", c + i); if(c[i] == curValue) { ++curNum; pos[i] = pos[i - 1]; } else { seq.push_back(curNum); curValue = c[i]; curNum = 1; pos[i] = pos[i - 1] + 1; } } seq.push_back(curNum); preSum.clear(); preSum.push_back(seq[0]); int len = seq.size(); For(i, 1, len) { preSum.push_back(preSum[i - 1] + seq[i]); } init(len); int x,y; while(q--) { scanf("%d %d",&x,&y); --x; --y; if(pos[x] == pos[y]) { printf("%d\n", y - x + 1); continue; } int lmax = preSum[pos[x]] - x; int rmax = y + 1 - preSum[pos[y] - 1]; int res = max(lmax, rmax); if(pos[y] == pos[x] + 1) { printf("%d\n", res); } else { int ql = pos[x] + 1; int qr = pos[y] - 1; printf("%d\n", max(res, rmq(ql, qr))); } } } return 0; }
[uva11235]frequentvalues
题目大意：给一个非降序排列的整数数组a，你的任务是对于一系列询问(i,j)，回答ai,ai+1...aj中次数出现最多的值所出现的次数。解题思路：由于是非降序排列，所有相同的数都是连在一起的。本题可用RMQ做，但是我不会啊。其实... 查看详情
uva11235:frequentvalues(rmq)(代码片段)
Youaregivenasequenceof n integers a1 ,a2 ,...,an innon-decreasingorder.Inadditiontothat,youaregivenseveralqueriesconsistingofindices i and j (1≤i≤j≤n) 查看详情
uva11235frequentvalues(rmq)
题意：给出一个非降序的序列，你的任务是对于一系列询问（i，j），回答在这个区间内出现最多的数的次数。SampleInput103-1-111113101010231105100SampleOutput143思路：将数字分段，相同的为一段，用value[i]和c[i]分别表示第i段的数值和出... 查看详情
[uva11235]frequentvalues（rmq，st，离散化）
题目链接：https://vjudge.net/problem/UVA-11235题意：给一串不递减数字，q次询问，每次查询[l,r]内出现次数最多的数字出现的次数。查询分两部分：一部分是[l,r]为同一个数的区间，另一部分则是在上下界处截取一部分的情况。首先离... 查看详情
uva11235frequentvalues(rmq&&区间出现最多次的数的次数)
题意:给出一个长度为n的不降序序列，并且给出q个形如(L,R)的问询，问你这个区间出现的最多次的数的次数。 分析: 很自然的想到将区间“缩小”，例如112333就可以变成213，构造出“数量数组”，这个数组实际上就是已经... 查看详情
uva11235(代码片段)
N-Frequentvalues题意：给出一个非递减数组，求【L，R】区间内出现最多的数的次数。分析：看训练指南吧。代码：#include<map>#include<queue>#include<vector>#include<math.h>#include<stdio.h>#include<string.h>#include 查看详情
[poj3368][uva11235]frequentvalues[st表](代码片段)
题意：给出一个不降序列，有多个询问，询问[l,r]中出现次数最多的数的出现次数多组数据对于序列-1-111113101010可以这么理解<-1,2>,<1,4>,<3,1>,<10,3>cnt[i]记录这个数字的出现次数,lef[i]记录左端点,righ[i]记录右端点,be... 查看详情
poj3368frequentvalues（线段树区间合并）
【题目链接】 http://poj.org/problem?id=3368 【题目大意】 有一个有序序列，要求区间查询出现次数最多的数 【题解】 维护每个区间左端点和右端点，以及左右的长度，还有区间的答案 每次线段合并的时候... 查看详情
uva-11235rmq
UVA-11235题意：给出一个非降序的整数数组，你的任务是对于一系列询问，回答区间内出现最多的值的次数。tags：大白书的题果然有意思，智商不够用了1】注意给出的是非降序的数组，那么相同的数是连在一起的。所以我们可以... 查看详情
rmq
Frequentvalues UVA-11235 1#include<bits/stdc++.h>2usingnamespacestd;34#defineCLR(m,a)memset(m,a,sizeof(m))56constintmaxn=100010;7intval[maxn],cnt[maxn];8intnum[maxn],Left[maxn],R 查看详情
uva11297census——二维线段树
【题目分析】 二维线段树模板题目。 简直就是无比的暴力。时间复杂度为两个log。 标记的更新方式比较奇特，空间复杂度为N^2。 模板题目。【代码】#include<cstdio>#include<cstring>//#include&l... 查看详情
uva11990”dynamic“inversion（线段树+树状数组）
...计出现的逆序对数量 对于每个删去的数，我们可以用线段树求出它在原序列中的逆序对贡献 在线段树的每个区间有序化数据，就可以二分查找出这个数在每个区间的位置， 这样就处理出了划分出的区间的贡献，先用... 查看详情
uva11297census(二维线段树)
...查询qx1y1x2y2查询这个矩形内的最大值和最小值。析：二维线段树裸板。代码如下：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<string>#include<cstd 查看详情
poj2528uva10587mayor‘sposters线段树(代码片段)
Mayor’spostersTimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:99829Accepted:28528DescriptionThecitizensofBytetown,AB,couldnotstandthatthecandidatesinthemayoralelectioncampaignhavebeenplacingtheirel 查看详情
uva12299带循环移动的rmq（线段树）
...循环移动（往前移动）。分析：求区间问题，很容易想到线段树，西东就相当于单点更新。建树，有两种方案，第一种是nlogn，就是不断的更新，更新logn，有n个数。1#include<bits/stdc++.h>23usingnamespace 查看详情
uva-11992线段树
UVA-11992题意：有一个r*c的全0矩阵,进行3种操作。1x1y1x2y2val表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素加val；2x1y1x2y2val表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素变为val；3x1y1x2y2val表示输出(x1,y1,x2,y2)（x1&l... 查看详情
uva11525permutation——（线段树，脑筋急转弯）
...再用了，依次类推即可得到整个排列了。 那么随便用线段树维护一下即可。 代码如下：1#include<stdio.h>2#include<algorithm>3#include<strin 查看详情
[uva11992]fastmatrixoperations（多延迟标记，二维线段树，区间更新）
...子矩阵和、最小值、最大值n很小(<=20)，所以可以开20棵线段树，每次操作按行更新。特别小心put和add两个延迟标记，坑老惨了。put初始化-1最简单的坑，略过。build的时候要每一个节点都要clear，不能只clear叶 查看详情