题目链接

题意

一天做到两道这种题目描述如此神仙的题也是够了。真锻炼语文能力。

题目的意思其实就是，给你一个序列，然后每次询问一个区间。使得尽量按照严格上升的顺序从这个区间内取数。如果当前取得数字小于等于前面的其中一个，就让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;

}

一言

烟花易冷，人事易分。