Luogu1438|Luogu1438 无聊的数列（线段树） Luogu1438无聊的数列（线段树）

传送门：https://www.luogu.org/problem/P1438
线段树板子题，
真的裸，
数学题真好磕
如果看到加上等差数列还想不到差分的话我也没话可说了……

#include using namespace std; const int N = 100050; typedef long long ll; #define fr(i,n) for(int i = 1; i <= n; i++) #define pr(n) printf("%d\n",n) inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x * f; } int n,m; int s[N], tag[N<<2]; int sum[N<<2]; void pushup(int u) { sum[u] = sum[u << 1] + sum[u << 1 | 1]; }void buildTree(int u, int uL, int uR) { if(uL == uR) { scanf("%lld",&sum[u]); return ; } int mid = (uL + uR) >> 1; buildTree(u << 1, uL,mid); buildTree(u << 1 | 1, mid + 1,uR); pushup(u); }void update(int u, int uL, int uR, int mx) { tag[u] += mx; sum[u] += (ll)(uR - uL + 1) * mx; }void pushdown(int u, int uL, int uR) { if(tag[u]){ int mid = (uL + uR) >> 1; update(u << 1, uL, mid, tag[u]); update(u << 1|1, mid + 1,uR, tag[u]); tag[u] = 0; } }void modify(int u, int uL, int uR, int mL, int mR, int mx) { if(mL <= uL && mR >= uR) { update(u,uL,uR,mx); return; } pushdown(u,uL,uR); int mid = (uL + uR) >> 1; if(mL <= mid) modify(u << 1, uL, mid, mL, mR, mx); if(mid < mR) modify(u << 1 | 1, mid + 1, uR, mL,mR, mx); pushup(u); }ll query(int u, int uL, int uR, int mL, int mR) { if(mL <= uL && mR >= uR)return sum[u]; pushdown(u, uL, uR); int mid = (uL + uR) >> 1; ll ans = 0; if(mL <= mid) ans += query(u << 1, uL, mid, mL, mR); if(mid < mR) ans += query(u << 1 | 1, mid + 1, uR, mL, mR); return ans; }
//------------------------------------------------以上是板子---------------------------------- int main() { int l,r,opt,k,d,n,m,aim; n = read(); m = read(); fr(i,n) s[i] = read(); while(m--){ opt = read(); if(opt == 1){ //1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。 l = read(),r = read(),k = read(),d = read(); modify(1,1,n,l,l,k); if(r > l) modify(1,1,n,l+1,r,d); int N = r - l + 1; if(r != n) modify(1,1,n,r+1,r+1,-(k+(N-1)*d)); } else { aim = read(); pr(s[aim] + query(1,1,n,1,aim)); } } return 0; }

【Luogu1438|Luogu1438 无聊的数列（线段树）】转载于:https://www.cnblogs.com/phemiku/p/11630562.html