#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
10724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
