Solution CF1430E String Reversal
题目大意：给定一个字符串，每次操作可以交换两个相邻字符，询问最少多少次操作可以让字符串翻转
树状数组
分析：
首先考虑一个 (n^2) 算法，我们找出字符串与翻转串不同的位置，往后找到第一个需要交换的位置，修改字符串并且统计答案
rev = str;
reverse(rev.begin(),rev.end());
for(int i = 0;i < str.size();i++){
if(str[i] != rev[i]){
for(int j = i + 1;j < str.size();j++)
if(str[j] == rev[i]){
for(int k = j;k >= i + 1;k--)
str[k] = str[k - 1];
str[i] = rev[i];
ans += j - i;
break;
}
}
}
这样无法通过，需要优化，对于每种字符单独考虑，维护每个字符出现的位置，我们需要支持的操作：
- 1.删除第一个数
- 2.将小于某个阈值的所有数全部加 (1)
- 3.询问第一个数
可以通过差分，然后树状数组维护。位置单调，因而 (2) 操作可以二分。
应该是(nlog^2n)带个(26)常数，跑的贼慢
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 100;
struct BIT{
int f[maxn];
inline int lowbit(int x){return x & (-x);}
inline void add(int pos,int x){
while(pos < maxn){
f[pos] += x;
pos += lowbit(pos);
}
}
inline int query(int pos){
int res = 0;
while(pos){
res += f[pos];
pos -= lowbit(pos);
}
return res;
}
};
struct node{
int val[maxn],beg = 1,end = 0;
BIT bit;
inline int top(){return val[beg] + bit.query(beg);}
inline int query(int pos){return val[pos] + bit.query(pos);}
inline void push(int x){
val[++end] = x;
}
inline void pop(){
beg++;
}
inline void modify(int limit){
int l = beg,r = end,ans = -1;
if(!end)return;
while(l <= r){
int mid = (l + r) >> 1;
if(bit.query(mid) + val[mid] < limit)ans = mid,l = mid + 1;
else r = mid - 1;
}
if(ans == -1)return;
bit.add(beg,1);
bit.add(ans + 1,-1);
}
}val[26];
inline int idx(char c){return c - 'a';}
int n;
long long ans;
string str,rev;
int main(){
ios::sync_with_stdio(false);
cin >> n;
cin >> str;
rev = str;
reverse(rev.begin(),rev.end());
for(int i = 0;i < n;i++)
val[idx(str[i])].push(i);
for(int i = 0;i < n;i++){
int pos = val[idx(rev[i])].top();
ans += pos - i;
val[idx(rev[i])].pop();
for(int j = 0;j < 26;j++)
if(j != idx(rev[i]))val[j].modify(pos);
}
cout << ans << '
';
return 0;
}
有个更妙的做法，从逆序对的角度来考虑（可能我还是太naive了）
假设原串每个字符的编号为 (1-n)，然后我们将反串每个字符的位置按升序求出来，我们就求出了最优情况下每个字符应该变换到的位置，比如第一个样例aaaza对应的序列应该是 (1,3,4,2,5)，交换相邻两数，使得数列有序，这个十分经典，答案即为这个序列的逆序对
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
namespace bit{
int f[maxn];
inline int lowbit(int x){return x & (-x);}
inline void add(int pos,int x){
while(pos < maxn){
f[pos] += x;
pos += lowbit(pos);
}
}
inline int query(int pos){
int res = 0;
while(pos){
res += f[pos];
pos -= lowbit(pos);
}
return res;
}
}
inline int idx(char c){return c - 'a';}
vector<int> vec[26];
int n,val[maxn],beg[maxn];
long long ans;
char str[maxn],rev[maxn];
int main(){
scanf("%d",&n);
scanf("%s",str + 1);
for(int i = 1;i <= n;i++)rev[i] = str[i];
reverse(rev + 1,rev + 1 + n);
for(int i = 1;i <= n;i++)
vec[idx(rev[i])].push_back(i);
for(int i = 1;i <= n;i++)
val[i] = vec[idx(str[i])][beg[idx(str[i])]++];
for(int i = n;i >= 1;i--)
ans += bit::query(val[i]),bit::add(val[i],1);
printf("%lld
",ans);
return 0;
}