题解 P1969 【积木大赛】
qwaszx
2018-02-24 21:32:11
qwq为什么没有差分题解啊
一般区间操作首先要想差分————yql
差分是个啥?
△f=f(x+1)-f(x),就像微积分,但把增量换成了1,也叫有限微积分
这里定义差分f[i]=h[i]-h[i-1],i=1...n+1,h[0]=0,h[n+1]=0.
容易知道f中正值之和等于负值之和的绝对值
Σf[i]=Σh[i]-h[i-1]=h[n+1]-h[0]=0,得证.
于是我们可以猜ans=正值之和
证明?
如果f[i]为正,容易知道我们要往这一摞上搭积木,所以ans+=h[i]-h[i-1]=f[i]
如果f[i]为负,可以在之前搭的时候一起搭上去,所以ans不变
当然这可以通过其他方式省去数组,但差分有更多的用途
考虑区间加
在a(原数组,下同)上表现为i=l...r,a[i]+=w;
而在f数组上的表现则为f[l]+=w,f[r+1]-=w.
证明自己yy一下就好,很容易
于是这东西可以O(1)修改
可以推广到二维和树上,区间乘法应该也可以???适用于多询问少修改的题
然后今天有一道毒瘤题要求区间翻转+区间加+带负值积木大赛+查询历史版本
于是可以差分做
------------
考虑翻转之后的f
对于l+1~r+1,可以取反然后翻转
对于l和r,暴力处理一下即可
丢到平衡树上就好了
历史版本加上一个操作树就好
没有强制在线就不需要持久化
------------
到这是yql原话反正我没怎么听懂orz
最后回到这个题上来233
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int c[110000],n,ans=0;
inline int getin()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x;
}
inline int max(int a,int b)
{
if(a>b)return a;return b;
}
int main()
{
n=getin();
for(register int i=1;i<=n;i++)
c[i+1]=-getin(),c[i]-=c[i+1],ans+=max(c[i],0);
printf("%d",ans);
}
```
4ms...慢的要死,可以自己再卡卡常数
区间的话分块O(nsqrt(n))/线段树(nlogn)啥的都能做
我这么菜不会别的233