제출 #59597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59597		IvanC	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	240 ms	10724 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define LSOne(S) (S & (-S))
using namespace std;

const int MAXN = 5*1e5 + 10;
typedef struct node* pnode;

struct node{

	pnode l,r;
	int key,prior,size;

	node(int _key){
		l = r = NULL; // no children
		key = _key;
		prior = rand(); // random priority
		size = 1;
	}

};

int sz(pnode t){
	if(t == NULL) return 0; // empty tree
	return t->size;
}

void upd(pnode t){
	if(t == NULL) return; // empty subtree, nothing to update
	t->size = sz(t->l) + 1 + sz(t->r); // sum of the size of children plus one
}

void split(pnode t,int key,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL; // base case : empty subtree
	}
	else if(key < t->key){
		split(t->l,key,l,t->l);
		r = t;
	}
	else{
		split(t->r,key,t->r,r);
		l = t;
	}
	upd(t);
}

void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	upd(t);
}

void insert(pnode &t,int key){
	pnode aux = new node(key);
	pnode L,R;
	split(t,key-1,L,R);
	merge(t,L,aux);
	merge(t,t,R);
}

void erase(pnode &t,int key){
	pnode L,mid,R;
	split(t,key-1,L,R);
	split(R,key,mid,R);
	if(mid) merge(mid,mid->l,mid->r);
	merge(t,L,mid);
	merge(t,t,R);
}

int count(pnode &t,int key,int bigger){
	if(bigger == 0){
		pnode L,R;
		split(t,key-1,L,R);
		int ans = sz(L);
		merge(t,L,R);
		return ans;
	}
	else{
		pnode L,R;
		split(t,key,L,R);
		int ans = sz(R);
		merge(t,L,R);
		return ans;
	}
}

pnode bit[MAXN];

void bit_update(int pos,int v,int op,int N){
	pos++; // 1-indexed
	while(pos <= N){
		if(op == 0) insert(bit[pos],v);
		else erase(bit[pos],v);
		pos += LSOne(pos);
	}
}

long long read(int pos,int v,int op){
	long long ans = 0;
	while(pos > 0){
		ans += count(bit[pos],v,op);
		pos -= LSOne(pos);
	}
	return ans;
}

long long query(int a,int b,int v,int op){
	a++,b++; // 1-indexed
	if(a > b) return 0;
	return read(b,v,op) - read(a-1,v,op);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	
	int Q=X.size();
	std::vector<int> answer(Q);
	long long inversoes = 0;
	int N = A.size();

	for(int i = 1;i<=N;i++) bit[i] = NULL;
	for(int i = 0;i<N;i++){
		inversoes += query(0,i-1,A[i],1);
		bit_update(i,A[i],0,N);
	}

	for(int q = 0;q<Q;q++){
		int x = X[q],v = V[q];
		inversoes -= query(0,x-1,A[x],1);
		inversoes -= query(x+1,N-1,A[x],0);
		A[x] = v;
		inversoes += query(0,x-1,A[x],1);
		inversoes += query(x+1,N-1,A[x],0);
		answer[q] = inversoes;
	}

	return answer;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40