Strange Race - EDITORIAL

#PROBLEM LINK:
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) .

AC Solution CodeChef: Practical coding for everyone

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) .

AC Solution CodeChef: Practical coding for everyone

I think we can use sparse segment tree as well and it’s time complexity will be O(log(N)) per query maybe :slight_smile: