BZOJ 3339 & 莫队+"所谓的暴力"

题意:

　　给一段数字序列,求一段区间内未出现的最小自然数.

SOL:

　　框架显然用莫队.因为它兹瓷离线.

　　然而在统计上我打了线段树...用&维护的结点...400w的线段树...然后二分查找...炸的妥妥的...

　　然后发现所谓的"暴力"...直接开数组维护...因为指针具有一定的单调性,一次更改可以直接得到解,不用每次都查询...

　　woc真是...有时候数据结构用多了忽略了那些更简单更实用的方法...

Code

　　TLE的代码:

/*==========================================================================

# Last modified: 2016-03-22 20:48

# Filename: 3339.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 3600000

#define cap 201000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

struct Query{

	int l,r,id,op;

}q[cap];

int n,m;

int v[maxn],a[cap],ans[cap];

int cmp(const Query &x,const Query &y){

	if (x.op==y.op) return x.r<y.r;

	else return x.op<y.op;

}

void change(int node,int l,int r,int x,int d){

	if (l==r) { v[node]+=d; return;}

	int mid=rs(l,r),lc=ls(node,0),rc=lc|1;

	if (x<=mid) change(lc,l,mid,x,d);

		else change(rc,mid+1,r,x,d);

	v[node]=(v[lc]?1:0)&(v[rc]?1:0);

}

int query(int node,int l,int r){

	if (l==r) return l;

	int mid=rs(l,r),lc=ls(node,0),rc=lc|1;

	if (!v[lc]) query(lc,l,mid);

		else query(rc,mid+1,r);

}

void init(){

	read(n); read(m);

	int sz=trunc(sqrt(n));

	FORP(i,1,n) { read(a[i]); a[i]++;}

	FORP(i,1,m) {

		read(q[i].l); read(q[i].r); q[i].id=i;

		q[i].op=q[i].l/sz+(q[i].l%sz?1:0);

	}

}

int main(){

	init();

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

	int L=q[1].l,R=q[1].r;

	FORP(i,L,R) change(1,1,cap,a[i],1);

	ans[q[1].id]=query(1,1,cap);

	FORP(i,2,m){

		while (L<q[i].l) { change(1,1,cap,a[L],-1); L++;}

		while (L>q[i].l) { L--; change(1,1,cap,a[L],1);}

		while (q[i].r<R) { change(1,1,cap,a[R],-1); R--;}

		while (q[i].r>R) { R++; change(1,1,cap,a[R],1);}

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

	}

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

}

　　A掉的代码:

/*==========================================================================

# Last modified: 2016-03-22 20:48

# Filename: 3339.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 3600000

#define cap 201000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

struct Query{

	int l,r,id,op;

}q[cap];

int n,m;

int cnt[maxn],a[cap],ans[cap];

int now=0;

int cmp(const Query &x,const Query &y){

	if (x.op==y.op) return x.r<y.r;

	else return x.op<y.op;

}

void change(int x,int d){

	cnt[x]+=d;

	if (x<now){

		if (cnt[x]==0) now=x;

	}

	else if (now==x)

		while(cnt[now]) now++;

}

void init(){

	read(n); read(m);

	int sz=trunc(sqrt(n));

	FORP(i,1,n) { read(a[i]);}

	FORP(i,1,m) {

		read(q[i].l); read(q[i].r); q[i].id=i;

		q[i].op=q[i].l/sz+(q[i].l%sz?1:0);

	}

}

int main(){

	init();

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

	int L=q[1].l,R=q[1].r;

	FORP(i,L,R) change(a[i],1);

	ans[q[1].id]=now;

	FORP(i,2,m){

		while (L<q[i].l) { change(a[L],-1); L++;}

		while (L>q[i].l) { L--; change(a[L],1);}

		while (q[i].r<R) { change(a[R],-1); R--;}

		while (q[i].r>R) { R++; change(a[R],1);}

		ans[q[i].id]=now;

	}

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

}

巴特西

BZOJ 3339 & 莫队+"所谓的暴力"

最新文章

热门文章