样例不过求调
查看原帖
样例不过求调
999274
CNS_5t0_0r2楼主2025/1/22 10:40
#include<iostream>
#include<algorithm>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
inline char gc(){
    const int SIZE = 1 << 16;
    static char buf[SIZE],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,SIZE,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
const int N = 2e5 + 9;
int n;
int seq[N];
int pre[N],nex[N],last[N];

struct rect{
	int x1,y1,x2,y2;
} a[N];
int cnt;
struct node{
	int x,y1,y2,k;
} seg[N << 1];
bool cmp(node elem1,node elem2){
	return elem1.x < elem2.x;
}
int tmp0[N],top0;
int tmp[N << 1],top;
long long ans;
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
struct seg_tree{
	int cnt,len;
} t[N << 4];
void push_up(int root,int l,int r){
	if(t[root].cnt > 0)
		t[root].len = tmp[r + 1] - tmp[l];
	else
		t[root].len = t[lchild].len + t[rchild].len;
}
void update(int root,int l,int r,int L,int R,int k){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		t[root].cnt += k;
		push_up(root,l,r);
		return;
	}
	update(lchild,l,mid,L,R,k);
	update(rchild,mid + 1,r,L,R,k);
	push_up(root,l,r);
}
void clear_tree(int root,int l,int r){
	if(l == r){
		t[root].cnt = t[root].len = 0;
		return;
	}
	clear_tree(lchild,l,mid);
	clear_tree(rchild,mid + 1,r);
}
void clear(){
	if(top)
		clear_tree(1,1,top);
	ans = top0 = top = cnt = 0;
}
void solve(){
	clear();
	n = read();
	for(int i = 1;i <= n;i++){
		seq[i] = read();
	    tmp0[++top0] = seq[i];
	}
	sort(tmp0 + 1,tmp0 + top0 + 1);
	top0 = unique(tmp0 + 1,tmp0 + top0 + 1) - tmp0 - 1;
	for(int i = 1;i <= n;i++)
		seq[i] = lower_bound(tmp0 + 1,tmp + top0 + 1,seq[i]) - tmp0;
	for(int i = 1;i <= top0;i++)
		last[i] = 0;
	for(int i = 1;i <= n;i++){
		pre[i] = last[seq[i]];
		last[seq[i]] = i;
	}
	for(int i = 1;i <= top0;i++)
		last[i] = 0;
	for(int i = n;i >= 1;i--){
		nex[i] = last[seq[i]];
		last[seq[i]] = i;
	}
	for(int i = 1;i <= n;i++){
		a[i] = (rect){pre[i] + 1,i,i,nex[i] - 1};
		tmp[++top] = i;
		tmp[++top] = nex[i] - 1;
	}
	sort(tmp + 1,tmp + top + 1);
	top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
	for(int i = 1;i <= n;i++){
		a[i].y1 = lower_bound(tmp + 1,tmp + top + 1,a[i].y1) - tmp;
		a[i].y2 = lower_bound(tmp + 1,tmp + top + 1,a[i].y2) - tmp;
		seg[++cnt] = (node){a[i].x1,a[i].y1,a[i].y2,1};
		seg[++cnt] = (node){a[i].x2,a[i].y1,a[i].y2,-1};
	}
	sort(seg + 1,seg + cnt + 1,cmp);
	for(int i = 1;i <= cnt;i++){
		int l = seg[i].y1,r = seg[i].y2,k = seg[i].k;
		int x = seg[i].x,x2 = seg[i + 1].x;
		update(1,1,top,l,r - 1,k);
		ans += 1ll * (x2 - x) * t[1].len;
	}
	cout << (ans == ((1ll * n * (n + 1) >> 1)) ? "non-boring" : "boring") << '\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	int T = read();
	while(T--)
		solve();
	return 0;
}
2025/1/22 10:40
加载中...