【NOIP提高A组模拟2018.8.14】 区间

区间加：差分数组修改

O(n)扫描，负数位置单调不减

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=100005;

int a[MAXN],d[MAXN];
queue<int> Q1,Q2;
int n,ans;

int main(){
    freopen("range.in","r",stdin);
    freopen("range.out","w",stdout);
    n=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=n;i++){
        d[i]=a[i]-a[i-1];
        if(d[i]>0) ans+=d[i];
    }
    d[n+1]=-(1<<29);
    printf("%d
",ans);
    int j=2;
    for(int i=1;i<=n;i++){
        if(d[i]==0) continue;
        while(d[i]!=0){
            if(d[j]>=0){j++;continue;}
            d[i]-=1;
            d[j]+=1;
            printf("%d %d
",i,j-1);
        }    
    }    
    return 0;
}