danihao123's Blog

很容易想到线段树水过。

很可惜，这样估计也就70分。

然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定？

不知道诸位还记得差分序列？记得就好，用差分序列的方法维护即可。

等等，我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的，能过？

推荐一个行之有效的优化：注意一下每一次修改都是在之前的基础上反悔或前进几次，所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~

代码：

#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
    register int i,cnt=0;
    if(x>last)
        for(i=last+1;i<=x;i++){
            C[l[i]]+=d[i];
            C[r[i]+1]-=d[i];
        }
    if(x<last)
        for(i=x+1;i<=last;i++){
            C[l[i]]-=d[i];
            C[r[i]+1]+=d[i];
        }
    last=x;
    for(i=1;i<=n;i++){
        cnt+=C[i];
        if(cnt>A[i])
            return false;
    }
    return true;
}

int main(){
    register int i,L,M,R;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=m;i++){
        scanf("%lld%d%d",&d[i],&l[i],&r[i]);
    }
    L=1;
    R=m+1;
    while(L<R){
        M=L+(R-L)/2;
        if(Check(M)){
            L=M+1;
        }else{
            R=M;
        }
    }
    if(L==m+1)
        puts("0");
    else
        printf("-1\n%d\n",L);
    return 0;
}

这题并不很好下手，但注意差分序列的前缀和为原值这个性质。

由此可见，所求数列的差分序列除了第一项以外都应该是0，求出满足条件的最小操作次数就轻松多了。

求满足条件的数列个数似乎也不是难事。通过差分序列易推数列第一项差分值的范围，突破口就在于此。

看起来，满足条件数列个数为[tex]max(S1,S2)-min(S1,S2)[/tex]（S1，S2分别为正、负差分绝对值的和）。但是请注意，存在第一项没被操作的特殊情况。并且精度也是个问题！

/**************************************************************
    Problem: 3043
    User: danihao123
    Language: C++
    Result: Accepted
    Time:292 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int n;
    long long last=0,temp;
    register long long S1=0,S2=0,i,cf,ans2;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%llu",&temp);
        cf=temp-last;
        if(i!=1){
            if(cf>0)
                S1+=cf;
            else
                S2-=cf;
        }
        last=temp;
    }
    ans2=max(S1,S2)-min(S1,S2)+1;
    printf("%llu\n%llu\n",max(S1,S2),ans2);
    return 0;
}