国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

當前位置: 首頁 > news >正文

網(wǎng)站建設免費軟件有哪些推特最新消息今天

網(wǎng)站建設免費軟件有哪些,推特最新消息今天,動態(tài)網(wǎng)站編程,做網(wǎng)站怎么賺錢廣告【題目鏈接】 ybt 1541:【例 1】數(shù)列區(qū)間最大值 【題目考點】 1. RMQ問題 RMQ問題是給定一個序列,多次求區(qū)間最值的問題。 常用解法: ST表:離線算法,預處理 O ( n log ? n ) O(n\log n) O(nlogn),區(qū)間…

【題目鏈接】

ybt 1541:【例 1】數(shù)列區(qū)間最大值

【題目考點】

1. RMQ問題

RMQ問題是給定一個序列,多次求區(qū)間最值的問題。
常用解法:

  • ST表:離線算法,預處理 O ( n log ? n ) O(n\log n) O(nlogn),區(qū)間查詢 O ( 1 ) O(1) O(1)
  • 線段樹:在線算法,預處理 O ( n ) O(n) O(n),區(qū)間查詢 O ( log ? n ) O(\log n) O(logn)

【解題思路】

解法1:ST表

概念及解析見洛谷 P3865 【模板】ST 表 && RMQ 問題

解法2:線段樹

基本概念及解析見洛谷 P3374 【模板】樹狀數(shù)組 1(線段樹解法)
線段樹中每個結點保存的值為該結點表示的區(qū)間中的最大值。
使用孩子結點的值更新雙親結點的值時(pushUp操作),取左右孩子結點的值的最大值,即為當前結點的值。
區(qū)間查詢時:

  • 如果當前結點表示的區(qū)間被待查詢區(qū)間完全包含,則返回當前結點的值。
  • 如果當前結點表示的區(qū)間沒有被待查詢區(qū)間包含,則求出左右孩子結點表示的區(qū)間在待查詢區(qū)間中的最大值,返回這兩個值的最大值。

【題解代碼】

解法1:ST表
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define L 30
int a[N], lg[N], f[N][L];//f[i][j]:a[i]~a[i+2^j-1]中的最大值 
void initLg(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;
}
int query(int l, int r)
{int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;initLg(n);for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i)f[i][0] = a[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);while(m--){cin >> l >> r;cout << query(l, r) << '\n';}return 0;
}
解法2:線段樹
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int l, r, val;
} tree[4*N];
int a[N];
void pushUp(int i)
{tree[i].val = max(tree[2*i].val, tree[2*i+1].val);
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r){tree[i].val = a[l];return;}int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].l > r || tree[i].r < l)return INT_MIN;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return max(query(2*i, l, r), query(2*i+1, l, r));
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];build(1, 1, n);while(m--){cin >> l >> r;cout << query(1, l, r) << '\n';}return 0;
}
http://aloenet.com.cn/news/34734.html

相關文章:

  • 局域網(wǎng)網(wǎng)站怎么做谷歌搜索排名
  • 用vue做的網(wǎng)站怎么實現(xiàn)響應式株洲專業(yè)seo優(yōu)化
  • 深圳微網(wǎng)站開發(fā)最新全國疫情消息
  • 南昌網(wǎng)站關鍵詞優(yōu)化廣州百度關鍵詞推廣
  • 天津網(wǎng)絡優(yōu)化網(wǎng)站建設互聯(lián)網(wǎng)產(chǎn)品運營
  • 教人做飲料的網(wǎng)站寧波網(wǎng)絡營銷策劃公司
  • 做圖片類型網(wǎng)站需要什么服務器網(wǎng)站設計師
  • dw做網(wǎng)站怎么用到java免費發(fā)帖推廣網(wǎng)站
  • 網(wǎng)站項目評價河源疫情最新通報
  • 網(wǎng)站開發(fā)是前端還是后臺有友情鏈接的網(wǎng)站
  • 珠海建網(wǎng)站上海aso蘋果關鍵詞優(yōu)化
  • 網(wǎng)站做的好的醫(yī)院google瀏覽器下載
  • 貿(mào)易公司做網(wǎng)站有優(yōu)勢嗎競價是什么意思
  • 網(wǎng)頁設計 傳統(tǒng)網(wǎng)站全網(wǎng)推廣代理
  • 河南企業(yè)網(wǎng)站制作wordpress免費建站
  • 網(wǎng)絡上建個網(wǎng)站買東西多少錢怎么找專業(yè)的營銷團隊
  • 網(wǎng)上購物系統(tǒng)源碼seo診斷a5
  • 視頻公司的網(wǎng)站設計模板網(wǎng)站建站公司
  • 如何對網(wǎng)站建設和維護企業(yè)策劃
  • 用織夢網(wǎng)站后臺發(fā)布文章為什么還需要審核谷歌下載安裝
  • 公司網(wǎng)站建設南寧百度競價收費標準
  • 房地產(chǎn)營銷網(wǎng)站建設新浪微指數(shù)
  • 鄭州中揚科技網(wǎng)站建設公司怎么樣網(wǎng)絡營銷方案ppt
  • 手機端網(wǎng)站建站品牌營銷案例分析
  • wordpress耗資源關閉深圳最好的外貿(mào)seo培訓
  • 安徽省建設廳網(wǎng)站域名容易被百度收錄的網(wǎng)站
  • 網(wǎng)站開發(fā)需求調研互動營銷案例100
  • 用vue做的網(wǎng)站模板seo網(wǎng)站推廣如何做
  • 江蘇中南建筑信息平臺搜索引擎seo優(yōu)化怎么做
  • 做網(wǎng)站合肥百度搜索推廣平臺