noic-solucao-avancado-s62.cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e6+10, root = 320, maxv = 1e6;

int resp, n, q, v[maxn], f[maxn], ans[maxn], bit[maxn];

struct Q
{
	int l, r, y, id, b;

	bool operator<(const Q& o) const
	{
		if(b == o.b) // otmização de paridade, não precisa (NESSE CASO) mas não custa nada sempre colocar =)
		{
			if(b&1) return r > o.r; // se o bloco for ímpar, ordenamos do maior r para o menor
			else return r < o.r; // se for par, ordenamos do menor r para o maior
		}
		return b < o.b; // se estivermos em blocos diferente ordenamos do menor para o maior bloco
	}
} qr[maxn];

int query(int p) // responde quantos números maiores que p existem
{
	int sum = 0;

	while(p <= maxv && p)
	{
		sum += bit[p];
		p += (p & -p);
	}

	return sum;
}

int upd(int p, int val) // atualizo adicono val em p 
{
	while(p > 0)
	{
		bit[p] += val;
		p -= (p & -p);
	}
}

int main()
{
	cin >> n >> q;

	for(int i = 1 ; i <= n ; ++i) cin >> v[i];

	for(int i = 0 ; i < q ; ++i)
	{
		cin >> qr[i].l >> qr[i].r >> qr[i].y; // leio as perguntas de Sufia

		qr[i].id = i;
		qr[i].b = (qr[i].l/root);
	}

	// Algoritmo de Mo

	sort(qr, qr+q); // ordeno as perguntas

	int left = 0, right = 0;

	for(int i = 0 ; i < q ; ++i)
	{
		int l = qr[i].l;
		int r = qr[i].r;
		int y = qr[i].y;
		int id = qr[i].id;
			
		while(right < r) // a rua right esta no dentre do meu intervalo
		{
			right++; // aumento o intevalo
			upd(v[right], 1); // adiociono o prédio na bit
		}

		while(left > l) // a rua left esta no dentre do meu intervalo
		{
			left--; // aumento o intervallo
			upd(v[left], 1); // adiciono o prédio na bit
		}

		while(right > r) // a rua right não esta no dentre do meu intervalo
		{
			upd(v[right], -1); // removo o prédio na bit
			right--; // diminuo o intervalo
		}

		while(left < l) // a rua left não esta no dentre do meu intervalo
		{
			upd(v[left], -1); // removo o prédio na bit
			left++; // diminuo o intervalo
		}

		ans[id] = query(y+1); // consulto quantos prédio com altura maior que y existem entre as ruas l e r
	}

	for(int i = 0 ; i < q ; ++i) // imprimo as respostas
	{
		cout << ans[i] << "\n";
	}
}