FREQUENT - Frequent values

luogu-SP1684

poj 3368

题目大意：

有一个单调不降序列，让你求出某些区间内的出现次数最多的数出现的次数（有多组数据，以0结尾）

输入样例

10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0

输出样例

1 4 3

数据范围：

$1\le n,q\le 100000$
$-100000\le a_i\le 100000$

解题思路：

用线段树，同时要保存左边数字出现的次数，和右边数字出现的次数，如果中间相等，就可以尝试拼接

代码：

#include<cstdio> #include<cstring> #include<iostream> #define max(x,y) (x)>(y)?(x):(y) using namespace std; int n,m,x,y,s[100500]; struct rec {int l,r,num,ls,rs; }tree[800500]; void up(int dep,int mid)//传递 {tree[dep].num=max(tree[dep*2].num,tree[dep*2+1].num);tree[dep].ls=tree[dep*2].ls;//ls是左边的数出现的次数tree[dep].rs=tree[dep*2+1].rs;//rs是右边的数出现的次数if (s[mid]==s[mid+1])tree[dep].num=max(tree[dep].num,tree[dep*2].rs+tree[dep*2+1].ls);//如果可以就合并if (s[tree[dep].l]==s[mid+1])tree[dep].ls+=tree[dep*2+1].ls;//同上if (s[mid]==s[tree[dep].r])tree[dep].rs+=tree[dep*2].rs;return; } void make(int dep)//建树 {if (tree[dep].l==tree[dep].r){tree[dep].num=1;tree[dep].ls=1;tree[dep].rs=1;return;}int mid=(tree[dep].l+tree[dep].r)>>1;tree[dep*2].l=tree[dep].l,tree[dep*2].r=mid;tree[dep*2+1].l=mid+1,tree[dep*2+1].r=tree[dep].r;make(dep*2);make(dep*2+1);up(dep,mid);return; } int find(int dep,int l,int r) {if (tree[dep].l==l&&tree[dep].r==r) return tree[dep].num;if (tree[dep].l>=tree[dep].r) return 0;int mid=(tree[dep].l+tree[dep].r)>>1,sum=1,sum1=1;if (r<=mid) return find(dep*2,l,r);//在左边if (l>mid) return find(dep*2+1,l,r);//在右边if (s[mid]==s[mid+1]) sum=min(mid-l+1,tree[dep*2].rs)+min(r-mid,tree[dep*2+1].ls);//合并sum1=max(find(dep*2,l,mid),find(dep*2+1,mid+1,r));//去一个更优的return max(sum,sum1);//两种方法选一种 } int main() {while(scanf("%d",&n),n)//多组数据{memset(tree,0,sizeof(tree));scanf("%d",&m);for (int i=1;i<=n;++i)scanf("%d",&s[i]);tree[1].l=1;tree[1].r=n;make(1);for (int i=1;i<=m;++i){scanf("%d %d",&x,&y);printf("%d\n",find(1,x,y));}} }

总结

以上是生活随笔为你收集整理的【线段树】FREQUENT - Frequent values（luogu-SP1684 / poj 3368）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。