1.P1438 无聊的数列 - 洛谷 | 计算机科学教育新生态

线段树 + 差分,一开始的思路是直接将整个等差数列加到线段树中,但是pushdown不好维护于是改变思路,想到我们可以去维护a的差分数组,这样一来对[l , r]加上一个首项为看，公差为d的等差数列其实就是在l上加k，[l + 1 ~ r]上加d,之后我们求第p项也转变成求[1 ~ p]的区间和即可，一开始多尝试新思路,不要在困难的思路上折磨自己,多想少code

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;struct node
{int l,r;ll sum,add;
}tr[4 * N];int n,m;
ll a[N],b[N];void pushup(node &u,node &l,node &r)
{u.sum = l.sum + r.sum;
}void pushup(int u)
{pushup(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}void pushdown(node &u,node &l,node &r)
{if(u.add){l.sum += (l.r - l.l + 1) * u.add;r.sum += (r.r - r.l + 1) * u.add;l.add += u.add,r.add += u.add;u.add = 0;}
}void pushdown(int u)
{pushdown(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}void build(int u,int l,int r)
{if(l == r){tr[u] = {l , r , b[l] , 0};}else{tr[u] = {l , r};int mid = (l + r) / 2;build(u << 1 , l , mid);build(u << 1 | 1 , mid + 1 , r);pushup(u);}
}void modify(int u,int l,int r,ll d)
{if(tr[u].l >= l && tr[u].r <= r){tr[u].sum += (tr[u].r - tr[u].l + 1) * d;tr[u].add += d;}else{int mid = (tr[u].l + tr[u].r) / 2;pushdown(u);if(l <= mid){modify(u << 1 , l , r , d);}if(r > mid){modify(u << 1 | 1 , l , r , d);}pushup(u);}
}node query(int u,int l,int r)
{if(tr[u].l >= l && tr[u].r <= r){return tr[u];}else{int mid = (tr[u].l + tr[u].r) / 2;pushdown(u);if(r <= mid){return query(u << 1 , l , r);}else if(l > mid){return query(u << 1 | 1 , l , r);}else{node left = query(u << 1 , l , r);node right = query(u << 1 | 1 , l , r);node res;pushup(res , left , right);return res;}}
}int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i = 1 ; i <= n ; i++){cin>>a[i];b[i] = a[i] - a[i - 1];}        build(1 , 1 , n);while(m--){int op;cin>>op;if(op == 1){ll l,r,d,k;cin>>l>>r>>k>>d;modify(1 , l , l , k);if(r + 1 <= n){modify(1 , r + 1 , r + 1 , - k);}if(r > l){modify(1 , l + 1 , r , d);if(r + 1 <= n){modify(1 , r + 1 , r + 1 , -d * (r - l));}   }}else{int p;cin>>p;cout<<query(1 , 1 , p).sum<<"\n";}}return 0;
}// 5 8
// 1 2 3 4 5
// 1 2 4 1 2
// 1 3 5 4 9
// 1 1 2 1 2
// 2 1
// 2 2
// 2 3
// 2 4
// 2 5// 2 
// 6
// 10
// 22
// 27