[TIOJ] 1871 . こちら、ふたなり幸福安心委員会です。

題目連結:http://tioj.infor.org/problems/1871

---

裸區間極值題(RMQ)，寫個sparse table就好了，這裡附上個我自己debug用時用的lib1871.h

---

lib1871.h

#include <utility>
#include <stdio.h>

namespace futa{
	int size;
	int *arr;
	int q;

	int init(){
		scanf("%d",&size);
		arr = new int[size];
		return size;
	}
	int* momo_gives_you_list_of_futa(){
		for(int i=0;i<size;i++){
			scanf("%d",&arr[i]);
		}
		return arr;
	}
	int momo_tells_you_q(){
		scanf("%d",&q);
		return q;
	}
	std::pair<int,int> momo_asks(){
		int l,r;
		scanf("%d %d",&l,&r);
		return std::make_pair(l,r);
	}
	void you_tell_momo(int a){
		printf("ANS:%d\n",a);
	}
}

Main Code:

#include "lib1871.h"
#include <utility>
#include <vector>
#include <algorithm>

using std::pair;
using std::vector;
using std::min;

vector<int> sTable[30];

inline int query(int,int);

int main(){
	int size = futa::init();
	auto arr = futa::momo_gives_you_list_of_futa();
	for(int i=0;i<size;i++)
		sTable[0].push_back(arr[i]);
	for(int i=2;i<=size;i*=2)
		for(int j=0;j+i<=size;j++)
			sTable[31-__builtin_clz(i)].push_back(min(sTable[31-__builtin_clz(i)-1][j], sTable[31-__builtin_clz(i)-1][j+(i>>1)]));
	int q = futa::momo_tells_you_q();
	while(q--){
		pair<int,int> p = futa::momo_asks();
		futa::you_tell_momo(query(p.first,p.second));
	}
}

inline int query(int a,int b){
	b+=1;
	int k = 31-__builtin_clz(b-a);
	return min(sTable[k][a], sTable[k][b-(1<<k)]);
}