\(\color{red}{\mathcal{Description}}\)
给你一个数列，要求支持单点查询\(and\)区间加等差数列。
\(\color{red}{\mathcal{Solution}}\)
哈哈哈哈这个题十分的有意思，至于为什么有意思等会儿再说~
其实我们观察这两个操作，单点查询……就是那个\(naive\)的单点查询，那么区间加等差数列呢？我们可以思考一下等差数列的性质——存在公差。不妨考虑差分
\(emmm\)发现我好像还没有在博客园里提过差分……那么就整一整吧正好我好久没捯饬这玩意儿了\(qwq\)
差分
其实就是对于一个给定的数列\(base\)，我们用另一个数组\(dif_i\)记录\(base_i - base_{i - 1}\)，从而我们可以通过\(dif\)反向得到$$base_i = \sum_{j = 1}^{i}{dif_j}$$呐，我们如果有区间加减这种操作或者其他的，我们可以通过操作\(dif_i\)和\(dif_{j + 1}\)来起到对区间\(i\)~\(j\)打标记的作用。关键就是一定要是单点查询……区间查询仿佛也可以做？但是有点麻烦略略略。
回到这个题，我们的线段树可以建在数列的差分数组上。然后区间加等差数列的时候，我们就让\(dif_L += D\)，\(dif_{L+1...R} += K\)，\(dif_{R+1} -= (K \times (R - L) + D)\)很显然。如果要是区间查询的话，我们就直接线段树求个$$ans = \sum_{i = 1}^{P}{dif_i}$$但是在程序实现的时候，笔者在此偷了个懒，没有初始化\(dif\)数组，那么我们就需要在区间查询的时候改成这样$$ans = \sum_{i = 1}^{P}{dif_i} + base_P$$
\(Code\)
#include <cstdio>
#include <iostream>
#define mid ((l + r) >> 1)
using namespace std ;
const int MAXN = 100050 ;
int N, M, P, mark, i, base[MAXN] ;
int L, R, K, D, dif[MAXN << 2], tag[MAXN << 2] ;
inline int qrd(){
int k = 0, f = 1 ; char c = getchar() ;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar() ;}
while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k * f ;
}
inline void p_u(int rt){dif[rt] = dif[rt << 1] + dif[rt << 1 | 1] ;}
inline void p_d(int rt, int l, int r){
if(tag[rt]){
dif[rt << 1] += tag[rt] * (mid - l + 1) ;
dif[rt << 1 | 1] += tag[rt] * (r - mid) ;
tag[rt << 1] += tag[rt] ;
tag[rt << 1 | 1] += tag[rt] ;
tag[rt] = 0 ;
}
}
void update(int rt, int l, int r, int ul, int ur, int k){
if(ul <= l && r <= ur){
tag[rt] += k ;
dif[rt] += k * (r - l + 1) ;
return ;
}p_d(rt, l, r) ;
if(ul <= mid) update(rt << 1, l, mid, ul, ur, k) ;
if(ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, k) ;
p_u(rt) ;
}
int query(int rt, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){return dif[rt] ;}p_d(rt, l, r) ;
int res = 0 ;
if(ql <= mid) res += query(rt << 1, l, mid, ql, qr) ;
if(qr > mid) res += query(rt << 1 | 1, mid + 1, r, ql, qr) ;
return res ;
}
int main(){
N = qrd(), M = qrd() ;
for(i = 1; i <= N; i ++) base[i] = qrd() ;
for(i = 1; i <= M; i ++){
cin >> mark ;
if (mark == 1) {
L = qrd(), R = qrd(), K = qrd(), D = qrd() ;
update(1, 1, N, L, L, K) ;
if (R > L) update(1, 1, N, L + 1, R, D) ;
if (R != N) update(1, 1, N, R + 1, R + 1, -(R - L) * D - K) ;
}
else {
P = qrd() ;
cout << base[P] + query(1, 1, N, 1, P) << endl ;
}
}
}
\(upd:\)诶我好像是忘记说哪里好玩儿了……
这个题前不久\(qyf\)给我们讲的时候忘记怎么做了，然后在经过讨论之后，觉得wx的想法不错，于是当时就奉为了正解。当时的想法好像是在\(base\)上建一棵线段树，push_down的时候我们记录一下两个子区间的第一个元素应该加多少&公差，整个区间暴力加和。
现在想想吧……好像好麻烦的样子……并且因为它是单点查询，中间维护那么多次区间和根本没必要……复杂度的话…也是\(nlogn\)?应该是吧……但是好像很蠢的样子qwq
啊……真怀念当时啊……