Frequent values POJ - 3368(线段树，区间合并)

本文主要是介绍Frequent values POJ - 3368(线段树，区间合并)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Frequent values POJ - 3368

题目链接

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

题目要求区间内出现次数最多的数的出现次数，那么这一个值是必须要有的，记为maxx吧；
对于一个连续的区间[l, r]，若它是由两个区间[l, mid], [mid+1, r]合并过来的，那么可以合并的前提条件是：

a[l]==a[mid+1]：左区间和右区间的左半部分合并；
a[mid]==a[r]：左区间的右半部分和右区间合并；
a[l]==a[r]：左区间和右区间合并；
a[mid]==a[mid+1]：左区间的右半部分和右区间的左半部分合并；
那么我们就需要记录lson, rson分别用来表示该区间最左边的数的出现次数和最右边数的出现次数；

然后就直接建树，然后查询；
对于查询同样要和合并一样分情况；

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1e5+10;
struct node{int l, r, lson, rson, maxx;
}tr[maxn<<2];
int a[maxn];
void pushup(int m){//先继承左右孩子的最大值；tr[m].lson=tr[m<<1].lson;tr[m].rson=tr[m<<1|1].rson;tr[m].maxx=max(tr[m<<1].maxx, tr[m<<1|1].maxx);//然后就行合并；int len=0, lson=0, rson=0, maxx=0;if(a[tr[m<<1].l]==a[tr[m<<1|1].r]){//a[l]==a[l]len=tr[m<<1].lson+tr[m<<1|1].rson;}if(a[tr[m<<1].l]==a[tr[m<<1|1].l]){//a[l]==a[mid+1]lson=tr[m<<1].lson+tr[m<<1|1].lson;}if(a[tr[m<<1].r]==a[tr[m<<1|1].r]){//a[mid]==a[r]rson=tr[m<<1|1].rson+tr[m<<1].rson;}if(a[tr[m<<1].r]==a[tr[m<<1|1].l]){//a[mid]==a[mid+1]maxx=tr[m<<1].rson+tr[m<<1|1].lson;}//维护最值；tr[m].lson=max(tr[m].lson, max(len, lson));tr[m].rson=max(tr[m].rson, max(len, rson));tr[m].maxx=max(tr[m].maxx, max(maxx, len));tr[m].maxx=max(tr[m].maxx, max(tr[m].lson, tr[m].rson));//printf("m:%d l:%d r:%d lson:%d maxx:%d rson:%d\n", m, tr[m].l, tr[m].r, tr[m].lson, tr[m].maxx, tr[m].rson);
}
void build(int m, int l, int r){tr[m].l=l;tr[m].r=r;if(l==r){tr[m].lson=tr[m].rson=tr[m].maxx=1;return;}int mid=(l+r)>>1;build(m<<1, l, mid);build(m<<1|1, mid+1, r);pushup(m);
}
//得到区间[l, r]中最左边数的出现次数；
int query_lson(int m, int l, int r){//printf("query_lson: m:%d tr[m].l:%d tr[m].r:%d l:%d r:%d\n", m, tr[m].l, tr[m].r, l, r);if(tr[m].l==l&&tr[m].r==r){//cout << ".............." << endl;return tr[m].lson;}int mid=(tr[m].l+tr[m].r)>>1;if(r<=mid) return query_lson(m<<1, l, r);else if(l>mid) return query_lson(m<<1|1, l, r);else{if(a[l]==a[mid+1]) return mid-l+1+query_lson(m<<1|1, mid+1, r);else return query_lson(m<<1, l, mid);}
}
//得到区间[l, r]中最右边数的出现次数；
int query_rson(int m, int l, int r){//printf("query_son: m:%d tr[m].l:%d tr[m].r:%d l:%d r:%d\n", m, tr[m].l, tr[m].r, l, r);if(tr[m].l==l&&tr[m].r==r){//cout << ".............." << endl;return tr[m].rson;}int mid=(tr[m].l+tr[m].r)>>1;if(r<=mid) return query_rson(m<<1, l, r);else if(l>mid) return query_rson(m<<1|1, l, r);else{if(a[r]==a[mid]) return r-mid+query_rson(m<<1, l, mid);else return query_rson(m<<1|1, mid+1, r);}
}
//得到区间[l, r]中最大出现次数；
int query(int m, int l, int r){//printf("query: m:%d tr[m].l:%d tr[m].r:%d l:%d r:%d\n", m, tr[m].l, tr[m].r, l, r);if(tr[m].l==l&&tr[m].r==r){//cout << ".............." << endl;return tr[m].maxx;}int mid=(tr[m].l+tr[m].r)>>1;if(r<=mid) return query(m<<1, l, r);else if(l>mid) return query(m<<1|1, l, r);else{int lson=0, rson=0, mson=0, max1=0, max2=0;if(a[l]==a[r]){return r-l+1;}//查询时的合并；if(a[l]==a[mid+1]) lson=mid-l+1+query_lson(m<<1|1, mid+1, r);if(a[mid]==a[r]) rson=r-mid+query_rson(m<<1, l, mid);if(a[mid]==a[mid+1]) mson=query_rson(m<<1, l, mid)+query_lson(m<<1|1, mid+1, r);max1=query(m<<1, l, mid), max2=query(m<<1|1, mid+1, r);return max(lson, max(rson, max(mson, max(max1, max2))));}
}
int main(){int n, q;while(scanf("%d", &n), n){scanf("%d", &q);for(int i=1; i<=n; i++){scanf("%d", &a[i]);}build(1, 1, n);while(q--){int i, j;scanf("%d%d", &i, &j);printf("%d\n", query(1, i, j));}}return 0;
}