P1438 无聊的数列
代码得了十分甚至九分but找不到错(
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int a[N], n, m;
struct TreeNode {
int l, r, sum, tag=0;
} tr[N<<2];
void build (int p, int l, int r) {
tr[p].l = l;
tr[p].r = r;
if (l == r) {
tr[p].sum = a[l];
return;
}
int mid = l+r>>1;
build (p<<1, l, mid);
build (p<<1|1, mid+1, r);
tr[p].sum = tr[p<<1].sum + tr[p<<1|1].sum;
}
void pushdown (int p) {
if(tr[p].tag) {
int mid = tr[p].l+tr[p].r>>1, le = p<<1, ri = p<<1|1;
tr[le].sum += tr[p].tag*(mid-tr[p].l+1);
tr[ri].tag += tr[p].tag*(tr[p].r-mid);
tr[le].tag += tr[p].tag;
tr[ri].tag += tr[p].tag;
tr[p].tag = 0;
}
}
void add (int p, int x, int y, int z) {
if (x <= tr[p].l && tr[p].r <= y) {
tr[p].tag += z;
tr[p].sum += (tr[p].r-tr[p].l+1)*z;
return;
}
pushdown (p);
int mid = tr[p].l+tr[p].r>>1;
if (x <= mid) add (p<<1, x, y, z);
if (y > mid) add (p<<1|1, x, y, z);
tr[p].sum = tr[p<<1].sum + tr[p<<1|1].sum;
}
int query (int p, int x, int y) {
if (x <= tr[p].l && tr[p].r <=y) return tr[p].sum;
int mid = tr[p].l+tr[p].r>>1;
int ans = 0;
pushdown (p);
if (x <= mid) ans += query(p<<1 ,x, y);
if (y > mid) ans += query(p<<1|1, x, y);
return ans;
}
signed main() {
scanf ("%lld%lld", &n, &m);
for (int i=1; i<=n; i++) {
scanf ("%lld", &a[i]);
}
for (int i=n-1; i>0; i--) {
a[i+1] = a[i+1]-a[i];
}
build (1, 1, n);
for (int i=1; i<=m; i++) {
int mode;
scanf ("%lld", &mode);
if(mode == 1) {
int l, r, k, d;
scanf ("%lld%lld%lld%lld", &l, &r, &k, &d);
add (1, l, l, k);
if(l+1 <= r) add (1, l+1, r, d);
if(r<n) add (1, r+1, r+1, -(k+d*(r-l)));
} else {
int t;
scanf ("%lld", &t);
printf ("%lld", query (1, 1, t));
}
}
}
线段树还是太难了