题解 P1969 【积木大赛】

qwaszx

2018-02-24 21:32:11

Solution

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