[BJOI2018] 链上二次求和
时间限制:4000MS 内存限制:131072KB
难度:\(6.2\)
-
题目描述
YJC 有一棵 \(n\) 个节点的树, \(i\)、\(i+1\) (\(1 \leq i < n\))节点间有一条边,第 \(i\) 个点的权值为整数 \(a_i\) 。
现在他有 \(m\) 个询问:
操作 \(1\)(修改):给定树上两个节点 \(u\)、\(v\) 和一个整数 \(d\),表示将树上 \(u\) 到 \(v\) 唯一的简单路径上每个点权值都加上 \(d\)。
操作 \(2\)(询问):给定两个正整数 \(l\)、\(r\) ,表示求树上所有节点个数大于等于 \(l\) 且小于等于 \(r\) 的简单路径节点权值和之和。由于答案很大,只用输出对质数 \(1000000007\) 取模的结果即可。
一条节点个数为 \(k\) 的简单路径节点权值和为这条上所有 \(k\) 个节点(包括端点)的权值之和,而本题中要求是对所有满足要求的简单路径,求这一权值和的和。
树边是无向的,所以路径也是无向的,即点 \(1\) 到点 \(2\) 的路径与点 \(2\) 到点 \(1\) 的路径是同一条,不要重复计算。
-
输入格式
输入第一行包含两个正整数 \(n\)、\(m\),分别表示节点个数和操作次数。
第二行包含 \(n\) 个整数,其中第 \(i\) 个数 \(a_i\) 为第 \(i\) 个点的初始权值。
接下来 \(m\) 行,每行为 1 u v d 或 2 l r 的形式,分别表示进行一次操作 \(1\)(修改)或操作 \(2\)(询问)。
-
输出格式
对于每次询问,输出一行一个整数,表示答案对 \(1000000007\) 取模的余数。
-
样例输入
1 2 3 4 5 6 7 |
5 5 1 1 1 1 1 2 5 5 2 1 2 1 1 2 2 2 1 1 1 1 5 3 |
-
样例输出
1 2 3 |
5 13 9 |
-
样例说明
节点个数为 \(5\) 的简单路径只有 \(1\) 条,权值和为 \(5\),故第一次询问输出 \(5\) 。
节点个数为 \(1\) 的简单路径有 \(5\) 条,每条权值和都是 \(1\);节点个数为 \(2\) 的简单路径有 \(4\) 条,每条权值和都是 \(2\),故第二次询问输出 \(13\) 。
在将点 \(1\) 和点 \(2\) 的权值加 \(2\) 后, \(5\) 条节点个数为 \(1\) 的简单路径权值和分别为 \(3\)、\(3\)、\(1\)、\(1\)、\(1\) ,故第三次询问输出 \(9\) 。
-
数据规模与约定
记操作 \(1\)(修改)的次数为 \(m’\)。
对于全部数据, 保证 \(n \leq 200000, m \leq 500000, m’ \leq 100000, 0 \leq a_i < 1000000007\),
\(1 \leq u \leq n, 1 \leq v \leq n, 0 \leq d < 1000000007, 1 \leq l \leq r \leq n\)。
测试点 | \(n \leq\) | \(m \leq\) | \(m’ \leq\) | 约束 |
---|---|---|---|---|
1 | \(50\) | 无 | ||
2 | ||||
3 | \(300\) | |||
4 | ||||
5 | \(5000\) | \(5000\) | \(5000\) | |
6 | \(5 \times 10^5\) | |||
7 | ||||
8 | \(10^5\) | |||
9 | \(2 \times 10^5\) | \(1\) | \(0\) | 保证 \(l=1, r=n\) |
10 | \(5 \times 10^5\) | 无 | ||
11 | \(10^5\) | 保证 \(u=v\) | ||
12 | 保证 \(l=1, r=n\) | |||
13 | 保证 \(u=1, v=n, a_i=0\) | |||
14 | 保证 \(u=1, v=n\) | |||
15 | 保证 \(d=1, a_i=0\) | |||
16 | 保证 \(d=1\) | |||
17 | 保证 \(a_i=0\) | |||
18 | ||||
19 | 无 | |||
20 |
加强版:YZOJ P4611 区间加多项式(YJC 的数组/多项式?)
标题 = 正解 系列(
询问的这个很奇怪的东西它其实是 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n {\sum\limits_{j=i-k+1}^i a_j}}\) 。
好复杂,记 \(A_i = \displaystyle\sum\limits_{j=1}^i a_j\) 即 \(a_i\) 的前缀和,那么变成 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n {\left(A_i – A_{i-k}\right)}}\) 。
拆开,变成 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n A_i – \sum\limits_{i=0}^{n-k}A_i}\) 。
还是好复杂,再记 \(B_i = \displaystyle\sum\limits_{j=1}^i A_j\) 即 \(A_i\) 的前缀和,那么变成 \(\displaystyle\sum\limits_{k=l}^r {\left(B_n – B_{k-1} – B_{n-k}\right)}\) 。
拆开,变成 \(\displaystyle \left(r-l+1\right)B_n – \sum\limits_{i=l-1}^{r-1} B_i – \sum\limits_{i=n-r}^{n-l} B_i\) 。
于是发现可以用 线段树/树状数组 维护 \(B_i\) ,现在考虑修改如何操作。
在 \(a\) 上区间加常数,变成在 \(A\) 上区间加一次函数,变成在 \(B\) 上区间加二次函数。
可以随便手推一下式子:设 \(\mbox{len}=r-l+1\) ,
对于 \(l \leq i \leq r\),有 \(B_i \mathrel{+}= \displaystyle\frac{\left(i-l+1\right)\left(i-l+2\right)}{2}d\) ;
对于 \(r < i \leq n\),有 \(B_i \mathrel{+}= \displaystyle\frac{\mbox{len}\left(\mbox{len}+1\right)}{2}d + \mbox{len}\left(i-r\right)d\) 。
线段树 分别维护各次项系数(标记永久化 \(>\) 打 \(\mbox{tag}\)),区间修改/区间查询 即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #define MOD 1000000007 #define INV2 500000004 #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } typedef long long LLONG; int sum[605050],tag[605050][3]; struct _lson{ inline int operator[](const int&idx){return idx<<1;} }lson; struct _rson{ inline int operator[](const int&idx){return (idx<<1)|1;} }rson; int _ps0[205050],_ps1[205050],_ps2[205050]; #define PowerSum(_arr,_l,_r) ((_arr)[_r]-(_arr)[_max((_l)-1,0)]) #define PointAns(_tag,_l,_r) ((((LLONG)(_tag)[0]*PowerSum(_ps0,_l,_r)+ \ (LLONG)(_tag)[1]*PowerSum(_ps1,_l,_r)+ \ (LLONG)(_tag)[2]*PowerSum(_ps2,_l,_r))%MOD+MOD)%MOD) int _Qret,QL,QR; void QueryTree(register int o,register int l,register int r) { if(QL<=l && QR>=r) { (_Qret+=sum[o])%=MOD; return; } register int mid=(l+r)>>1; if(QL<=mid) QueryTree(lson[o],l,mid); if(QR>mid) QueryTree(rson[o],mid+1,r); (_Qret+=PointAns(tag[o],_max(l,QL),_min(r,QR)))%=MOD; } int ML,MR,MV[3]; void ModifyTree(register int o,register int l,register int r) { if(l>=ML && r<=MR) { (sum[o]+=PointAns(MV,l,r))%=MOD; #define _pltag(_i) ((tag[o][_i]+=MV[_i])%=MOD) _pltag(0),_pltag(1),_pltag(2); return; } register int mid=(l+r)>>1; if(ML<=mid) ModifyTree(lson[o],l,mid); if(MR>mid) ModifyTree(rson[o],mid+1,r); sum[o]=(sum[lson[o]]+sum[rson[o]]+PointAns(tag[o],l,r))%MOD; } int a[205050]; void BuildTree(register int o,register int l,register int r) { if(l==r) { sum[o]=a[l]; return; } register int mid=(l+r)>>1; BuildTree(lson[o],l,mid),BuildTree(rson[o],mid+1,r); sum[o]=(sum[lson[o]]+sum[rson[o]])%MOD; } int main() { register int N=getnum(),M=getnum(); for(register int i=1;i<=N;i++) a[i]=(a[i-1]+getnum())%MOD, _ps0[i]=_ps0[i-1]+1,_ps1[i]=(_ps1[i-1]+i)%MOD, _ps2[i]=(_ps2[i-1]+(LLONG)i*i)%MOD; for(register int i=2;i<=N;i++) (a[i]+=a[i-1])%=MOD; BuildTree(1,0,N); for(register int lp=1;lp<=M;lp++) { register int opt=getnum(),l=getnum(),r=getnum(); if(l>r) l^=r^=l^=r; if(opt==1) { register int x=getnum(),xt=(LLONG)x*INV2%MOD; MV[2]=xt; MV[1]=(LLONG)(3-(l<<1)+MOD)*xt%MOD; MV[0]=(LLONG)(1-l)*(2-l)%MOD*xt%MOD; ML=l,MR=r,ModifyTree(1,0,N); MV[2]=0; MV[1]=(LLONG)(r-l+1)*x%MOD; MV[0]=(LLONG)(r-l+1)*(2-l-r+MOD)%MOD*xt%MOD; if(r+1<=N) ML=r+1,MR=N,ModifyTree(1,0,N); } else { register int ans=0; _Qret=0,QL=N,QR=N,QueryTree(1,0,N); ans=(LLONG)_Qret*(r-l+1)%MOD; _Qret=0,QL=l-1,QR=r-1,QueryTree(1,0,N); QL=N-r,QR=N-l,QueryTree(1,0,N); ans=(ans-_Qret+MOD)%MOD; printf("%d\n",ans); } } return 0; } |