K - Krystalova‘s Trivial Problem （lazytag线段树）

需要一个带有lazytag的线段树，维护一下区间和，和区间平方和。对于每一次加x的操作，假设原区间平方和是 ,对于加完x后的操作后， 原序列变为

 拆开后合并同类项,我们可以根据最后一个式子来区间维护这个区间平方和。

ACcode 

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 250;
const int mod = 1e9 + 7;
int a[N];
int n, m;
struct node
{int l, r;int lz;int sum;int v;
} t[N * 4];
void pushup(int p)
{t[p].sum = (t[p << 1].sum % mod + t[p << 1 | 1].sum % mod) % mod;t[p].v = (t[p << 1].v % mod + t[p << 1 | 1].v % mod) % mod;
}void pushdown(int p)
{if (t[p].lz != 0){int tt = t[p].lz%mod;t[p << 1].lz = (t[p << 1].lz + t[p].lz) % mod;t[p << 1 | 1].lz = (t[p << 1 | 1].lz + t[p].lz) % mod;t[p << 1].v = (t[p << 1].v % mod + 2ll * tt % mod * t[p << 1].sum % mod + (t[p << 1].r - t[p << 1].l + 1ll) * tt % mod * tt % mod+mod) % mod;t[p << 1 | 1].v = (t[p << 1 | 1].v % mod + 2ll * tt % mod * t[p << 1 | 1].sum % mod + (t[p << 1 | 1].r - t[p << 1 | 1].l + 1) * tt % mod * tt % mod+mod) % mod;t[p << 1].sum = (t[p << 1].sum % mod + tt * (t[p << 1].r - t[p << 1].l + 1) % mod+mod) % mod;t[p << 1 | 1].sum = (t[p << 1 | 1].sum % mod + tt * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1ll) % mod+mod) % mod;t[p].lz = 0;}
}void build(int p, int l, int r)
{t[p] = {l, r, 0, 0, 0};if (l == r){t[p].sum = a[l] % mod;t[p].v = a[l] * a[l] % mod;return;}int mid = l + r >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);
}void modify(int p, int l, int r, int x)
{if (t[p].l >= l && t[p].r <= r){t[p].v = (t[p].v % mod + 2ll * x * t[p].sum % mod + (t[p].r - t[p].l + 1ll) * x % mod * x % mod) % mod;t[p].sum = (t[p].sum % mod + (t[p].r - t[p].l + 1ll) * x % mod) % mod;t[p].lz = (t[p].lz % mod + x % mod) % mod;return;}pushdown(p);if (t[p << 1].r >= l)modify(p << 1, l, r, x);if (t[p << 1 | 1].l <= r)modify(p << 1 | 1, l, r, x);pushup(p);
}
int query(int p, int l, int r)
{if (t[p].l >= l && t[p].r <= r){return t[p].v % mod;}pushdown(p);int res = 0;if (t[p << 1].r >= l)res = (res % mod + query(p << 1, l, r) % mod+mod) % mod;if (t[p << 1 | 1].l <= r)res = (res % mod + query(p << 1 | 1, l, r) % mod+mod) % mod;pushup(p);return res % mod;
}void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];a[i] % mod;}build(1, 1, n);while (m--){char op[10];cin >> op;if (op[0] == 'u'){int l, r, x;cin >> l >> r >> x;modify(1, l, r, x);}else{int l, r;cin >> l >> r;cout << (query(1, l, r)%mod+mod)%mod << endl;}}
}signed main(void)
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！