欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-02 11:19:00
题意 一天做到两道这种题目描述如此神仙的题也是够了。真锻炼语文能力。 题目的意思其实就是,给你一个序列,然后每次询问一个区间。使得尽量 ......

题目链接

题意

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

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

一言

烟花易冷,人事易分。