学网站论坛,外资做网站的公司,互联网官网,网站空间在哪申请扶桑号战列舰 时间限制: 1 Sec 内存限制: 128 MB Special Judge 提交: 197 解决: 63 [提交] [状态] [命题人:admin] 题目描述 众所周知#xff0c;一战过后#xff0c;在世界列强建造超无畏级战列舰的竞争之中#xff0c;旧日本海军根据“个舰优越主义”#xff0c;建造了扶…扶桑号战列舰 时间限制: 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 il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
typedef pairint,int p;
p dp[100100][25];
int arr[100100];
pairint,int res[100100];
void RMQ(int n) {for(int i1;in;i) {dp[i][0].secondarr[i];dp[i][0].firsti;}for(int k1;k(int)log2(n);k) {for(int i1;i(1k)-1n;i) {if(dp[i][k-1].seconddp[i(1(k-1))][k-1].second) {dp[i][k].seconddp[i][k-1].second;dp[i][k].firstdp[i][k-1].first;}else {dp[i][k].seconddp[i(1(k-1))][k-1].second;dp[i][k].firstdp[i(1(k-1))][k-1].first;}}}
}
p find(int l,int r) {int k(int)log2(r-l1);if(dp[l][k].seconddp[r1-(1k)][k].second) return dp[l][k];else return dp[r1-(1k)][k];
}
int cnt;
void fenzhi(int l,int r,int num) {if(lr) return;p napefind(l,r);int tnape.second;int midnape.first;for(int knum1;kt;k) {cnt;res[cnt].firstl;res[cnt].secondr;}fenzhi(l,mid-1,t);fenzhi(mid1,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 i1;icnt;i) {printf(%d %d\n,res[i].first,res[i].second);}return 0;
}
