洛谷4231 三步必杀

Luogu

算法

等差数列,考虑两次差分。

设公差为$d$,具体操作方法是$delta[l]+=s,delta[l+1]+=(d-s),delta[r+1]-=(d+e),delta[r+2]+=e$

找个规律就能出来。

最后$O(n)$扫描一遍即可。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int delta[10000010];

mainint main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        int l=read(),r=read(),s=read(),e=read();
        int d=(e-s)/(r-l);
        delta[l]+=s,delta[l+1]+=(d-s);
        delta[r+1]-=(d+e),delta[r+2]+=e;
    }
    int ans1=0,ans2=0;
    for (re int i=1,a=0,b=0;i<=n;i++) {
        b+=delta[i],a+=b;
        ans1^=a;
        if (a>ans2) ans2=a;
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 54 PM

发表评论