TLE 求调
查看原帖
TLE 求调
945788
Hsj2022楼主2025/6/27 17:25
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=2e5+10;
int n;
int a[N];
int last[N];//last[i]记录数值i上一次出现的位置
int L[N],R[N];//对于i位置的最长non-boring区间
struct Node{
    int x,l,r,w;
    bool operator <(const Node &t)const{
        return x<t.x||x==t.x&&w==1;//满足先加后减
    }
}seq[N*2];
struct ST{
    int l,r;
    int cnt,len;//覆盖次数和[l,r]中的覆盖长度
}tr[N*4];
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
void init(){
    for(int i=1;i<=n;i++) L[i]=R[i]=0;
}
void pushup(int u){
    if(tr[u].cnt) tr[u].len=tr[u].r-tr[u].l+1;
    else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    else tr[u].len=0;
}
void build(int u,int l,int r){
    tr[u]={l,r,0,0};
    if(l==r) tr[u]={l,r,0,0};
    else{
        int mid=tr[u].l+tr[u].r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}
void modify(int u,int l,int r,int w){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].cnt+=w;
        pushup(u);
    }
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,w);
        if(r>mid) modify(u<<1|1,l,r,w);
        pushup(u);
    }
}
ll ScaningLine(){
    ll ans=0;
    sort(seq+1,seq+2*n+1);
    build(1,1,n);
    modify(1,seq[1].l,seq[1].r,seq[1].w);
    for(int i=2;i<=2*n;i++){
        ans+=(ll)(seq[i].x-seq[i-1].x)*tr[1].len;
        modify(1,seq[i].l,seq[i].r,seq[i].w);
    }
    return ans;
}
signed main(){
    int T=read();
    while(T--){
        init();
        n=read();
        vector<int> lsh;
        for(int i=1;i<=n;i++){
            a[i]=read();
            lsh.push_back(a[i]);
        }
        sort(lsh.begin(),lsh.end());
        lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin();
            if(last[a[i]]) R[last[a[i]]]=i-1;
            L[i]=last[a[i]]+1;
            last[a[i]]=i;
        }
        for(int i=0;i<lsh.size();i++){
            R[last[i]]=n;
            last[i]=0;
        }
        for(int i=1;i<=n;i++){
            seq[i]={L[i],i,R[i],1};
            seq[i+n]={i+1,i,R[i],-1};
        }
        if(ScaningLine()==(ll)n*(n+1)/2) puts("non-boring");
        else puts("boring");
    }
    return 0;
}
2025/6/27 17:25
加载中...