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]); } };
|
近期评论