|
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
上金工实习,无聊,找到题目想想吧,那就pku 3368吧,一直想做掉却一直没想法,题目意思很明确,
给定一串序列,然后是m条询问,问[a, b]区间之间出现的数字频率最多的是哪个数,由于m很大,所以
询问的复杂度必须要是log(n),这样一来就先确定下来是线段树了,但是以前没深入想下去,
重新看了遍题目,然后到了8教就开始想,突然就有思路了,主要是以前有个限制条件没看见,
有了这个限制条件题目就变得简单了。就是这句话in non-decreasing order,所有的数非递减排列。
换言之,就是说如果两个数相同的话,他们必定生活在以前,并且中间的数和他们也相同。
于是就有了nlog(n)的算法:
对于所有的数均设定一个组号,也可以叫离散化吧,相同的数有相同的组号,然后将各个数的频率统计后
记录在一个数组中,表示该类数的大小,然后对于输入的询问[x, y],直接查询它们在哪个组,分三种情况
1. 如果x和y在一个组,那么最长长度就是y - x + 1
2. 如果组号相差1,那么找出两者的分界点z(假设z点和x点组号相同),那么答案就是Max{z - x + 1, y - z}
3. 如果相差大于1,那么先将两头截掉,统计大的记录,再和中间那段的最大值比较大小,中间那段的最大值可以用线段树区间查询最值
*/
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct point {
int start;
int end;
int num;
int coun;
}p[ 100010 ];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int ori[ 100010 ];
int n, T;
int Rhash[ 100010 ]; //第i个数所在新的分组中的编号
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Seg {
int num;
int Count;
}tree[1000010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void init() {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
T = 1;
p[1].start = 0;
p[1].end = 0;
p[1].coun = 1;
p[1].num = ori[0];
Rhash[ 0 ] = 1;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i < n; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(ori[i] == ori[i-1]) {
p[ T ].coun ++;
p[ T ].end = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
T ++;
p[ T ].num = ori[i];
p[ T ].coun = 1;
p[ T ].start = i;
p[ T ].end = i;
}
Rhash[ i ] = T;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Build(int P, int l, int r) {
int mid = (l + r) / 2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l == r) {
tree[P].Count = p[l].coun;
tree[P].num = p[l].num;
return ;
}
Build(2*P, l, mid);
Build(2*P+1, mid+1, r);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(tree[2*P].Count > tree[2*P+1].Count) {
tree[P] = tree[2*P];
}else
tree[P] = tree[2*P+1];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Query(int P, int a, int b, int l, int r) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(a == l && r == b) {
return tree[P].Count;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mid = (l + r) / 2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(b <= mid) {
return Query(2*P, a, b, l, mid);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(mid + 1 <= a) {
return Query(2*P+1, a, b, mid+1, r);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
int x = Query(2*P, a, mid, l, mid);
int y = Query(2*P+1, mid+1, b, mid+1, r);
return x > y ? x : y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Solve(int x, int y) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//如果所在组号相同,说明中间所有数都是一样的,直接返回区间长度
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(Rhash[x] == Rhash[y]) {
return y - x + 1;
}
//如果组号相差1,说明中间必定由一个分段点,将[x, y]线段分成两段,去大的
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else if(Rhash[x] + 1 == Rhash[y]) {
int l = p[ Rhash[x] ].end - x + 1;
int r = y - p[ Rhash[y] ].start + 1;
return l > r ? l : r;
}
//如果组号相差1以上,那么端点的两个取最大,中间的区段用线段树查询最大值
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int l = p[ Rhash[x] ].end - x + 1;
int r = y - p[ Rhash[y] ].start + 1;
int Max = l > r ? l : r;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ans = Query(1, Rhash[x] + 1, Rhash[y] - 1, 1, T);
return Max > ans ? Max : ans;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i;
int q, x, y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d", &n) != EOF && n) {
scanf("%d", &q);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < n; i++) {
scanf("%d", &ori[i]);
}
init();
Build(1, 1, T);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(q--) {
scanf("%d %d", &x, &y);
x --; y --;
printf("%d\n", Solve(x, y) );
}
}
return 0;
}
|