洛谷5026 Lycanthropy 差分套差分

题目链接

　　https://www.luogu.com.cn/problem/P5026

题意

　　在一个长度为m的序列中，每次给一个下标x，和一个权值v，然后从x-v*3到x-v*2单调递增，从x-v*2到x单调递减，从x到x+v*2再次递增，然后x+v*2到x+v*3递减，递增递减都是斜率绝对值为1的直线。

分析

　　刚学了差分趁现在还没忘赶紧把自己想的写下来

　　看到这个其实很容易想到，对于每次修改，将其分为四个区间进行修改，由于它是单调递增的，所以让每个点对应的差分数组加一就行，这样就用到了线段树维护差分数组，但这样还是效率不是很高，我们仍然可以优化，对于同一区间内的每个点与前一个点的差值也是一定的，所以只要修改区间的两端就可以使整个区间内的差值改变，这样两个点的差值就可以构成一个差分数组，然后通过对这个差分数组求前缀和，可以得到每个点与前一个点的差值，再然后更新每个点值的前缀和数组，然后就可以得到这个点的值，输出就行，也就是rt，差分套差分。

　　其实这个挺简单的，仔细想想也  很容易    困难想得出来

　　最后是关于负数的问题，数组下标是不能为负数的，会RE，某大佬的做法是将原点左移，我试了试也是可以的，后来在洛谷上学习了一篇题解的做法，觉得这个很不错，直接用一个指针来代替数组，其实数组的实质也是指针，比如数组aa[10]->从指针aa开始往后数10个，所以只要让一个指针指向数组中间就能实现负下标的数组，感觉挺实用 好玩。

 1 #include<cstdio>
 2 const int N=2e6;//记得开大点，不然会被一些极大的数据RE掉
 3 int aa[N<<1],bb[N<<1];
 4 int main(){
 5     int *a=aa+N,*b=bb+N;
 6     int m,n;
 7     scanf("%d%d",&n,&m);
 8     for(int i=1;i<=n;i++){
 9         int v,x;
10         scanf("%d%d",&v,&x);
11         a[x-v*3+1]++;
12         a[x-v*2+1]-=2;
13         a[x+1]+=2;
14         a[x+v*2+1]-=2;
15         a[x+v*3+1]++;
16     }
17     for(int i=-40000;i<=40000+m;i++)
18         a[i]+=a[i-1],b[i]+=b[i-1]+a[i];
19     for(int i=1;i<=m;i++)
20         printf("%d ",b[i]);
21     return 0;
22 }

小正方形的每个朋友有一个体积数值 $v$，当体积为 $v$ 的一个朋友跳入水中，我们设入水点为 $i$，将会导致 $i-v+1$ 到 $i$ 的水位依次降低 $1,2,\cdots ,v$

同样地，第 $i$ 到 $i+v-1$ 的水位会依次降低 $v,v-1,\cdots ,1$.

相对应地，$i-v$ 的水位不变， $i-v-1$ 到 $i-2\ast v$ 水位依次增加 $1,2,\cdots ,v$， $i-2\ast v$ 到 $i-3\ast v+1$ 水位依次增加 $v,v-1,\cdots ,1$

同样，$i+v$ 水位不变，$i+v+1$ 到 $i+2\ast v$ 水位增加 $1,2,\cdots ,v$，$i+2\ast v$ 到 $i+3\ast v-1$ 水位依次增加 $v,v-1,\cdots ,1$