BZOJ4059: [Cerc2012]Non-boring sequences

선분 수
제목 전송 문
이 문 제 는 바로 계발 식 분 치 이지 만 선분 수 도 할 수 있다.
이 문제 와 비슷 하 다. 똑 같이 n x t [i] nxt[i] nxt [i] nxt[i] a [i] [i] a [i] [i] [i]] 다음 에 나타 날 위 치 를 매 거 왼쪽 점, 취소 [i, n x t [i] - 1] [i, nxt [i]] - 1 [i, nxt [i] - 1], [n x t [i], n x t [n x t [i]] - 1] [nx [i]] - 1] [nxt [nxt [nxt [] - 1] [nxt [nxt], nxt [nxt]] - 1], [nxt [nxt [nxt]] - 1] - 1], [i] - 1] 를 더 하고 [i, n x t t [n x t t [[i, n] [i, n]완전히 덮어 쓸 지 여부 입 니 다.
코드:

#include
#include
#include
#include
#define N 200005
#define F inline
using namespace std;
struct tree{ int l,r,f,mn; }t[N<<2];
int q,n,a[N],b[N],nxt[N],lst[N];
F char readc(){
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	return l==r?EOF:*l++;
}
F int _read(){
	int x=0; char ch=readc();
	while (!isdigit(ch)) ch=readc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
	return x;
}
F void pshp(int x){ t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn); }
F void pshd(int x){
	if (!t[x].f) return; int k=t[x].f; t[x].f=0;
	t[x<<1].f+=k,t[x<<1].mn+=k,t[x<<1|1].f+=k,t[x<<1|1].mn+=k;
}
F void build(int x,int l,int r){
	t[x]=(tree){l,r,0,0};
	if (l==r) return; int mid=l+r>>1;
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
F void mdfy(int x,int l,int r,int w){
	if (t[x].l>r||t[x].r<l) return;
	if (t[x].l>=l&&t[x].r<=r)
		return t[x].f+=w,void(t[x].mn+=w);
	pshd(x),mdfy(x<<1,l,r,w),mdfy(x<<1|1,l,r,w),pshp(x);
}
F int srch(int x,int l,int r){
	if (t[x].l>r||t[x].r<l) return 1e9;
	if (t[x].l>=l&&t[x].r<=r) return t[x].mn;
	return pshd(x),min(srch(x<<1,l,r),srch(x<<1|1,l,r));
}
int main(){
	for (q=_read();q;q--){
		n=_read(),build(1,1,n); bool f=true;
		for (int i=1;i<=n;i++) b[i]=a[i]=_read(),lst[i]=n+1;
		sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
		for (int i=n;i;i--){
			a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
			nxt[i]=lst[a[i]],lst[a[i]]=i;
		}
		for (int i=1;i<=n;i++)
			if (lst[a[i]]==i) mdfy(1,i,nxt[i]-1,1);
		for (int i=1;i<n;i++){
			if (!srch(1,i,n)){ f=false; break; }
			mdfy(1,i,nxt[i]-1,-1);
			if (nxt[nxt[i]]) mdfy(1,nxt[i],nxt[nxt[i]]-1,1);
		}
		puts(f?"non-boring":"boring");
	}
	return 0;
}