[CF1526D] Kill Anton（逆序对，搜索）

题面

A

N

T

O

N

\rm ANTON

ANTON 的基因由

A

,

N

,

T

,

O

\rm A,N,T,O

A,N,T,O 四种碱基排列组成。

A

N

T

O

N

\rm ANTON

ANTON 的身体很智能，一旦发现基因序列被改变了，就会通过尽量少的次数交换相邻两个碱基，来还原回开始的基因序列。

现在给出

A

N

T

O

N

\rm ANTON

ANTON 的基因序列，长为

N

N

N ，求一个打乱后的该序列，满足还原时需要交换操作最少次数最多，输出任意一个符合条件的序列。

1

≤

N

≤

1

0

5

1\leq N \leq10^5

1≤N≤105.

我们先考虑最少操作次数怎么求。根据做题经验，有一个贪心思路：把相同类型的碱基不交叉地一一配对，然后把每个初始位置的目标位置拿出来组成一个序列（因此这应该是个1~N的排列），最小操作次数即该排列的逆序对数。

那么，我们不妨把打乱后的序列也这样一一对应回去，每个位置上记录初始位置的编号。容易发现，对于同一种碱基的所有位置，初始位置的编号一定是单增的。在满足这个条件的情况下，我们可以想想怎么最大化逆序对数。

这里有一个结论：一定存在一种逆序对最多的方案，满足同种碱基都相邻。

A……A

那么，由于只有四种碱基，全排列有

M

!

=

4

!

=

24

M!=4!=24

M!=4!=24 种，最终的序列也只有这么多种，其中一定存在一个答案序列，我们暴力枚举找它。复杂度

O

(

M

!

n

log

⁡

n

)

O(M!n\log n)

O(M!nlogn)。

还有一种

O

(

n

)

O(n)

O(n) 的做法。交换次数不一定要求逆序对，还可以求初始与目标的距离。由于我们知道同种碱基要相邻，可以通过预处理前缀和等方式，快速判断每种碱基段在某个位置对答案贡献为多少，这样一来，枚举全排列时就不用每次

O

(

n

)

O(n)

O(n) 求答案，而是常数时间。总时间复杂度就主要只有输入和预处理了。

O

(

24

n

log

⁡

n

)

O(24n\log n)

O(24nlogn)

#include<set>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 400005

#define ENDL putchar(‘\n’)

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

#define INF 0x3f3f3f3f

LL read() {


LL f = 1,x = 0;char s = getchar();<br/>
while(s &lt; &#39;0&#39; || s &gt; &#39;9&#39;) {if(s==&#39;-&#39;)f = -f;s = getchar();}<br/>
while(s &gt;= &#39;0&#39; &amp;&amp; s &lt;= &#39;9&#39;) {x=x*10+(s-&#39;0&#39;);s = getchar();}<br/>
return f * x;<br/>


}

int n,m,i,j,s,o,k;

char s0[10] = “ANTO”;

char ss[MAXN];

int c[MAXN];

void addc(int x,int y){while(x&lt;=n)c[x]+=y,x+=lowbit(x);}

int sum(int x){int s=0;while(x&gt;0)s+=c[x],x-=lowbit(x);return s;}

void INIT() {for(int i = 1;i &lt;= n;i ++) c[i] = 0;}

LL as = 0,CN;

char D[MAXN],e[MAXN];

void ADD(int x) {


D[CN --] = ss[x];<br/>
as += sum(x-1); addc(x,1);<br/>
return ;<br/>


}

int main() {


int T = read();<br/>
while(T --) {<br/>
	scanf(&#34;%s&#34;,ss + 1);<br/>
	n = strlen(ss + 1);<br/>
	for(int i = 1;i &lt;= n;i ++) e[i] = ss[i];<br/>
	LL ans = -1;<br/>
	for(int a=0;a&lt;4;a++) {<br/>
		for(int b=0;b&lt;4;b++) if(b!=a) {<br/>
			for(int c=0;c&lt;4;c++) if(c!=a&amp;&amp;c!=b) {<br/>
				for(int d=0;d&lt;4;d++) if(d!=a&amp;&amp;d!=b&amp;&amp;d!=c) {<br/>
					INIT();<br/>
					CN = n;as = 0;<br/>
					for(int i = n;i &gt; 0;i --) if(ss[i] == s0[d]) ADD(i);<br/>
					for(int i = n;i &gt; 0;i --) if(ss[i] == s0[c]) ADD(i);<br/>
					for(int i = n;i &gt; 0;i --) if(ss[i] == s0[b]) ADD(i);<br/>
					for(int i = n;i &gt; 0;i --) if(ss[i] == s0[a]) ADD(i);<br/>
					if(as &gt; ans) {<br/>
						for(int i = 1;i &lt;= n;i ++) e[i] = D[i];<br/>
						ans = as;<br/>
					}<br/>
				}<br/>
			}<br/>
		}<br/>
	}<br/>
	for(int i = 1;i &lt;= n;i ++) putchar(e[i]);ENDL;<br/>
}<br/>
return 0;<br/>


}