题解 P4458 【[BJOI2018]链上二次求和】

话说凌晨终于卡完这道题的常数的时候真的有一股松爷附体的感觉…… 第一次感觉到了信仰的力量…… 另外这道题说的是链加，其实就是区间加，但是要注意的一点是因为是唯一路径，所以l，r可以是反的……如果一直在WA可以注意一下…… _________________________ # 这道题可以使用根号算法通过 ## 本题题解 这道题乍一看是个线段树题……，因为区间加什么的本来就有非常好的性质可以让我们使用线段树维护它，但是由于询问十分鬼畜(所有长度在l,r的连续子段和的和)，因此我们发现线段树并不是非常的好处理修改和询问的关系…… 但是注意到询问的时候总是询问了一段连续的长度区间，所以我们可以考虑把所有答案变成一个序列$\{a\}$,其中$a_{i}$表示长度恰好为i的连续子段和的和，那么我们的询问操作就变成了询问a序列的区间和，此时我们发现在原序列上的区间加将会引起a数组一系列复杂的变化……，这样线段树其实就不是非常的好做了 (情况开始变得辣手) 那么此时让我们来想两个具有启发意义的$O(n^2)$暴力 ### 暴力1 如果所有询问在修改之后呢？ 通过将原数组差分，我们可以$O(1)$的记录下每个修改 然后在所有修改结束之后我们可以$O(n)$的对差分数组做一遍前缀和从而还原出原序列，此时我们希望可以快速的处理出答案序列$a$这样的话我们就可以对a数组做一遍前缀和，从而$O(1)$的回答每个区间询问了 那么我们暴力的枚举左端点来求$a_{i}$应该可以得到这样一个式子,其中sum_{i}表示原数组的前缀和数组 ## $a_{i}=\sum_{j=0}^{n-i}sum_{j+i}-sum{j}$ 拆开Σ可以得到 ## $a_{i}=\sum_{j=i}^{n}sum_{j}-\sum_{j=0}^{n-i}sum{j}$ 发现我们对前缀和数组再做一遍前缀和就可以$O(1)$的计算出$a_{i}$ 此时我们$O(n)$的计算出所有的$a_{i}$就可以$O(n)$的计算出$a_{i}$的前缀和 然后此时我们就可以O(n)的计算出前缀和了，然后$O(1)$回答每个询问即可 对于每个修改我们都重复一遍刚才的流程，算法复杂度$O(n^2)$显然会T飞 ### 暴力2 如果修改很少呢？当然我们可以使用刚才的算法，但是我们注意到这里还有另外一个暴力，我们可以考虑每一个修改对当前的贡献，这样的话我们处理修改的时候暴力的扫一遍之前的所有的修改，累加所有的贡献就是答案了 我们假设在原数组的某个点i加1，那么我们观察答案数组a的一位j会变化多少 我们令$C_{i,j}$表示点i加1的时候答案数组的第j位的变化量 那么我们把C这个方阵打出来之后大概长这样 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 1 2 3 4 4 3 1 1 2 3 4 4 3 1 1 2 3 3 3 3 1 1 2 2 2 2 2 1 1 1 1 1 1 1 1 大概就是最外边一圈是一圈1，里面是一圈2，再里面是一圈3……这样的规律 那么我们考虑我们一个修改(l1,r1,delta)对询问(l2,r2)的贡献的时候，我们会发现这其实就是我们这个C矩阵在(l1,l2)(r1,r2)这个子矩阵的权值和再去乘上一个delta 感性理解以下就是我们把这个区间加操作看成单点加的集合，然后考虑每一个单点加对这个询问区间的贡献，然后发现这就是这个贡献矩阵的子矩阵之和乘上修改的权值delta了 所以我们会自然的想到这样一个暴力，对于每一个询问，我们暴力的考虑在它之前的询问对他的贡献，对于最开始的序列，我们直接处理出静态的解 问题来了，我们如何$O(1)$的求出这个系数矩阵的和呢？ 我们首先发现这个矩阵是中心对称的，因此可以把这个子矩阵矩阵切成4块，每块按照右上角的方阵的形式来算 那么问题来了，如何快速求出右上角的一个子矩阵的和呢？ 我们发现这个子矩阵的和并不是非常的好算，因此我们考虑可不可以快速的求出这个1/4方阵的二维前缀和，这样就可以快速计算出这个矩阵的子矩阵和了 那么我们不妨设这个1/4方阵的第N行第M列的二维前缀和为$F_{N,M}$，既然要求二位前缀和我们就需要了解一下第i行第j列的元素是什么，通过大胆推结论我们可以得到这个元素就是min(i,j) 所以我们发现$F_{N,M}$就是 ## $\sum_{i=1}^{N}\sum_{j=1}^{M}min(i,j)$ 我们不妨设M<N，那么我们可以把式子拆成这个样子 ## $\sum_{i=1}^{M}\sum_{j=1}^{M}min(i,j)+\sum_{i=M+1}^{N}\sum_{j=1}^{M}min(i,j)$ 然后因为min运算具有结合律，我们可以采取一个非常传统的操作，将类似于方阵的Σ形式只算一个三角部分然后乘2，最后减去对角线部分，这样我们的式子就变成了这样 ### $2\sum_{i=1}^{M}\sum_{j=1}^{i}min(i,j)-\sum_{i=1}^{M}min(i,i)+\sum_{i=M+1}^{N}\sum_{j=1}^{M}min(i,j)$ 然后发现3个Σ当中的j均小于i，所以min运算就被消掉了 ## $2\sum_{i=1}^{M}\sum_{j=1}^{i}j-\sum_{i=1}^{M}i+(N-M)\sum_{j=1}^{M}j$ 然后我们令$F_{1}(i)=\sum_{j=1}^{i}j$,$F_{2}(i)=\sum_{j=1}^{i}F_{1}(j)$ 显然这两个函数都是非常好预处理或者直接利用数学公式计算的 那么我们发现最后$F(N,M)$是这样的 ## $F_(N,M)=2F_{2}(M)+(N-M-1)F_{1}(M)$ 至此，我们可以$O(1)$的计算前缀和了，因此我们就可以在常数事件内完成这个求子矩阵和的工作 但是到现在为止，我们只是有两个看似并无卵用的$O(n^2)$暴力，所以我们接下来要如何优化这些基本已经没有优化空间的暴力，从而让我们过掉这个$N=2×10^5,m'<10^5,m<5×10^5$的鬼畜数据呢？ ## 定期重构 对，我们直接用暴力来优化暴力，当一道题有两个不同的$O(n^2)$暴力时，我们可以通过将这两个暴力结合到一起来创造一个优秀的$O(n\sqrt{n})$的暴力算法 我们发现这道题的修改操作并不是非常的多，因此我们可以使用差分数组$O(1)$的记录下每一个修改，同时将它们惰性的push到一个栈当中，每次询问的时候先使用答案数组得到一个静态的解，然后暴力的扫一遍这个栈，查询每个修改对询问的贡献，如果在一次询问开始前，发现我们已经做了超过275次操作，那么清空整个栈，直接暴力重构这个数组 听起来这个东西非常的暴力，我们冷静分析一波复杂度，会发现这个算法的复杂度大概是 $O(363n+275(m-m')+m')$的，然后分析到这里我们也不会觉得这个算法可以通过，因为这个算法实在是太像一个高分暴力了，然而其实它就是一个高分暴力，但是问题是这道题的正解的常数也不小，因此我们可以利用常数这点来成功的卡过去 所以下面要介绍的部分才是这篇乱搞AC题解的重点，卡常数！ ## 卡常数 先解释一下为什么不是每根号m'(即316)次重构一次，而是采用了275这个偏小的数，另外200也可以，但是十分玄学的250并不行 因为我们仔细观察一下我们考虑询问对修改的贡献这个地方的常数，会发现是大于我们重构的复杂度的，因此我们只能尽量多的重构，具体来讲就是倾斜一下我们的重构常数，使得算法向多重构这个方向倾斜 然后我们加上了这个伪优化，发现还是t，事实上这个时候一般会有一个非常大的常数出在取膜运算上，因此我们去掉了重构函数中第一次计算ans值的取膜运算 以及查询子矩阵函数的取膜运算仅做一次，另外我们计算二维前缀和的时候仅仅在使用减法的时候才进行取膜操作，这样的话一次询问最多进行9次取模操作，而原来是21次，这个时候我们的常数就不是非常大了，可以在3600ms左右的时间通过本题 当然了这个写法有一个好处就是代码复杂度极低，全程不需要任何数据结构做支持，只需要几个简单的函数就可以完成实现了 上代码~ ```C #include<cstdio> #include<algorithm> #include<cmath> using namespace std;const int N=2*1e5+10;typedef unsigned long long ll; const ll mod=1e9+7;const int M=200;ll del[N];ll sum[N];ll ans[N];int n;int m;//这里的M采用了200 int ml[N];int mr[N];ll val[N];ll f1[N];ll f2[N];int tp;int mid; inline void rebuild()//重构函数，对差分数组做3遍前缀和，构造ans { for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+del[i])%mod; for(int i=1;i<=n;i++)(sum[i]+=sum[i-1])%=mod; for(int i=1;i<=n;i++)(sum[i]+=sum[i-1])%=mod;//省了一个取膜 for(int i=1;i<=n;i++)ans[i]=sum[n]+mod-sum[i-1]+mod-sum[n-i]; for(int i=1;i<=n;i++)(ans[i]+=ans[i-1])%=mod; } inline ll sqrs(int a,int b)//查询二维前缀和 {if(a<b)swap(a,b);return (a==b)?2*f2[b]+mod-f1[b]:2*f2[b]+(a-b-1)*f1[b];} inline ll subquery(int xl,int xr,int dl,int dr)//1/4矩阵查询，优化两个取膜 {return sqrs(xl,dl)+sqrs(xr,dr)+mod-sqrs(xr,dl)%mod+mod-sqrs(xl,dr)%mod;} inline ll query(int xl,int xr,int dl,int dr)//矩阵查询，切成4份 { //减少了4次取膜运算 ll ret=0;int cxl=n-max(xl,mid);int cxr=min(xr,mid); int cdl=n-max(dl,mid);int cdr=min(dr,mid); if(xl<=mid&&dl<=mid)ret+=subquery(xl,cxr,dl,cdr); if(xl<=mid&&mid<dr)ret+=subquery(xl,cxr,n-dr,cdl); if(mid<xr&&dl<=mid)ret+=subquery(n-xr,cxl,dl,cdr); if(mid<xr&&mid<dr)ret+=subquery(n-xr,cxl,n-dr,cdl); return ret%mod; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)f1[i]=(f1[i-1]+i)%mod;//预处理f数组减少常数 for(int i=1;i<=n;i++)f2[i]=(f2[i-1]+f1[i])%mod; for(int i=1;i<=n;i++)scanf("%lld",&del[i]); for(int i=n;i>=1;i--)(del[i]+=mod-del[i-1])%mod; rebuild();mid=n/2; for(int i=1,t,l,r;i<=m;i++) { scanf("%d",&t); if(t==1)//惰性的加入到栈中 { ++tp;scanf("%d%d%lld",&ml[tp],&mr[tp],&val[tp]); if(ml[tp]>mr[tp]){swap(ml[tp],mr[tp]);}//注意判掉这种情况 (del[ml[tp]]+=val[tp])%=mod;(del[mr[tp]+1]+=mod-val[tp])%=mod;//使用差分数组记录修改 } else { int l;int r;ll ret=0;scanf("%d%d",&l,&r);//先处理出静态的解 if(tp>=M){tp=0;rebuild();}ret=(ans[r]+mod-ans[l-1])%mod; for(int i=1;i<=tp;i++)(ret+=val[i]*query(ml[i]-1,mr[i],l-1,r))%=mod;//暴力考虑修改对询问的贡献 printf("%lld\n",ret); } }return 0;//拜拜程序~ } ```