链接
https://www.luogu.org/problemnew/show/P4137
思路
做了好几次，每次都得想一会，再记录一下
可持久化权值线段树
区间出现存最小的下标
然后线段树上二分
如果左边min>L
那就去右边
因为左边都被【L,R】占满了
虽然比卡常的莫队慢好多(700ms和1000ms)
但是理论上快哇
线段树
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
int x = 0, f = 1; char s = getchar();
for(; s > '9' || s < '0'; s = getchar()) if(s == '-') f = -1;
for(; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
int n, m, a[N], rt[N];
namespace seg_tree {
#define ls e[rt].ch[0]
#define rs e[rt].ch[1]
struct node {int ch[2],mex;}e[N*31];
int cnt;
void modify(int &rt, int old, int l, int r, int L) {
rt = ++cnt;
e[rt] = e[old];
if(l == r) {
e[rt].mex = L;
return;
}
int mid = (l + r) >> 1;
if(a[L] <= mid) modify(ls, e[old].ch[0], l, mid, L);
else modify(rs, e[old].ch[1], mid + 1, r, L);
e[rt].mex = min(e[ls].mex ,e[rs].mex);
}
int query(int rt, int l, int r, int L) {
if(l == r) return l;
int mid = (l + r) >> 1;
if(e[ls].mex >= L) return query(rs, mid + 1, r, L);
else return query(ls, l, mid, L);
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) a[i] = min(read(), 200000);
for (int i = 1; i <= n; ++i) {
seg_tree::modify(rt[i], rt[i-1], 0, 200000, i);
}
for (int i = 1; i <= m; ++i) {
int x = read(), y = read();
printf("%d
", seg_tree::query(rt[y], 0, 200000, x));
}
return 0;
}
莫队
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#define maxn 301001
using namespace std;
int n,m,now;
int a[maxn];
int belong[maxn];
int vis[maxn];
int ma;
struct node {
int l,r,id;
} q[maxn];
int ans[maxn];
inline int read() {
int x=0,f=1;char s=getchar();
while('0'>s||s>'9') {if(s=='-') f=-1;s=getchar();}
while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
inline bool cmp(node a,node b) {
return belong[a.l]==belong[b.l] ? belong[a.l]&1 ? a.r<b.r : a.r>b.r : belong[a.l]<belong[b.l];
}
inline void add(int x) {
++vis[x];
if(now < x) return;
if(now==x&&vis[x]==1) {
for(int i=now+1; i<n; ++i) {
if(!vis[i]) {
now=i;
return;
}
}
}
}
inline void delet(int x) {
--vis[x];
if(now < x) return;
if(now > x) {
if(!vis[x]) {
now=x;
}
}
}
int main() {
n=read();
m=read();
int k=n/sqrt(m);
for(int i=1; i<=n; ++i) {
a[i]=read();
if(a[i] > n)
a[i]=n+1;
}
for(int i=1; i<=n; ++i)
belong[i]=(i-1)/k+1;
for(int i=1; i<=m; ++i)
{
q[i].l=read();
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int l=1,r=0;
for(int i=1; i<=m; ++i) {
while(l > q[i].l) add(a[--l]);
while(l < q[i].l) delet(a[l++]);
while(r < q[i].r) add(a[++r]);
while(r > q[i].r) delet(a[r--]);
ans[q[i].id]=now;
}
for(int i=1; i<=m; ++i)
printf("%d
",ans[i]);
return 0;
}