Non-boring sequences(分治) - boring, Non, Sequences, 分治

We were afraid of making this question too boring, so we decided to make this question super short. A sequence is called not boring, only if there is a unique number in each successive subsequence, that is, at least one number in each subsequence appears only once. Given a sequence of integers, please judge if it is not boring.

Input

A positive integer T in the first line indicates that there are T groups of data. A positive integer n in the first row of each group of data indicates the length of the sequence, 1 <= n <= 200000. The next line of n non-negative integers not exceeding 10^9 represents this sequence.

Output

For each set of data, output one line, output “non-boring” to indicate that the sequence is not boring, output “boring” Indicates that this sequence is boring.

Sample Input

Sample Output

< div class="content">

non-boring
boring
non-boring
boring

solution:
A type of interval maximum/minimum problem , It can be found that as long as the interval of a certain position is crossed, it must be legal.
Then we can divide and conquer from both sides of this position, and then ensure the complexity, look for pos from both sides
code:

#include
#define lll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int N = 3e5+10;
int n;
int a[N];
lll ans=0;
int L[N],R[N];
int pos[N];
vector v;

void dfs(int l,int r)
{

    if(l>r)return;
    int ll=l,rr=r;
    for(int i=l;i<=r;i++)
    {
        if(i&1)
        {
            if(L[ll]r)
            {
                ans += 1ll*(ll-l+1)*(r-ll+1);
                dfs(l,ll-1);dfs(ll+1,r);return;
            }
            ll++;
        }else
        {
          if(L[rr]r)
            {ans += 1ll*(rr-l+1)*(r-rr+1);
                dfs(l,rr-1);dfs(rr+1,r);return;
            }
            rr--;
        }
    }

}
int main()
{
    int T;cin>>T;
    while(T--)
    {
        cin>>n;rep(i,1,n)scanf("%d",a+i);
        v.clear();
        rep(i,1,n)v.push_back(a[i]);
        sort(all(v));v.erase(unique(all(v)),v.end());
        rep(i,1,n)a[i]=lower_bound(all(v),a[i])-v.begin()+1;
       rep(i,1,n)pos[i]=0;
        rep(i,1,n)
        {
            if(!pos[a[i]])L[i]=0;
            else L[i]=pos[a[i]]+1;
            pos[a[i]]=i;
        }
        rep(i,1,n)pos[i]=0;

        for(int i=n;i;i--)
        {
            if(!pos[a[i]])R[i]=n+1;
            else R[i]=pos[a[i]]-1;
            pos[a[i]]=i;
        }
        ans=0;dfs(1,n);
        ans==1ll*n*(n+1)/2?puts("non-boring"): puts("boring");
    }

    return 0;
}

For each set of data, output one line. The output “non-boring” indicates that the sequence is not boring, and the output “boring” indicates that the sequence is boring.

non-boring
boring
non-boring
boring

solution:
A type of interval maximum/minimum problem, you can find that as long as the interval across a certain position must be legal
then we divide and conquer from this position. , And then to ensure the complexity, look for pos
code from both sides:

#include #define lll long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define all(x) (x).begin(),(x).end() using namespace std; const int N = 3e5+10; int n; int a[N]; lll ans=0; int L[N],R[N]; int pos[N]; vector v; void dfs(int l,int r) { if(l>r)return; int ll=l,rr=r; for(int i=l;i<=r;i++) { if(i&1) { if(L[ll]r) { ans += 1ll*(ll-l+1)*(r-ll+1); dfs(l,ll-1);dfs(ll+1,r);return; } ll++; }else { if(L[rr]r) {ans += 1ll*(rr-l+1)*(r-rr+1); dfs(l,rr-1);dfs(rr+1,r);return; } rr--; } } } int main() { int T;cin>>T; while(T--) { cin>>n;rep(i,1,n)scanf("%d",a+i); v.clear(); rep(i,1,n)v.push_back(a[i]); sort(all(v));v.erase(unique(all(v)),v.end()); rep(i,1,n)a[i]=lower_bound(all(v),a[i])-v.begin()+1; rep(i,1,n)pos[i]=0; rep(i,1,n) { if(!pos[a[i]])L[i]=0; else L[i]=pos[a[i]]+1; pos[a[i]]=i; } rep(i,1,n)pos[i]=0; for(int i=n;i;i--) { if(!pos[a[i]])R[i]=n+1; else R[i]=pos[a[i]]-1; pos[a[i]]=i; } ans=0;dfs(1,n); ans==1ll*n*(n+1)/2?puts("non-boring"): puts("boring"); } return 0; }

Leave a Comment Cancel reply