扶桑號戰列艦
時間限制: 1 Sec 內存限制: 128 MB Special Judge
提交: 197 解決: 63
[提交] [狀態] [命題人:admin]
題目描述
眾所周知，一戰過后，在世界列強建造超無畏級戰列艦的競爭之中，舊日本海軍根據“個艦優越主義”，建造了扶桑級戰列艦，完工時為當時世界上武裝最為強大的艦只。
同時，扶桑號戰列艦也是艦島最為科幻的戰列艦。
當然，要建造這樣的艦船，科技水平是必須的。
同樣眾所周知的是，德意志科學技術天下第一，所以IJN的司令官從德國學來了一種先進的建船方法。
一只戰艦橫過來可以看做一個長度為n的序列，每個位置有一個數ai表示這個位置設計的高度。這種先進的造船技術可以每次將一個區間[l,r]內的所有位置高度都+1,求到達最終設計狀態的最少操作次數。
如果你不能及時完成的話，IJN司令官會獎勵你去參加蘇里高海戰。

輸入
第一行包含一個整數n，表示序列的長度。
第二行包含n個非負整數a1,a2,a3,…,an，表示最終的狀態。

輸出
輸出的第一行是一個正整數m，表示最少的操作次數。
接下來m行每行兩個正整數li,ri，表示一次操作。
你需要保證1≤li≤ri≤n。
保證最少次數m≤105，輸出可以以任意順序輸出。

樣例輸入
復制樣例數據
6
2 3 3 3 3 3
樣例輸出
3
1 6
1 6
2 6

提示

解題思路：
通過RMQ維護區間最小值，然后在分治即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
typedef pair<int,int> p;
p dp[100100][25];
int arr[100100];
pair<int,int> res[100100];
void RMQ(int n) {for(int i=1;i<=n;i++) {dp[i][0].second=arr[i];dp[i][0].first=i;}for(int k=1;k<=(int)log2(n);k++) {for(int i=1;i+(1<<k)-1<=n;i++) {if(dp[i][k-1].second<=dp[i+(1<<(k-1))][k-1].second) {dp[i][k].second=dp[i][k-1].second;dp[i][k].first=dp[i][k-1].first;}else {dp[i][k].second=dp[i+(1<<(k-1))][k-1].second;dp[i][k].first=dp[i+(1<<(k-1))][k-1].first;}}}
}
p find(int l,int r) {int k=(int)log2(r-l+1);if(dp[l][k].second<=dp[r+1-(1<<k)][k].second) return dp[l][k];else return dp[r+1-(1<<k)][k];
}
int cnt;
void fenzhi(int l,int r,int num) {if(l>r) return;p nape=find(l,r);int t=nape.second;int mid=nape.first;for(int k=num+1;k<=t;k++) {cnt++;res[cnt].first=l;res[cnt].second=r;}fenzhi(l,mid-1,t);fenzhi(mid+1,r,t);
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int n;scanf("%d",&n);rep(i,1,n) {scanf("%d",&arr[i]);}RMQ(n);fenzhi(1,n,0);printf("%d\n",cnt);for(int i=1;i<=cnt;i++) {printf("%d %d\n",res[i].first,res[i].second);}return 0;
}