【Luogu4137】Rmq Problem/mex (莫队)
Problem 莫队 rmq
2023-09-11 14:14:41 时间
【Luogu4137】Rmq Problem/mex (莫队)
题面
题解
裸的莫队
暴力跳\(ans\)就能\(AC\)
考虑复杂度有保证的做法
每次计算的时候把数字按照大小也分块
每次就枚举答案在哪一块里面就好
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 220000
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int n,m,blk;
struct Query{int l,r,blk,id;}q[MAX];
int cnt[MAX],ans=0;
int Ans[MAX],a[MAX];
int sum[MAX];
bool operator<(Query a,Query b)
{
if(a.blk!=b.blk)return a.blk<b.blk;
return a.r<b.r;
}
void work(int l,int w)
{
if(w==1)
{
cnt[a[l]]++;
if(cnt[a[l]]==1)sum[a[l]/450]++;
}
else
{
cnt[a[l]]--;
if(!cnt[a[l]])sum[a[l]/450]--;
}
}
int calc()
{
for(int i=0;i<=450;++i)
if(sum[i]!=450)
for(int j=0;j<=449;++j)
if(!cnt[i*450+j])return i*450+j;
}
int main()
{
n=read();m=read();blk=sqrt(n);
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].blk=(q[i].l-1)/blk+1;
sort(&q[1],&q[m+1]);
int l=1,r=0;
for(int i=1;i<=m;++i)
{
while(r<q[i].r)work(++r,1);
while(r>q[i].r)work(r--,-1);
while(l<q[i].l)work(l++,-1);
while(l>q[i].l)work(--l,1);
Ans[q[i].id]=calc();
}
for(int i=1;i<=m;++i)
printf("%d\n",Ans[i]);
return 0;
}
相关文章
- Leetcode: Water and Jug Problem && Summary: GCD求法(辗转相除法 or Euclidean algorithm)
- Leetcode: The Skyline Problem
- Eclipse出现"Running Android Lint has encountered a problem"解决方式
- log4net encoding problem
- 【BZOJ2998】Problem A(动态规划)
- Leetcode 218 The Skyline Problem
- UVA - 10245 The Closest Pair Problem
- 【BZOJ3489】A simple rmq problem kd-tree
- 2015 Multi-University Training Contest 1 hdu 5296 Annoying problem
- C#,布尔表达式括号问题(Boolean Parenthesization Problem)的求解算法与源代码
- C#,回文分割问题(Palindrome Partitioning Problem)算法与源代码
- HDU 1402 A * B Problem Plus (FFT)
- 【HDU 5832】A water problem(大数取模)
- hdu - 4971 - A simple brute force problem.(最大权闭合图)