luogu 3709 大爷的字符串题 构造 莫队 区间众数
题目链接
题目描述
给你一个字符串a,每次询问一段区间的贡献
贡献定义:
每次从这个区间中随机拿出一个字符\(x\),然后把\(x\)从这个区间中删除,你要维护一个集合S
如果\(S\)为空,你\(rp\)减\(1\)
如果S中有一个元素不小于\(x\),则你\(rp\)减\(1\),清空\(S\)
之后将\(x\)插入\(S\)
由于你是大爷,平时做过的题考试都会考到,所以每次询问你搞完这段区间的字符之后最多还有多少\(rp\)?\(rp\)初始为\(0\)
询问之间不互相影响~
输入输出格式
输入格式:
第一行两个数\(n\),\(m\),表示字符串长度与询问次数
之后一行\(n\)个数,表示字符串
由于你是大爷,所以字符集\(1e9\)
之后\(m\)行每行两个数,表示询问的左右区间
输出格式:
\(m\)行,每行一个数表示答案
输入输出样例
输入样例#1:
3 3
3 3 3
3 3
3 3
3 3
输出样例#1:
-1
-1
-1
思路
构造
要使得扣除尽量少的\(rp\),就要使得每次操作插入的数大于原先集合中已有的数字,即保持集合的严格单调性。到万不得已的时候再重新开始。
共需重新开始的次数为出现最多的一个数出现的个数,即众数的出现次数。
故题意就是给一个序列,每次询问一个区间,问这个区间里的众数的出现次数。
莫队算法
可用莫队算法离线处理所有询问。
维护众数的出现次数:用\(cnt[i]\)维护数字\(i\)的出现次数,用\(num[i]\)维护出现了\(i\)次的数字有多少个,因此,最大的不为\(0\)的\(num[\ ]\)的下标即为众数的出现次数。
注意点
读入初始数据之后就要进行离散化。如果用\(map\)存,每次操作的时候都进行映射,这样时间代价太大。
Code
/*
下面是50分代码↓↓↓
基本上参考着Candy?大佬的从头到尾改了一遍后来又厚颜无耻地交了一发大佬的代码都还是有5组一直T十分困惑...。
就姑且先50分着吧。还是学到了不少的,比如莫队的优美写法、\(cnt\)和\(num\)的妙招、先离散化而不是用\(map\)瞎搞。
*/
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long LL;
int a[maxn], ans[maxn], cnt[maxn], mp[maxn], num[maxn], now, block[maxn];
struct node {
int l, r, id;
}q[maxn];
inline LL read(){
char c=getchar(); LL x=0,f=1;
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;
}
bool cmp(node u, node v) {
return block[u.l] < block[v.l] || (block[u.l] == block[v.l] && block[u.r] < block[v.r]);
}
void add(int i) {
--num[cnt[a[i]]], ++num[++cnt[a[i]]];
while (num[now+1]) ++now;
}
void del(int i) {
--num[cnt[a[i]]], ++num[--cnt[a[i]]];
while (!num[now]) --now;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int grp = sqrt(n);
for (int i = 1; i <= n; ++i) a[i] = mp[i] = read(), block[i] = (i-1) / grp;
sort(mp+1, mp+1+n);
int nn = unique(mp+1, mp+1+n) - (mp+1);
for (int i = 1; i <= n; ++i) a[i] = lower_bound(mp+1, mp+1+nn, a[i]) - mp;
for (int i = 0; i < m; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q, q+m, cmp);
int l = 0, r = 0;
for (int i = 0; i < m; ++i) {
while (q[i].l < l) add(--l);
while (q[i].l > l) del(l++);
while (q[i].r < r) del(r--);
while (q[i].r > r) add(++r);
ans[q[i].id] = now;
}
for (int i = 0; i < m; ++i) printf("%d\n", -ans[i]);
return 0;
}
最新文章
- css面包屑导航编号
- 常见ES6新属性
- 在C#代码中应用Log4Net 中配置文件的解释
- PowerDesigner反向数据库时遇到[Microsoft][ODBC SQL Server Driver][SQL Server]无法预定义语句。SQLSTATE = 37错误解决方法
- linux 打开远程samba服务器
- BZOJ 1052: [HAOI2007]覆盖问题
- JavaScript之arguments.callee
- Effective Java 第三版——23. 优先使用类层次而不是标签类
- HDU 4526 拼车记
- [摘译] IK: 操纵关节式物体的反向动力学和几何约束
- DevExpress中获取GridControl排序之后的List
- Nutch1.7学习笔记:基本环境搭建及使用
- Pig的使用场景
- windows下安装TA-Lib库
- Jqgrid利用正则匹配表达式正确移除html标签
- Yii登录验证和全局访问用户ID
- Git实战(四)状态转换
- Asp.Net MVC anti-forgery token的问题:nameidentifier or identityprovider not present
- 开源PCRF、PCRF体验与PCRF实现
- 用CSS模拟魔兽世界技能冷却的效果