BZOJ4059[Cerc2012]Non-boring sequences（扫描线/分治）

这题正解应该是扫描线，就是发现DP的区间在两个维度都为连续段，于是可以直接扫描线。但不幸的是，扫描线常数过大，无法通过本题。

考虑分治。对于分治区间[l,r]，可以记录pre和nxt表示其前/后一次出现的位置，每当遇到一个出现次数=1的数，可以直接把区间分为两半判断，反之则丢掉这个数，而仅会分治一次，且掐断地方是先判两边，复杂度近似O(nlogn)。

实在太坑了，其实是一道练习扫描线的好题qwq

#include<cstdio>

#include<algorithm>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int N=2e5+;

typedef long long ll;

struct line{int x,l,r,v;}c[N<<];

int n,m,a[N],b[N],L[N],R[N],pre[N],sum[N<<],cnt[N<<];

bool cmp(line a,line b){return a.x<b.x;}

void insert(int a1,int a2,int b1,int b2)

{c[++m]=(line){a1,b1,b2,},c[++m]=(line){a2+,b1,b2,-};}

void build(int l,int r,int rt)

{

    sum[rt]=cnt[rt]=;

    if(l==r)return;

    int mid=l+r>>;

    build(lson),build(rson);

}

void pushup(int l,int r,int rt)

{

    if(cnt[rt])sum[rt]=r-l+;

    else if(l==r)sum[rt]=;

    else sum[rt]=sum[rt<<]+sum[rt<<|];

}

void update(int L,int R,int v,int l,int r,int rt)

{

    if(L<=l&&r<=R){cnt[rt]+=v,pushup(l,r,rt);return;}

    int mid=l+r>>;

    if(L<=mid)update(L,R,v,lson);

    if(R>mid)update(L,R,v,rson);

    pushup(l,r,rt);

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        build(,n,);

        for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

        sort(b+,b+n+);

        m=unique(b+,b+n+)-b-;

        for(int i=;i<=n;i++)a[i]=lower_bound(b+,b+m+,a[i])-b;

        m=;

        for(int i=;i<=n;i++)pre[i]=;

        for(int i=;i<=n;i++)L[i]=pre[a[i]],pre[a[i]]=i;

        for(int i=;i<=n;i++)pre[i]=n+;

        for(int i=n;i;i--)R[i]=pre[a[i]],pre[a[i]]=i;

        for(int i=;i<=n;i++)insert(L[i]+,i,i,R[i]-);

        sort(c+,c+m+,cmp);

        ll ans=;

        for(int i=,p=;i<=n;i++)

        {

            while(p<m&&c[p+].x==i)p++,update(c[p].l,c[p].r,c[p].v,,n,);

            ans+=sum[];

        }

        if(ans==1ll*n*(n+)/)puts("non-boring");

        else puts("boring");

    }

}

扫描线的TLE代码

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

const int N=2e5+;

int n,m,a[N],pre[N],nxt[N];

map<int,int>lst;

bool solve(int l,int r)

{

    if(l>=r)return ;

    int p=l,q=r;

    while(p<=q)

    {

        if(pre[p]<l&&nxt[p]>r)return solve(l,p-)&&solve(p+,r);p++;

        if(pre[q]<l&&nxt[q]>r)return solve(l,q-)&&solve(q+,r);q--;

    }

    return ;

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        lst.clear();

        scanf("%d",&n);

        for(int i=,pos;i<=n;i++)scanf("%d",&a[i]),pos=lst[a[i]],nxt[pos]=i,pre[i]=pos,lst[a[i]]=i;

        for(int i=;i<=n;i++)nxt[lst[a[i]]]=n+;

        if(solve(,n))puts("non-boring");else puts("boring");

    }

}

分治的AC代码