[清华集训2017]小 Y 和地铁（神奇思路，搜索，剪枝，树状数组）

#includeusing namespace std;
typedef long long ll;
const int maxn=45;
#define FOR(i,a,b) for(int i=(a);i#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(ch‘0‘ || ch>‘9‘) f|=ch==‘-‘,ch=getchar();
    while(ch>=‘0‘ && ch‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return f?-x:x;
}
int t,n,m,tp[maxn],l[maxn],r[maxn],ans,sum,b[2][maxn];
inline void update(int id,int p,int v){
    while(pn){
        b[id][p]+=v;
        p+=p&-p;
    }
}
inline int query(int id,int p){
    int s=0;
    while(p){
        s+=b[id][p];
        p-=p&-p;
    }
    return s;
}
inline int query(int id,int l,int r){return query(id,r)-query(id,l-1);}
void dfs(int dep){
    if(sum>ans) return;
    if(dep>m) return void(ans=sum);
    int t1=query(0,l[dep],r[dep]),t2=query(0,r[dep],n),t3=query(1,l[dep],r[dep]),t4=query(1,r[dep],n);
    update(0,r[dep],1);
    sum+=min(t1,t2+t3+t4);
    dfs(dep+1);
    sum-=min(t1,t2+t3+t4);
    update(0,r[dep],-1);
    update(1,r[dep],1);
    sum+=min(t3,t1+t2+t4);
    dfs(dep+1);
    sum-=min(t3,t1+t2+t4);
    update(1,r[dep],-1);
}
int main(){
    t=read();
    while(t--){
        m=0;ans=1e9;
        n=read();
        FOR(i,1,n) tp[i]=read();
        FOR(i,1,n) FOR(j,i+1,n) if(tp[i]==tp[j]) l[++m]=i,r[m]=j;
        dfs(1);
        printf("%d\n",ans);
    }
}