题解 P2367 【语文成绩】

· · 题解

前情提要 这篇题解是面对从未接触过差分的人写的 嫌啰嗦的直接看楼上或者楼下哈

调差分调了一个半小时码力极弱的OIer来水一发题解......

来自OI-Wiki的差分介绍

差分基本思想：令b[i]=a[i]-a[i-1]

b[i]的含义为a[i]与a[i-1]的差值

这个东西易于在O(1)内维护区间内所有的数加减乘除一个值

实例：将a数组中[l,r]区间内的数字全部加k

设b数组存储差分信息，则易得 将b[l]加上k，然后再将b[r+1]减去k即为想要的结果

Q&A

Q1:为什么是b[l]?

A1:a[l]加k，则a[l]与a[l-1]的差增加k

Q2:那为什么是b[r+1]?

A2:a[r]加k，则a[r]与a[r+1]的差减小k。注意！此时操作的应该是b[r+1]而不是b[r]。

Q3:为什么b[l+1,r]不用更改？

A3:一起增加k，他们之间的差值不变

我是不会告诉你们我调Q2调了半个小时

并且比线段树简单 线段树是这么用的吧我还没学我唔知啊

最后输出只要从头到尾做一遍前缀和就可以了

最后是你们最喜欢的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define N 5000005
using namespace std;
int a[N],b[N];
inline int minx(int a,int b){return a<b?a:b;}
inline int read() //读入优化
{
    int x=0,k=1;char c=getchar();
    while (c<'0'||c>'9'){if (c=='-') k=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*k;
}
int main()
{
    int n,m,test=0,minn=0x7f7f7f7f;
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read(),b[i]=a[i]-a[i-1];
    for (int i=1,x,y,z;i<=m;i++)
    {//此处为差分操作
        x=read();y=read();z=read();
        b[x]+=z;b[y+1]-=z;
    }
    for (int i=1;i<=n;i++) minn=minx(minn,test+b[i]),test+=b[i];
  //前缀和找最小值
    cout<<minn;
    return 0;
}