【题解】[CCO2021] Swap Swap Sort

本文主要是介绍【题解】[CCO2021] Swap Swap Sort，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于初始排列，就是求原序列的逆序对数。

对于逆序对我们可以拆开来算，用 \([i,j]\) 表示满足 \(a_u =i,a_v=j,i>j\) 二元组 \((u,v)\) 个数。

那么初始答案可以表示为 \(\sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k}[i,j]\)。

推导之后可以得到，对于一次交换，令交换的两个数为 \(x,y\)，我们只用在上一次答案的基础上加上 \(2\times[x,y] - c _x\times c_y\)，其中 \(c_i\) 表示 \(i\) 在原序列中出现的次数。

现在我们只用求 \([x,y]\)​，这个玩意本质上也是求逆序对，考虑根号分治，对于 \(c_x, c_y\le \sqrt n\) 的直接爆算，其余的离线后对整个原序列扫一遍统计答案。

由于 \(q\) 远大于 \(n\) ，我们令 \(lim\) 表示对于 \(c_x, c_y\le lim\) 的 \([x,y]\) 进行爆算，解方程 \(q\times lim = \frac{n^2}{lim}\)，解的 \(lim = 100\) 时最优。

/*
    Author : SharpnessV
    Right Output ! & Accepted !
*/
#include<bits/stdc++.h>
//#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)
#define go(i, x) for(auto i : x)

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ze(p) memset(p, 0, sizeof(p))
#define mem(p, x) memset(p, x, sizeof(p))
#define YES puts("YES")
#define NO puts("NO")
#define si(x) (int)(x).size()
#define db cerr
#define pc putchar
#define el putchar('\n')

using namespace std;
const double eps = 1e-15, pi = 3.1415926535897932385;
typedef long long LL;
typedef pair<int,int> Pr;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}, inf = 0x7fffffff;

//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x = 0;bool f = 1;char ch = getchar();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = getchar();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    if(f)return x;return -x;
}
inline LL Read(){
    LL x = 0;bool f = 1;char ch = getchar();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = getchar();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    if(f)return x;return -x;
}
int gcd(int x,int y){return y ? gcd(y, x % y) : x;}
int lcm(int x,int y){return x / gcd(x, y) * y;}
#define P 1000000007
//#define P 998244353
#define bas 229
inline void ad(int &x, int y){x += y; if(x >= P) x -= P;}
inline void su(int &x, int y){x -= y; if(x < 0) x += P;}
inline void cmn(int &x,int y){if(y < x) x = y;}
inline void cmx(int &x,int y){if(y > x) x = y;}
inline void cmn(LL &x, LL y){if(y < x) x = y;}
inline void cmx(LL &x, LL y){if(y > x) x = y;}

int Pow(int x, int y){
	if(y < 0)return Pow(Pow(x, P - 2), -y);
	int now = 1 ;
	for(;y;y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}
#define N 100005
#define M 1000005
int n, m, q, a[N], c[N], u[M], p[N], b[N];LL ans[M], s[N], sum;
vector<Pr>e[N];vector<int>f[N];
const int lim = 100;
int calc(int x,int y){
	int sx = si(f[x]), sy = si(f[y]), cur = 0, j = 1;
	rp(i, sy){
		while(j <= sx && f[x][j - 1] < f[y][i - 1])j++;
		cur += j - 1;
	}
	return cur;
}
void solve(int x){
	memset(s, 0, sizeof(s));
	int cnt = 0;
	rp(i, n){
		if(a[i] == x)cnt++;
		else s[a[i]] += cnt;
	}
	go(w, e[x])ans[w.se] = s[w.fi];
}
void msort(int l, int r){
	if(l == r)return;
	int mid = (l + r) >> 1;
	msort(l, mid), msort(mid + 1, r);
	int top = 0, j = l;
	rep(i, mid + 1, r){
		while(j <= mid && a[j] > a[i])b[++top] = a[j++];
		sum += j - l, b[++top] = a[i];
	}
	while(j <= mid)b[++top] = a[j++];
	rep(i, l, r)a[i] = b[i - l + 1];
}
int main(){
	//int T = read();while(T--)solve();
	n = read(), m = read(), q = read();
	rp(i, n)c[a[i] = read()] ++ , f[a[i]].pb(i);
	rp(i, m)p[i] = i;
	rp(i, q){
		u[i] = read();
		int x = p[u[i]], y = p[u[i] + 1];
		swap(p[u[i]], p[u[i] + 1]);
		if(c[x] < c[y])swap(x, y);
		if(c[x] > lim)e[x].pb(mp(y, i));
		else ans[i] = calc(x, y);
	}
	rp(i, m)if(si(e[i]))solve(i);
	msort(1, n);
	//cout << "ss " << sum << endl;
	rp(i, n)p[i] = i;
	rp(i, q){
		int x = p[u[i]], y = p[u[i] + 1];
		swap(p[u[i]], p[u[i] + 1]);
		if(c[x] < c[y])ans[i] = 1LL * c[x] * c[y] - ans[i];
		//cout << "Ss " << x << " " << y << " " << ans[i] << " " << c[x] << " " << c[y] << endl;
		sum += ans[i] * 2 - 1LL * c[x] * c[y];
		printf("%lld\n", sum);
	}
	return 0;
}

这篇关于【题解】[CCO2021] Swap Swap Sort的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！