題意 一天做到兩道這種題目描述如此神仙的題也是夠了。真鍛煉語文能力。 題目的意思其實就是，給你一個序列，然後每次詢問一個區間。使得儘量 ...
題目鏈接
題意
一天做到兩道這種題目描述如此神仙的題也是夠了。真鍛煉語文能力。
題目的意思其實就是，給你一個序列，然後每次詢問一個區間。使得儘量按照嚴格上升的順序從這個區間內取數。如果當前取得數字小於等於前面的其中一個，就讓rp--，然後重新開始記錄。問rp最多可以是多少。
思路
思考一下可以發現，其實就是求區間內眾數出現的次數。
原因如下:
如果有相等的數字，那麼這些數字是無法避免rp--的。既然無論如何都要減了，那麼就要考慮如何讓他減得更有價值。
比如說有一段序列:1 1 1 2 2 5 5 6 7 8
現在1 和 2都是有多個，顯然按照下麵的順序取數是最優秀的:
1 2 5 6 7 8 1 2 5 1
這樣減掉的rp其實就是眾數1出現的次數。
所以這道題就是詢問區間內眾數出現的次數了。可以用莫隊來實現。
用cnt[i]來表示i這個數字出現的次數(需要先離散化)。T[i]表示出現次數為i的數的個數。
在從一個區間向另一個區間轉移時，方法很顯然。具體見代碼
代碼
/*
* @Author: wxyww
* @Date: 2018-12-17 20:07:20
* @Last Modified time: 2018-12-17 20:40:37
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int N = 200000 + 10;
map<int,int>ma;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int a[N],cnt[N],ls[N],anss[N];
int ans,L,R,belong[N],T[N];
struct node {
int id,l,r;
}Q[N];
bool cmp(node x,node y) {
return belong[x.l] == belong[y.l] ? x.r < y.r : x.l < y.l;
}
void update(int pos,int c) {
T[cnt[a[pos]]]--;
if(T[cnt[a[pos]]] == 0 && ans == cnt[a[pos]]) {
while(T[ans] == 0 && ans) ans--;
}
cnt[a[pos]] += c;
T[cnt[a[pos]]]++;
if(cnt[a[pos]] > ans) ans = cnt[a[pos]];
}
int main() {
int n = read(),m = read();
int blsiz = sqrt(n);
for(int i = 1;i <= n;++i) ls[i] = a[i] = read(),belong[i] = (i - 1) / blsiz + 1;
int lsjs = 0;
sort(ls + 1,ls + n + 1);
ma[ls[1]] = ++lsjs;
for(int i = 2;i <= n;++i) if(ls[i] != ls[i - 1]) ma[ls[i]] = ++lsjs;
for(int i = 1;i <= n;++i) a[i] = ma[a[i]];
for(int i = 1;i <= m;++i)
Q[i].l = read(),Q[i].r = read(),Q[i].id = i;
sort(Q + 1,Q + n + 1,cmp);
for(int i = 1;i <= m;++i) {
while(L > Q[i].l) update(--L,1);
while(R < Q[i].r) update(++R,1);
while(L < Q[i].l) update(L++,-1);
while(R > Q[i].r) update(R--,-1);
anss[Q[i].id] = ans;
}
for(int i = 1;i <= m;++i) printf("%d\n",-anss[i]);
return 0;
}
