Strange Race - EDITORIAL

contest

#PREREQUISITES:
SQRT-Decomposition.

#Problem:
Given an array of numbers you have perform 2 type of queries:-
1-Replace ith given number with the new number.
2-Count how many numbers in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X(given)

#Explanation:
Idea is to partition the array to sqrt(n) partitions sort each partition separately then answer queries on each partition with a binary search.
As shown in the code below.

``````#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
const int LEN = 700;
int num[MAX], seg[MAX];

int lowerbound(int *a, int st, int en, int val) {
int idx, cnt, stp;
cnt = en - st;
while(cnt > 0) {
stp = cnt >> 1; idx = st + stp;
if(a[idx] < val) st = ++idx, cnt -= stp+1;
else cnt = stp;
}
return st;
}

int upperbound(int *a, int st, int en, int val) {
int idx, cnt, stp;
cnt = en - st;
while(cnt > 0) {
stp = cnt >> 1; idx = st + stp;
if(a[idx] <= val) st = ++idx, cnt -= stp+1;
else cnt = stp;
}
return st;
}

void insert(int st, int en, int j, int v, int x) {
int i = j; seg[j] = num[x] = v;
for(i = j; i + 1 < en && seg[i] > seg[i + 1]; i++) swap(seg[i], seg[i + 1]);
for(i = j; i - 1 >= st && seg[i] < seg[i - 1]; i--) swap(seg[i], seg[i - 1]);
}

int main() {
int n, q, i, j, k, sz, x, y, v, st, en;
// char op[2];
int type;
scanf("%d %d", &n, &q);
for(i = 0; i < n; i++) {
scanf("%d", &num[i]);
seg[i] = num[i];
}
for(i = 0; i < n; i++) {
j = min(i + LEN, n);
sort(seg + i, seg + j);
i = j - 1;
}
sz = (n + LEN - 1) / LEN;
while(q--) {
scanf("%d", &type);
switch(type) {
case 2:
scanf("%d %d %d", &x, &y, &v);
st = --x / LEN; en = --y / LEN;
if(st == en) {
for(i = x, k = 0; i <= y; i++) k += (num[i] <= v);
printf("%d\n", k);
}
else {
j = min((st + 1)*LEN, n);
for(i = x, k = 0; i < j; i++) k += (num[i] <= v);
for(i = en * LEN; i <= y; i++) k += (num[i] <= v);
for(i = st + 1; i <= en - 1; i++) k += upperbound(seg, i * LEN, min((i+1) * LEN, n), v) - i * LEN;
printf("%d\n", k);
}
break;
case 1:
scanf("%d %d", &x, &v);
k = --x / LEN;
j = lowerbound(seg, st = k*LEN, en = min((k+1)*LEN, n), num[x]);
insert(st, en, j, v, x);
}
}
return 0;
}``````

There is an O(log^2(n)) per query solution.

1. First do coordinate compression on the data. (Even on the queries)
2. Now make a 2d Range tree. Where x coordinate is the position in the array and y coordinate is the compressed value. You can use a bit for 1st dimension and a pointer segment tree for second dimension

For Query 1 :
Just remove the previous coordinate of position i and add a new coordinate.

For Query 2 :
Count the number of coordinates in rectangle (P,1) to (Q,x) .

There is an O(log^2(n)) per query solution.

1. First do coordinate compression on the data. (Even on the queries)
2. Now make a 2d Range tree. Where x coordinate is the position in the array and y coordinate is the compressed value. You can use a bit for 1st dimension and a pointer segment tree for second dimension

For Query 1 :
Just remove the previous coordinate of position i and add a new coordinate.

For Query 2 :
Count the number of coordinates in rectangle (P,1) to (Q,x) .

//