主题

主题

 
   

2633. [HZOI 2016]数列操作e

原题:http://cogs.pro/cogs/problem/problem.php?pid=2633

【题目描述】

一个长度为n的序列,一开始序列数的权值都是0,有m次操作

支持两种操作,

1 L R x,给区间[L,R]内,第一个数加x,第二个数加2^2⋅x,第三个数加3^2⋅x...第R-L+1个数加(R−L+1)^2⋅x

2 L R 查询区间[L,R]内的权值和

每次询问的答案对2^64取模

【输入格式】

第一行两个数n,m,表示序列长度和操作次数

接下来m行,每行描述一个操作,有如下两种情况:

1 L R x,给区间[L,R]内,第一个数加x,第二个数加2^2⋅x,第三个数加3^2⋅x...第R-L+1个数加(R−L+1)^2⋅x

2 L R 查询区间[L,R]内的权值和

【输出格式】

为了减少输出,你只需要输出所有答案对264取膜之后的异或和。

【样例输入】

5 5

1 3 4 1

2 1 5

2 2 2

1 3 3 1

1 2 4 1

【样例输出】

5

【提示】

对于10%的数据 n,m<=2000

对于30%的数据 n,m<=10000

对于100%的数据,n,m<=100000,1<=L<=R<=n,0<=x<=10^9


个人解法:

事实上是A[i]+=w*(i-l+1)^2

那我们把加法拆分一下,大概是+=w*((i^2)+2*i*(1-l)+(l-1)^2)

利用线段树分别维护三种值,令A[i]=x+y*i+z*i^2,分别维护三种区间和即可。

更新也挺方便的。


代码如下:

https://code.csdn.net/snippets/2308586

 
 
评论