牛客练习赛135小柒的逆序对2
目录
牛客练习赛135——小柒的逆序对(2)
这里还得说一下，调换一个排列中任意两个不同的数，该排列的逆序数奇偶会改变
题目：
思路：
这道题的数据给的很大，如果我们用树状数组维护前缀和都没用，但是我们观察到英文字符只有26个，那我们可以开一个二维数组g[i][j]表示ij字符对有多少个
如何维护这个数组呢，其实也很简单，遍历s每个字符c，同时开一个数组储存26个字符
对于字符c，先遍历26个字符y，将g[y][c]加上y的个数，结束后再将c的数量加一
(对于这个维护，其实反过来遍历应该也是可以的)
那么提前维护好了字符对，接下来每次查找就容易多了
我们每次查找都直接暴力两层遍历，如果k的字典序大于j，那么答案就要加上g[k][j]（逆序对的定义）
代码：
#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#define ll long long
using namespace std;
int n, q;
string s;
string f;
int g[30][30];
int cnt[30];
int pos[30];
void solve()
{
cin >> n >> q;
cin >> s;
for (char c : s)
{
int idx = c - 'a';
for (int y = 0; y < 26; y++)
{
g[y][idx] += cnt[y];
}
cnt[idx]++;
}
for (int i = 0; i < q; i++)
{
cin >> f;
for (int y = 0; y < 26; y++)
pos[f[y] - 'a'] = y;
ll res = 0;
for (int j = 0; j < 26; j++)
{
for (int k = 0; k < 26; k++)
{
if (pos[k] > pos[j])
res += g[k][j];
}
}
cout << res << endl;
}
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}