제출 #1272347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272347		thuhienne	Swap Swap Sort (CCO21_day1problem1)	C++20	25 / 25	3263 ms	343300 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 = 700;
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