loj2323|luogu4005|清华集训|小Y和地铁

thkkkdalao太强了!

我们发现一个只有四种情况,在想一想:

两个方框内的两种情况对后面的影响完全相同。

  • 第一个

    破坏了1-3没有破坏2-4

  • 第二个

    没有破坏1-3破坏了2-4

    ​然后我们分两种情况:第一个、第二个,然后因为同种对后面影响相同,对前面都没影响,所以只需要比较前面对当前位置的影响,取较低值就好了。

    ​影响可以用树状数组维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#define N 110
int t,n,a[N],l[N],r[N],cnt,ans;
int bitup[N],bitdown[N];
void add(int *a,int x,int w)
{
while(x<=n)
{
a[x]+=w;
x+=(x&(-x));
}
}
int query(int *a,int x)
{
int r=0;
while(x)
{
r+=a[x];
x-=(x&(-x));
}
return r;
}
#define inf (1<<20)
void dfs(int x,int w)
{
if(w>=ans)
return;
if(x>cnt)
{
ans=w;
return;
}
int ww=0;
//up
ww=w+min(query(bitup,r[x])-query(bitup,l[x]-1),
query(bitdown,n)-query(bitdown,l[x]-1)
+query(bitup,n)-query(bitup,r[x]-1));
add(bitup,r[x],1);
dfs(x+1,ww);
add(bitup,r[x],-1);
//down
ww=w+min(query(bitdown,r[x])-query(bitdown,l[x]-1),
query(bitup,n)-query(bitup,l[x]-1)
+query(bitdown,n)-query(bitdown,r[x]-1));
add(bitdown,r[x],1);
dfs(x+1,ww);
add(bitdown,r[x],-1);
}
int main()
{
t=read();
while(t--)
{
n=read();
fr(i,1,n)
a[i]=read();
cnt=0;
fr(i,1,n)
fr(j,i+1,n)
if(a[i]==a[j])
{
cnt++;
l[cnt]=i;
r[cnt]=j;
}//处理出每对点
ans=inf;
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}