Cod sursa(job #2300733)

Utilizator livliviLivia Magureanu livlivi Data 11 decembrie 2018 21:45:09
Problema Arbori indexati binar Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#define d(x) x&(-x)
#define NMAX 100000
using namespace std;

ifstream cin ("aib.in");
ofstream cout("aib.out");

template <const int N, int (*merge)(int &, int &)>
class AIB {
private:
	int v[N + 1];
	int neutru;

public:
	AIB(int y = N, int x = 0){
		neutru = x;

		for(int i = 0; i <= N; i++)
			v[i] = neutru;
	}

	void update(int i, int x){
		for(; i <= N; i += d(i))
			v[i] = merge(v[i], x);
	}

	int query(int i){
		int ans = neutru;

		for(; i > 0; i -= d(i))
			ans = merge(ans, v[i]);

		return ans;
	}

	int binsearch(int x, bool strict = false, bool egal = false){
		int p = (1 << 30);
		int i = 0;
		int curr = neutru;

		while(p > 0){
			if (i + p <= N && merge(curr, v[i + p]) + strict <= x){
				curr = merge(curr, v[i + p]);
				i += p;
			}
			p /= 2;
		}

		if (egal){
			if (i + 1 > N || query(i + 1) != x) return -1;
			else return i + 1;
		}
		
		return i;
	}
};

int add(int &a, int &b){
	return a + b;
}

int main(){
	int n, m; cin >> n >> m;
	AIB <NMAX, add> myaib;

	for(int i = 1; i <= n; i++){
		int a; cin >> a;
		myaib.update(i, a);
	}

	for(int i = 1; i <= m; i++){
		int op; cin >> op;

		if (op == 0){
			int a, b; cin >> a >> b;
			myaib.update(a, b);
		}
		else
		if (op == 1){
			int a, b; cin >> a >> b;
			cout << myaib.query(b) - myaib.query(a - 1) << '\n';
		}
		else 
		if (op == 2){
			int a; cin >> a;
			cout << myaib.binsearch(a, true, true) << '\n';
		}
	}

	return 0;
}