Salary Queries

Solución 1

Como se menciona en el módulo, se puede aplicar compresión de coordenadas antes de usar un Árbol de Segmentos o un BIT.

Quedarse con arreglos (o vectors) siempre que sea posible; usar un map en su lugar puede dar TLE.

C++Java


#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int MX = 4e5 + 5;
 
ll bit[MX];
vector<int> vals;
int n, q;
 
void upd(int i, int val) {
	for (; i <= MX; i += i & (-i)) { bit[i] += val; }
}
 
void ad(int x, int b) {
	int ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();
	upd(ind, b);
}
 
ll sum(int x) {
	ll res = 0;
	for (; x; x -= x & (-x)) { res += bit[x]; }
	return res;
}
 
ll query(int x) {
	int ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();
	return sum(ind);
}
 
int main() {
	cin >> n >> q;
	vector<int> ar(n);
	for (int i = 0; i < n; i++) { cin >> ar[i]; }
	vals = ar;
	vector<array<int, 3>> rec;
	for (int i = 0; i < q; i++) {
		char t;
		int a, b;
		cin >> t >> a >> b;
		rec.push_back({t == '?', a, b});
		if (t == '!') vals.push_back(b);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	for (int i = 0; i < n; i++) { ad(ar[i], 1); }
	for (auto u : rec) {
		u[1]--;
		if (u[0] == 0) {
			ad(ar[u[1]], -1);
			ar[u[1]] = u[2];
			ad(ar[u[1]], 1);
		} else {
			cout << query(u[2]) - query(u[1]) << '\n';
		}
	}
}


import java.io.*;
import java.util.*;
 
// Aprovechamos que el número total de salarios únicos, incluyendo las consultas y
// el arreglo de entrada, no es más que n (2e5) + 2 * q (2e5), que es 6*10^5.
 
// Así no hay que preocuparse por salarios en el rango 1e9: los comprimimos.
 
public class Salary_Queries {
	static Reader fr = new Reader();
	static PrintWriter out = new PrintWriter(System.out);
 
	static long[] list;
	static long[] Seq;
	static HashMap<Long, Integer> map;
 
	public static void main(String[] args) throws java.lang.Exception {
		int n = fr.nextInt();
		int q = fr.nextInt();
 
		// Arreglo de tamaño fijo evita el overhead de redimensionar ArrayList y el autoboxing de Long.
		list = new long[n + (q << 1)];
		int ptr = 0;
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = fr.nextLong();
			list[ptr++] = arr[i];
		}
 
		long[][] query = new long[q][3];
		for (int i = 0; i < q; i++) {
			char ch = fr.nextChar();
			long a = fr.nextLong();
			long b = fr.nextLong();
 
			if (ch == '!') {
				query[i][0] = 0;
				query[i][1] = a - 1;
				query[i][2] = b;
 
				list[ptr++] = b;
			} else {
				query[i][0] = 1;
				query[i][1] = a;
				query[i][2] = b;
				list[ptr++] = a;
				list[ptr++] = b;
			}
		}
 
		// Paso de compresión
		// Inicio
		Arrays.sort(list, 0, ptr);
 
		int cnt = 0;
		long prev = 0;
		map = new HashMap<>();
		for (int i = 0; i < ptr; i++) {
			if (prev != list[i]) map.put(list[i], cnt++);
			prev = list[i];
		}
		// Fin
 
		BIT bt = new BIT(cnt);
 
		for (long ele : arr) { bt.update(map.get(ele), 1); }
 
		StringBuilder SB = new StringBuilder();
		for (long[] qr : query) {
			if (qr[0] == 0) {
				bt.update(map.get(arr[(int)qr[1]]), -1);
				arr[(int)qr[1]] = qr[2];
				bt.update(map.get(arr[(int)qr[1]]), 1);
			} else {
				int ans = bt.get(map.get(qr[1]), map.get(qr[2]));
 
				SB.append(ans).append('\n');
			}
		}
 
		out.println(SB.to_string());
		out.close();
	}
 
	// BeginCodeSnip{Reader}
	static class Reader {
		private final int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;
 
		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
 
		// Lee el siguiente entero de la entrada
		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') { c = read(); }
			boolean neg = (c == '-');
			if (neg) c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
			return neg ? -ret : ret;
		}
 
		// Lee el siguiente long de la entrada
		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ') { c = read(); }
			boolean neg = (c == '-');
			if (neg) c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
			return neg ? -ret : ret;
		}
 
		public char nextChar() throws IOException {
			byte c = read();
			while (c <= ' ') { c = read(); }
			return (char)c;
		}
 
		// Lee el siguiente byte del buffer
		private byte read() throws IOException {
			if (bufferPointer == bytesRead) fillBuffer();
			return buffer[bufferPointer++];
		}
 
		// Llena el buffer con datos nuevos
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1) buffer[0] = -1;
		}
	}
	// EndCodeSnip
 
	public static int max(int a, int b) { return Math.max(a, b); }
	public static int min(int a, int b) { return Math.min(a, b); }
	public static long max(long a, long b) { return Math.max(a, b); }
	public static long min(long a, long b) { return Math.min(a, b); }
}
 
class BIT {
	int[] bit;
	int size;
 
	public BIT(int n) {
		this.size = n;
		bit = new int[n + 1];
	}
	int sum(int r) {
		int res = 0;
		for (; r >= 0; r = (r & (r + 1)) - 1) { res += bit[r]; }
 
		return res;
	}
 
	void update(int x, int delta) {
		for (; x < size; x |= x + 1) { bit[x] += delta; }
	}
 
	int get(int l, int r) { return sum(r) - sum(l - 1); }
}

Aquí hay una solución similar con un map que pasa ligeramente por debajo del límite de tiempo.

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Binary Indexed Tree (from the module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
 
	T sum(int ind_left, int ind_right) {
		return pref_sum(ind_right) - pref_sum(ind_left - 1);
	}
};
// EndCodeSnip
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, q;
	cin >> n >> q;
	vector<int> coords;
	map<int, int> compr;
	vector<int> p(n + 1);
 
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		coords.push_back(p[i]);
	}
 
	vector<pair<char, pair<int, int>>> queries;
	for (int i = 0; i < q; i++) {
		char c;
		cin >> c;
		int a, b;
		cin >> a >> b;
		coords.push_back(a);
		coords.push_back(b);
		queries.push_back({c, {a, b}});
	}
 
	sort(coords.begin(), coords.end());
	const int num_coords = coords.size() + 1;
	BIT<int> bit(num_coords);
 
	for (int i = 0; i < num_coords - 1; i++) compr[coords[i]] = i;
	for (int i = 1; i <= n; i++) {
		p[i] = compr[p[i]];
		bit.add(p[i], 1);
	}
 
	for (const auto &[type, vals] : queries) {
		if (type == '!') {
			int k = vals.first;
			int x = compr[vals.second];
			bit.add(p[k], -1);
			bit.add(x, 1);
			p[k] = x;
		} else {
			cout << bit.sum(compr[vals.first], compr[vals.second]) << '\n';
		}
	}
}

Solución 2

¡Simplemente usar indexed set!

C++


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef pair<int, int> pii;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
 
const int INF = 1000000007;
 
int n, q, a[200001];
Tree<pii> o;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	FOR(i, 1, n + 1) {
		cin >> a[i];
		o.insert({a[i], i});
	}
	F0R(i, q) {
		char c;
		cin >> c;
		if (c == '!') {
			int x, y;
			cin >> x >> y;
			o.erase({a[x], x});
			a[x] = y;
			o.insert({a[x], x});
		} else {
			int x, y;
			cin >> x >> y;
			cout << o.order_of_key({y, INF}) - o.order_of_key({x - 1, INF}) << "\n";
		}
	}
}