BZOJ 4059: [CERC2012]Non-boring – [分治]

题目传送门(BZOJ)

题解 :

分治
考虑一段区间 (l, r), 若这个区间中有某个数字 x 使得它在整段区间中的出现次数为 1,
那么对于所有包含这个数字的子区间, 该数都有且仅有一次出现, 所以只需要分治它两边的区间即可
如果这个区间中没有这样的数, 那么这个区间不合法

求这样的一个数就是求某数上一次出现在 l 之前, 下一次出现在 r 之后, 我们先离散化一下, 然后用链表直接预处理出来这个即可
又由于这个数字不是恰好出现在区间中点, 故我们要从两侧同时向中点扫, 这样的复杂度一定是 O(2\times len_{short}) 的,
而 len_{short} 必然小于等于区间长度一半

这个思想似乎应该叫启发式分裂 ?
复杂度 O(T\times N\log N)
请注意, 由于数据组数可能很大, 不能用 memset 来清空数组

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 201000;
#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++
char buf[100000], *p1, *p2;
inline char gc() {
    char ch = nc();
    while(isspace(ch)) ch = nc();
    return ch;
}
inline int rd() {
    int x = 0, f = 1; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc();
    return x*f;
}
int T, n, a[N], v[N];
int L[N], R[N], H[N];
bool Solve(int l, int r) {
    if(l > r) return true;
    int mid = 0;
    for(int i = l; i <= (l+r) >> 1 && mid == 0; i ++ ) {
        if(L[i] < l && R[i] > r) mid = i;
        if(L[l+r-i] < l && R[l+r-i] > r) mid = l+r-i;
    }
    if(mid) return Solve(l, mid-1) && Solve(mid+1, r);
    return 0;
}
int main() {
    T = rd();
    while(T -- ) {
        n = rd();
        for(int i = 1; i <= n; i ++ ) v[i] = a[i] = rd(), H[i] = L[i] = 0, R[i] = n+1;
        sort(v+1, v+n+1);
        for(int i = 1; i <= n; i ++ ) a[i] = lower_bound(v+1, v+n+1, a[i])-v, L[i] = H[a[i]], R[L[i]] = i, H[a[i]] = i;
        if(Solve(1, n)) printf("non-");
        puts("boring");
    }
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<