程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [NYOJ 119] 士兵殺敵(三) (RMQ ST算法)

[NYOJ 119] 士兵殺敵(三) (RMQ ST算法)

編輯:C++入門知識

 

題目大意:

有N個士兵,從左到右排成一排,編號從1到N,每個人殺了不同數量的敵人。現在有Q個詢問,每次詢問要求求出[L,R]區間殺敵做多的和殺敵最少的差。 RMQ ST算法裸題。
/*
ID: [email protected]
PROG: beads
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define maxn 100010
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int N, Q, mx[20][maxn], mn[20][maxn];
void RMQ(int num)
{
    for (int i = 1; i <= log2(num) + 1; i++)
        for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num)
        {
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << i >> 1)]);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i >> 1)]);
        }
}
int main ()
{
    scanf(%d%d, &N, &Q);
    for (int i = 1; i <= N; i++)
    {
        scanf(%d, &mx[0][i]);
        mn[0][i] = mx[0][i];
    }
    RMQ(N);
    int st, ed;
    while(Q--)
    {
        scanf(%d%d, &st, &ed);
        int k = (int) log2(ed - st + 1.0);
        int mxans = max(mx[k][st], mx[k][ed - (1 << k) + 1]);
        int mnans = min(mn[k][st], mn[k][ed - (1 << k) + 1]);
        printf(%d
, mxans - mnans);
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved