Algorithm

Problem link- https://www.spoj.com/problems/GIVEAWAY/

GIVEAWAY - Give Away

#tree #binary-search

 

You are given a 1-indexed array X, consisting of N integers, and a set of Q queries. There are two kinds of queries:

  1. 0 a b c
    Here you are required to return the number of elements with indices in [a,b]
    greater than or equal to c
  2. 1 a b
    Here you are required to change the ath element of array to b.

Input Format:

First line contains N, the number of elements in the array X. The next line contains N space separated integers representing the elements of X. The third line of input contains a single integer, Q, the number of queries. The next Q lines of input each contain queries of two kinds as described above.

Output Format:

Q lines with the ith line contains the answer for the ith query

Constraints:

1 ≤ N ≤ 5*10^5
1 ≤ Q ≤ 10^5
1 ≤ X[i] ≤ 10^9
1 ≤ a ≤ b ≤ N for query type 0
1 ≤ a ≤ 10^5, 1 < b ≤ 10^9 for query type 1
1 ≤ c ≤ 10^9

Example

Sample Input:
5
1 2 3 4 5
3
0 1 5 10
1 2 20
0 1 3 10

Sample Output:
0
1

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 5e5+5;
int a[MAXN];
vector<int> b[710];

int main(){
	io;
	int n, q;
	cin >> n;
	int sqrtn = sqrt(n);
	for(int i = 0;i < n; i++){
		cin >> a[i];
		b[i/sqrtn].push_back(a[i]);
	}
	cin >> q;
	int numBlocks = ceil((double)n/sqrtn);
	for(int i = 0;i < numBlocks; i++)
		sort(b[i].begin(), b[i].end());
	while(q--){
		int c;
		cin >> c;
		if(c == 1){
			int idx, newVal;
			cin >> idx >> newVal;
			--idx;
			int block = idx/sqrtn;
			int initVal = a[idx];
			// search initVal in block
			int lo = 0, hi = sqrtn-1;
			while(lo <= hi){
				int mid = (lo + hi) >> 1;
				if(b[block][mid] == initVal){
					b[block][mid] = newVal;
					break;
				}else if(b[block][mid] < initVal){
					lo = mid + 1;
				}else{
					hi = mid - 1;
				}
			}
			a[idx] = newVal;
			sort(b[block].begin(), b[block].end());
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			--l;--r;
			int leftBlock = l/sqrtn;
			int rightBlock = r/sqrtn;
			int ans = 0;
			if(leftBlock == rightBlock){
				for(int i = l;i <= r; i++){
					if(a[i] >= x)
						ans++;
				}
				cout << ans << endl;
			}else{
				if(l%sqrtn != 0)
					leftBlock++;
				int i;
				for(i = l;i < leftBlock*sqrtn; i++)
					if(a[i] >= x)
						ans++;
				while(i+sqrtn-1 <= r){
					int bb = i/sqrtn;
					ans += b[bb].end() - lower_bound(b[bb].begin(), b[bb].end(), x);
					i += sqrtn;
				}
				while(i <= r){
					if(a[i] >= x)
						ans++;
					i++;
				}
				cout << ans << endl;
			}
		}
	}
	// vector<int> temp;
	// for(int i = 2;i<= 10; i++)
	// 	temp.push_back(i);
	// cout << temp.end() - lower_bound(temp.begin(), temp.end(), 2) << endl;
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
1 2 3 4 5
3
0 1 5 10
1 2 20
0 1 3 10

Output

x
–
+
cmd
0
1
Advertisements

Demonstration

SPOJ Solution-Give Away-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python