Submission #1272346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272346		thuhienne	Swap Swap Sort (CCO21_day1problem1)	C++20	25 / 25	2076 ms	443164 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define count __count__

int fen[100009];
void update(int pos,int val) {
	for (;pos <= 100003;pos += (pos & -pos)) fen[pos] += val;
}
int get(int pos) {
	int ret = 0;
	for (;pos;pos -= (pos & -pos)) ret += fen[pos];
	return ret;
}

const int BLOCK = 1000;
const int MAX = 100000;

int n,k,q,arr[MAX + 9];
int perm[MAX + 9],count[MAX + 9];

int cnt = 0;
struct {
	int freq[MAX + 9],count[BLOCK + 1],countpair[BLOCK + 1][BLOCK + 1];
	//freq -> gia tri trong block
	//countpair i j = so cap trong block ma i truoc j
} block[MAX/BLOCK + 9];
int maxblock = 0;

void preprocess() {
	for (int id = 0;;id ++) {
		int l = max(1,id * BLOCK);
		int r = min(n,(id + 1) * BLOCK - 1);
		cnt = 0;
		for (int i = r;i >= l;i--) {
			int val = arr[i];
			if (!block[id].freq[val]) block[id].freq[val] = ++cnt;
			int pos = block[id].freq[val];
			block[id].count[pos]++;
			for (int d = 1;d <= cnt;d++) if (d != pos) {
				block[id].countpair[pos][d] += block[id].count[d];
			}
		}
		if (r == n) {
			maxblock = id;
			break;
		}
	}
}

long long res = 0;

void process(int pos) {
	int d1 = perm[pos],d2 = perm[pos + 1];
	long long total = 1ll * count[d1] * count[d2],find = 0;
	//dem so cap (d1,d2)
	int countd1 = 0;
	for (int id = 0;id <= maxblock;id++) {
		int pos1 = block[id].freq[d1],pos2 = block[id].freq[d2];
		
		find += 1ll * countd1 * block[id].count[pos2] + 
				block[id].countpair[pos1][pos2];
		
		countd1 += block[id].count[pos1];
	}
	res = res - total + 2*find;
	cout << res << '\n';
	swap(perm[pos],perm[pos + 1]);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n >> k >> q;
	for (int i = 1;i <= n;i++) {
		cin >> arr[i];
		count[arr[i]]++;
	}
	for (int i = 1;i <= k;i++) perm[i] = i;
	for (int i = n;i >= 1;i--) {
		res += get(arr[i] - 1);
		update(arr[i],1);
	}
	preprocess();
	while (q--) {
		int pos;cin >> pos;
		process(pos);
	}
}

/*
  Thuong em khi mua thu
  Thuong em sang mua ha
  Thuong em bang qua mua dong,gui gio xuan om em vao long
  Thuong em bao mua mua
  Tham thuong luon bao mua nang
  Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14