[luogu3709][大爷的字符串题]

题目链接

题意

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

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

一言

烟花易冷，人事易分。