【bzoj 3585】mex莫隊+ブロック
ACチャネル:http://www.lydsy.com/JudgeOnline/problem.php?id=3585
【問題解】
この問題は思考が少し難しいので、コンニャクはpopoQQQおじいさんの問題解を覗かざるを得なかった.
1~n間の自然数をルート番号nブロックに分割し、各ブロックは現在のブロックに既に出現している異なる自然数の個数を記録する.
では、クエリーでは、各ブロックがr[i]-l[i]+1=blo[i]を満たしているかどうかを確認し、上記の条件を満たしていない最初のブロックを見つけ、そのブロック内で暴力的に検索するだけでよい.
【問題解】
この問題は思考が少し難しいので、コンニャクはpopoQQQおじいさんの問題解を覗かざるを得なかった.
1~n間の自然数をルート番号nブロックに分割し、各ブロックは現在のブロックに既に出現している異なる自然数の個数を記録する.
では、クエリーでは、各ブロックがr[i]-l[i]+1=blo[i]を満たしているかどうかを確認し、上記の条件を満たしていない最初のブロックを見つけ、そのブロック内で暴力的に検索するだけでよい.
/*************
bzoj 3585
by chty
2016.11.29
*************/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "read"
#define MAXN 200010
#define up(i,j,n) for(int i=j;i<=n;i++)
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
struct node{int x,y,id;}q[MAXN];
int n,m,block,a[MAXN],ans[MAXN],vis[MAXN],blo[MAXN],l[MAXN],r[MAXN],belong[MAXN];
bool cmp(node a,node b) {return a.x/block==b.x/block?a.yn) return;
if(!vis[x]) blo[belong[x]]++;
vis[x]+=v;
if(!vis[x]) blo[belong[x]]--;
}
int query(){
if(!vis[0]) return 0;
int i;
for(i=1;l[i];i++) if(r[i]-l[i]+1!=blo[i]) break;
int temp=i;
up(i,l[temp],r[temp]) if(!vis[i]) return i;
return n;
}
void init(){
n=read(); m=read(); block=(int)sqrt(n*1.0);
up(i,1,n) a[i]=read();
up(i,1,m) q[i].x=read(),q[i].y=read(),q[i].id=i;
for(int i=1;(i-1)*block+1<=n;i++) l[i]=(i-1)*block+1,r[i]=min(i*block,n);
up(i,1,n) belong[i]=(i-1)/block+1;
}
void solve(){
sort(q+1,q+m+1,cmp);
int l(1),r(0);
up(i,1,m){
while(q[i].y>r) updata(a[++r],1);
while(q[i].yl) updata(a[l++],-1);
while(q[i].x