题目描述

众所周知，一战过后，在世界列强建造超无畏级战列舰的竞争之中，旧日本海军根据“个舰优越主义”，建造了扶桑级战列舰，完工时为当时世界上武装最为强大的舰只。
同时，扶桑号战列舰也是舰岛最为科幻的战列舰。
当然，要建造这样的舰船，科技水平是必须的。
同样众所周知的是，德意志科学技术天下第一，所以IJN的司令官从德国学来了一种先进的建船方法。
一只战舰横过来可以看做一个长度为n的序列，每个位置有一个数ai表示这个位置设计的高度。这种先进的造船技术可以每次将一个区间[l,r]内的所有位置高度都+1,求到达最终设计状态的最少操作次数。
如果你不能及时完成的话，IJN司令官会奖励你去参加苏里高海战。

 

输入

第一行包含一个整数n，表示序列的长度。
第二行包含n个非负整数a1,a2,a3,…,an，表示最终的状态。

 

输出

输出的第一行是一个正整数m，表示最少的操作次数。
接下来m行每行两个正整数li,ri，表示一次操作。
你需要保证1≤li≤ri≤n。
保证最少次数m≤105，输出可以以任意顺序输出。

题目大意：每次对一段区间 +1 ，可以选择任意L R，问最少需要操作多少次使得到 指定的序列，序列初始都为0.

题目思路：

一：差分数组

差分数组  ：diff[i]=num[i]-num[i-1] 

所以，我们只要对一段区间进行 +1 操作时，总会有一个diff[i]会加1,区间起点 绝对加1，因为 num[s-1]没有处理到，所以num[s]-num[s-1]绝对会增加1，然后我们再看 既然有+1，绝对还会有-1，就是区间终点+1，就会-1，因为diff[e+1]=num[e+1]-num[e]，num[e]++，diff[e+1]就会--，还有一种情况就是 维护到n，当区间修改到n的话只有+1，没有-1。

根据这个性质，我们把已知序列的差分数组求出来，很显然，正数的和就是 操作数，如果出现一个负数，说明前面有一个正数和当前 i-1匹配，匹配次数就是负数绝对值，匹配原则就近匹配，1 1 -2 的话就 【1 2】 【2 2】，知道把负数匹配完，也就是以这个负数为终点的都解决了。如果没有负数那就正数匹配到n就可以了。具体操作我们用栈，将正数存到栈里，有负数就和当前栈首元素匹配，栈首元素到0，就pop()；最后剩下的正数都与n匹配即可。

具体操作用栈维护，我直接用stack也可以用数组模拟一下栈：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll num[maxn];
ll diff[maxn];
struct node{
    ll w;
    ll id;
};
stack<node>q;
int main()
{
    int ans=0;
    scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    diff[0]=0;for(int i=1;i<=n;i++) {diff[i]=num[i]-num[i-1];if(diff[i]>0) ans+=diff[i];}
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
    {
        if(diff[i]>0)
        {
            node temp;
            temp.id=i;
            temp.w=diff[i];
            q.push(temp);
        }
        else
        {
            ll sum=0,temp=abs(diff[i]);
            while(!q.empty())
            {
                node u=q.top();
                if(sum+u.w>temp)
                {
                    ll cop=temp-sum;
                    for(int k=1;k<=cop;k++) printf("%lld %lld\n",u.id,i-1);
                    u.w-=cop;
                    q.pop();
                    q.push(u);
                    break;
                }
                else
                {
                    q.pop();
                    for(int k=1;k<=u.w;k++) printf("%lld %lld\n",u.id,i-1);
                    sum+=u.w;
                }
            }
        }
    }
    while(!q.empty())
    {
        node u=q.top();q.pop();
        for(int k=1;k<=u.w;k++) printf("%lld %lld\n",u.id,n);
    }
    return 0;
}

二：笛卡尔树

前面讲到笛卡尔树，就是一个区间最小值最大值，而且他记录了左右点，所以我们对笛卡尔树进行一遍深搜即可：

根节点控制的绝对时 全部最小值 所以 区间 1 - n ，左边节点控制的 就是 1 到当前根节点-1， 右边就是当前根节点+1，n，递归遍历一下输出即可。

关于笛卡尔树的链接:笛卡尔树

AC代码：

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll l[maxn],r[maxn];
ll num[maxn];
int st[maxn];
void get_tree()
{
    int s=0;
    for(int i=1;i<=n;i++)
    {
        while(s&&num[i]<=num[st[s]])
            l[i]=st[s--];
        if(st[s]) r[st[s]]=i;
        st[++s]=i;
    }
}
void dfs(ll s,ll sum,ll L,ll R)
{
    for(int i=1;i<=num[s]-sum;i++)
        printf("%lld %lld\n",L,R);
    if(l[s])//向左遍历
        dfs(l[s],num[s],L,s-1);
    if(r[s])
        dfs(r[s],num[s],s+1,R);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    get_tree();
    int root=st[1];
    ll sum=0;
    for(int i=1;i<=n;i++)
        if(num[i]-num[i-1]>0) sum+=num[i]-num[i-1];
    printf("%lld\n",sum);
    dfs(root,0,1,n);
    return 0;
}