ST算法

Dear 丶 2022-06-14 04:38 138阅读 0赞

\#\#文字转载

作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例

举例：

给出一数组A\[0~5\] = \{5,4,6,10,1,12\},则区间\[2,5\]之间的最值为1。

方法：ST算法分成两部分：离线预处理 （nlogn）和 在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。

（1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。

（2）在线查询：对给定区间进行分割，借助该二维数组求最值

具体解释：

（1）离线预处理：

ST算法使用DP思想求解区间最值，貌似属于区间动态规划，不过区间在增加时，每次并不是增加一个长度，而是使用倍增的思想，每次增加2^i个长度。

使用F\[i,j\]表示以i为起点，区间长度为2j的区间最值，此时区间为\[i,i + 2j \- 1\]。

比如，F\[0,2\]表示区间\[0,3\]的最小值，即等于4，F\[2,2\]表示区间\[2,5\]的最小值，即等于1。

在求解F\[i,j\]时，ST算法是先对长度为2j的区间\[i,i + 2j\- 1\]分成两等份，每份长度均为2^(j - 1)^。之后在分别求解这两个区间的最值F\[i,j - 1\]和F\[i + 2^(j - 1), j - 1\]。，最后在结合这两个区间的最值，求出整个区间的最值。特殊情况，当j = 0时，区间长度等于0，即区间中只有一个元素，此时F\[i,0\]应等于每一个元素的值。

举例：要求解F\[1,2\]的值，即求解区间\[1,4\] = \{4,6,10,1\}的最小值，此时需要把这个区间分成两个等长的区间，即为\[1,2\]和\[3,4\]，之后分别求解这两个区间的最小值。此时这两个区间最小值分别对应着F\[1,1\] 和 F\[3,1\]的值。

状态转移方程是 F\[i,j\] = min(F\[i,j - 1\],F\[i + 2^(j - 1)^,j - 1\])

初始状态为：F\[i,0\] = A\[i\]。

在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值…，最后，对每一个元素，在求解区间长度为log2^n的区间最值后，算法结束，其中n表示元素个数。

即：先求F\[0\]\[1\]，F\[1\]\[1\]，F\[2\]\[1\]，F\[3\]\[1\]，,，F\[n\]\[1\]，再求.F\[0\]\[2\]，F\[1\]\[2\]，F\[2\]\[2\]，F\[3\]\[2\]，,，F\[m\]\[2\],… 。

#include<cstdio>
    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int maxn = 2500+10;
    typedef long long LL;
    struct node {
    	int x, y;
        bool operator < (const node &a) const {
            if (x == a.x)
                return y<a.y;
            return x<a.x;
        }
    }p[maxn];
    
    int n, k;
    int minsum[200010][20];
    
    void RMQ(int num) {
    	for (int j=1; j<20; j++) {
    		for (int i=1; i<=num; i++)
    			if (i+(1<<j)-1 <= num)
    				minsum[i][j] = min(minsum[i][j-1], minsum[i+(1<<(j-1))][j-1]);
    	}
    }
    
    int qry(int s, int t) {
    	int k=(int)((log(t-s+1))/log(2.0));
    	int minl = min(minsum[s][k], minsum[t-(1<<k)+1][k]);
    	return minl;
    }
    
    int main() {
        scanf("%d%d", &n, &k);
    	for (int i=1; i<=n; i++) 
    		scanf("%d", &minsum[i][0]);
        
    	RMQ(n);
    
    	int q;
    	scanf("%d", &q);
    	for (int i=0; i<q; i++) 
            scanf("%d%d", &p[i].x, &p[i].y);
        sort(p, p+q);
        
        int ans = 0;
    	for (int i=0; i<q; i++) {
    		for (int j=i+1; j<q; j++) {
    			int minn = min(p[i].y, p[j].y);
                
    			int minh = qry(p[i].x, p[j].x);
                
    			int dis = abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
    			if (minh >= minn) {
    				if (dis <= k)
    					ans++;
    			}
    			else {
    				dis = dis+(minn-minh)*2;
    				if (dis <= k)
    					ans++;
    			}
    		}
    	}
        printf("%d\n", ans);
        return 0;
    }