rmq（区间最值查询，可以查询__gcd）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


template<typename T>
class RMQ {
 public:
 	vector<vector<T> > dp; 
    RMQ() {}
    RMQ(vector<T>& a) {
    	int n = a.size();
    	dp.resize(n);
    	for(int i=0; i<n; i++)	dp[i].resize(20);
    	//for (auto& i : dp) i.resize(20);
    	for(int i=0; i<n; i++) dp[i][0]=a[i];
    	for(int j=1; (1<<j)<=n; j++)
        for(int i=0;i+(1<<j)-1<n;i++) {
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
    T que(int L, int R) {	//下标从零开始 
    	if(L>R)	return 0;
    	int k=0;
    	while((1<<(k+1))<=R-L+1) k++;
    	return min(dp[L][k],dp[R-(1<<k)+1][k]);
	}
};







			
赞微海报分享