有没有专业做咖啡店设计的网站,海口免费自助建站模板,WordPress中文音乐主题,seo深度解析Frequent values UVA - 11235
题目传送门
题目大意#xff1a;给出一个非降序的整数数组a1,a2,a3...an#xff0c;你的任务是对一系列的询问#xff08;i,j#xff09;#xff0c;回答ai,ai1,ai2...aj中出现次数最多的值所出现的次数。输入包括多组数据。每组数据第一行…Frequent values UVA - 11235
题目传送门
题目大意给出一个非降序的整数数组a1,a2,a3...an你的任务是对一系列的询问i,j回答ai,ai1,ai2...aj中出现次数最多的值所出现的次数。输入包括多组数据。每组数据第一行为两个整数n和q(1n,q100000)。第二行包含n个非降序排列的整数a1,a2,a3...an(-100000ai100000)以下q行每行包括两个整数i和j(1ijn)输入以0结束。
解决方法:用value[i]和Count[i]分别表示第i段的数值和出现的次数num[p],Left[p],Right[p]分别表示位置p所在段的编号和左右端点的位置所以i,j的答案就是取Right[i]-i1j-Left[j]1query(1,t,1,num[i]1,num[j]-1)的最大值。
AC代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
int arr[maxn];
int maxl[maxn];
int value[maxn];
int Count[maxn];
int Left[maxn];
int Right[maxn];
int num[maxn];
void pushup(int x)
{maxl[x]max(maxl[x1],maxl[x1|1]);
}
void build(int l,int r,int x)
{if(lr){maxl[x]Count[l];return ;}int mid(lr)1;build(l,mid,x1);build(mid1,r,x1|1);pushup(x);
}
int query(int l,int r,int x,int L,int R)
{int ans0;if(LlrR)return maxl[x];int mid(lr)1;if(Lmid)ansmax(ans,query(l,mid,x1,L,R));if(Rmid)ansmax(ans,query(mid1,r,x1|1,L,R));return ans;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);#endif//freopen(out.txt, w, stdout);ios::sync_with_stdio(0),cin.tie(0);int n,m;while(cinnn){cinm;ms(maxl);ms(arr);ms(value);ms(Count);ms(num);ms(Left);ms(Right);int t0;int l11,r1n;rep(i,1,n) {cinarr[i];if(arr[i]!arr[i-1]||i1){t;if(i!1)l1i;}num[i]t;Count[t];value[t]arr[i];Left[i]l1;}lep(i,n,1) {Right[i]r1;if(arr[i]!arr[i-1])r1i-1;}build(1,t,1);while(m--){int a,b;cinab;if(ab)cout1endl;else {int ans0;ansquery(1,t,1,num[a]1,num[b]-1);int nape;if(Right[a]Right[b])napeb-a1;elsenapemax(Right[a]-a1,b-Left[b]1);ansmax(ans,nape);coutansendl;}}}return 0;
}
