P 2880バランスのラインナップ

4906 ワード

ここでは、新しいアルゴリズム(非常に優れている):STテーブルを紹介します.
このアルゴリズムは,実際には区間内の最大値または最小値がいくらであるかを求めるものであり,もちろん時間の複雑さを低減する最適化である.
明らかに線分樹はダメなので(複雑度が高すぎるO(mlogn))、線分樹を妄想している人はやめましょう~:3
ではまず概念的解釈を理解し,dp[i][j]についてはiを起点とし,長さが2 jの区間における最大値を意味する(私の記述に注意).
それではとても简単で、主な思想は毎回2つに分けて、それぞれ最大値を求めて、更に全体の最大値を求めます.
区間が重ならないように注意(面倒ではない)、長さも最適化(i+(1<直接コード:

#include
#include
#include
using namespace std;
#define maxn 50005
int dp[maxn][21],dj[maxn][21];
int n,q,a[maxn],b[maxn];
void Deal_now()
{
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=a[i];
        dj[i][0]=a[i];
    }
    for(int j=1;(1<)
        for(int i=1;i+(1<1<=n;i++)
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<1))][j-1]);
            dj[i][j]=min(dj[i][j-1],dj[i+(1<1))][j-1]);
        }    
    for(int i=1;i<=n;i++)
         b[i]=log2(i);
}
int query(int L,int R)
{
    int k=b[R-L+1];
    int ans1=max(dp[L][k],dp[R-(1<1][k]);
    int ans2=min(dj[L][k],dj[R-(1<1][k]);
    return ans1-ans2;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    Deal_now();
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",query(x,y)); 
    }return 0;
}

転載先:https://www.cnblogs.com/popo-black-cat/p/10056118.html

[アルゴリズム]int配列a[]は、すべてのa[i]を求め、左側はそれ以下、右側はそれ以上である.

python reとre.subファイルの一部を置換