【BZOJ】3339: Rmq Problem & 3585: mex（线段树+特殊的技巧）

时间：2024-01-16 11:32:26

http://www.lydsy.com/JudgeOnline/problem.php?id=3585

好神的题。

但是！！！！！！！！！！！！！！我线段树现在要开8倍空间才能过！！！！！！！！！！这什么梗。。。。。。。。。。。。。。。。。。。。。。

我思考了很久空间的问题，因为我在pushdown的时候可能会越界，或许是pushup？

不管了。然后看了zyf的写法。看来以后得注意下。。。pushdown弄成先放了。。。

本题的做法：

好神orz

首先像莫队一样离线区间，左端点在前。

考虑如何从[l, r]转移到[l+1, r]：

显然，a[l]此时是去掉了，l+1~next[l]是空着了a[l]这个自然数的。next[l]是下一个a[l]的位置。

所以我们直接线段树更新l+1~next[i]的sg值即可！即如果这个区间内有询问的sg值>a[l]，那么更新！

好神。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

#define lc x<<1

#define rc x<<1|1

#define MID (l+r)>>1

#define lson l, mid, lc

#define rson mid+1, r, rc

const int N=200005, oo=~0u>>1;

struct dat { int l, r, id; }q[N];

int sg[N], mn[N<<2];

void upd(int x, int k) { mn[x]=min(mn[x], k); }

void pushdown(int x) {

	if(mn[x]!=oo) {

		upd(lc, mn[x]);

		upd(rc, mn[x]);

		mn[x]=oo;

	}

}

void build(int l, int r, int x) {

	if(l==r) { mn[x]=sg[l]; return; }

	mn[x]=oo;

	int mid=MID;

	build(lson); build(rson);

}

void update(int l, int r, int x, int L, int R, int k) {

	if(L<=l && r<=R) { mn[x]=min(mn[x], k); return; }

	pushdown(x);

	int mid=MID;

	if(L<=mid) update(lson, L, R, k);

	if(mid<R) update(rson, L, R, k);

}

int query(int l, int r, int x, int k) {

	if(l==r) return mn[x];

	pushdown(x);

	int mid=MID;

	if(k<=mid) return query(lson, k);

	return query(rson, k);

}

int a[N], b[N], n, m, tot, vis[N], ans[N], inext[N];

void getnext() {

	for1(i, 1, n) b[i]=a[i];

	sort(b+1, b+1+n); tot=unique(b+1, b+1+n)-b-1;

	for1(i, 1, n) a[i]=lower_bound(b+1, b+1+tot, a[i])-b;

	for1(i, 1, tot) vis[i]=0;

	for3(i, n, 1) inext[i]=vis[a[i]], vis[a[i]]=i;

}

bool cmp(const dat &a, const dat &b) { return a.l<b.l; }

void init() {

	int k=0;

	for1(i, 1, n) {

		if(a[i]<N) vis[a[i]]=1;

		while(vis[k]) ++k;

		sg[i]=k;

	}

	build(1, n, 1);

	sort(q+1, q+1+m, cmp);

	getnext();

	int now=1;

	for1(i, 1, m) {

		int l=q[i].l;

		while(now<l) {

			int nxt=inext[now];

			if(nxt==0) nxt=n;

			else --nxt; // printf("now:%d nxt:%d a[now]:%d\n", now, nxt, b[a[now]]);

			if(now+1<=nxt) update(1, n, 1, now+1, nxt, b[a[now]]);

			++now;

		}

		ans[q[i].id]=query(1, n, 1, q[i].r);

	}

	for1(i, 1, m) printf("%d\n", ans[i]);

}

int main() {

	read(n); read(m);

	for1(i, 1, n) read(a[i]);

	for1(i, 1, m) read(q[i].l), read(q[i].r), q[i].id=i;

	init();

	return 0;

}

　　

Description

　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

　　第一行n,m。
　　第二行为n个数。
　　从第三行开始，每行一个询问l,r。

Output

　　一行一个数，表示每个询问的答案。

Sample Input

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5

Sample Output

1
2
3
0
3

HINT

数据规模和约定

　　对于100%的数据：

　　1<=n,m<=200000

　　0<=ai<=109

　　1<=l<=r<=n

　　对于30%的数据：

　　1<=n,m<=1000

Source

相关文章