本文共 1144 字，大约阅读时间需要 3 分钟。
题意：
n个数q个询问，每次询问区间[i,j]中数出现最多的数的次数，序列是非降序的。
分析：
相同的数都是相邻的，把每段相同的数，标记起来，每段的标号id，左右边界left,right，数量num，当查询时，由三部分right[i]-i+1、j-left[j]+1、和编号id[i]+1,id[j]-1数量的最大值(用RMQ)
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef pair PII;typedef long long ll;#define lson l,m,rt<<1#define pi acos(-1.0)#define rson m+1,r,rt<<11#define All 1,N,1#define N 100010#define read freopen("in.txt", "r", stdin)const ll INFll = 0x3f3f3f3f3f3f3f3fLL;const int INF= 0x7ffffff;const int mod = 1000000007;int n,q,v[N],num[N],id[N],lef[N],righ[N],len,d[N][20];void init(){ for(int i=0;i =0;--i) { if(a[i]!=a[i+1]) r=i; righ[i]=r; } init(); int x,y; while(q--){ scanf("%d%d",&x,&y); x--; y--; if(id[x]==id[y]) printf("%d\n",y-x+1); else if(id[y]-id[x]==1) printf("%d\n",max(righ[x]-x+1,y-lef[y]+1)); else printf("%d\n",max(max(righ[x]-x+1,y-lef[y]+1),RMQ(id[x]+1,id[y]-1))); } }return 0;}
转载于:https://www.cnblogs.com/zsf123/p/4909810.html