悬赏5r求调线段树

#include <bits/stdc++.h>
using namespace std;

#define ios_close ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define yes puts("Yes")
#define no puts("No")
#define lowbit(x) (x) & (-x)
#define inf 0x3f3f3f3f
#define endl "\n"
#define PII pair<int, int>
typedef long long LL;

const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int n, m;
LL a[N];

/*====================*/

struct MatrixValu
{
	LL M[3][2];
	MatrixValu()
	{
		memset(M, 0, sizeof M);
	}
	friend MatrixValu operator + (const MatrixValu& a, const MatrixValu& b)
	{
		MatrixValu c;
		for (int i = 1; i <= 2; i++)
			for (int j = 1; j <= 1; j++)
				c.M[i][j] = (a.M[i][j] % MOD + b.M[i][j] % MOD) % MOD;
		return c;
	}
};

struct Tree
{
	int l, r;
	MatrixValu valu;
} tree[N << 2];

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }

void PushUp(int p)
{
	tree[p].valu = tree[ls(p)].valu + tree[rs(p)].valu;
}

void Build(int p, int l, int r)
{
	tree[p].l = l; tree[p].r = r;
	if (tree[p].l == tree[p].r)
	{
		tree[p].valu.M[1][1] = a[l] % MOD;
		tree[p].valu.M[2][1] = ((a[l] % MOD) * (a[l] % MOD)) % MOD;
	}
	else
	{
		int mid = (tree[p].l + tree[p].r) >> 1;
		Build(ls(p), l, mid + 0);
		Build(rs(p), mid + 1, r);
		PushUp(p);
	}
}

void Change(int p, int x, int k)
{
	if (tree[p].l == tree[p].r)
	{
		tree[p].valu.M[1][1] = k % MOD;
		tree[p].valu.M[2][1] = ((k % MOD) * (k % MOD)) % MOD;
	}
	else
	{
		int mid = (tree[p].l + tree[p].r) >> 1;
		if (x <= mid)Change(ls(p), x, k);
		if (x > mid) Change(rs(p), x, k);
		PushUp(p);
	}
}

LL Ask(int p, int l, int r, bool f)
{
	if (l <= tree[p].l && tree[p].r <= r)
	{
		return f ? tree[p].valu.M[1][1] % MOD : tree[p].valu.M[2][1] % MOD;	// 1: 区间和 0: 平方和
	}
	else
	{
		LL res = 0;
		int mid = (tree[p].l + tree[p].r) >> 1;
		if (l <= mid)(res += Ask(ls(p), l, r, f) % MOD) %= MOD;
		if (r > mid) (res += Ask(rs(p), l, r, f) % MOD) %= MOD;
		return res % MOD;
	}
}

LL qpow(int a, int b, int p)
{
	if (!b)	return 1;
	if (b % 2 == 0)
	{
		LL t = qpow(a, b / 2, p) % p;
		return ((t % p) * (t % p)) % p;
	}
	LL t = qpow(a, b - 1, p) % p;
	return ((t % p) * (a % p)) % p;
}

/*====================*/

void Solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i]; a[i] %= MOD;
	}
	Build(1, 1, n);
	while (m--)
	{
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1)
		{
			Change(1, x, y);
		}
		else
		{
			LL inv = qpow(y - x + 1, MOD - 2, MOD) % MOD;
			LL res1 = Ask(1, x, y, 0) % MOD;	// 平方和
			LL res2 = Ask(1, x, y, 1) % MOD;	// 区间和
			LL ave = ((inv % MOD) * (res2 % MOD)) % MOD; // 平均数
			// cout << "inv: " << inv << " res1: " << res1 << " res2: " << res2 << " ave: " << ave << endl;
			LL ans = (((inv % MOD) * (res1 % MOD)) % MOD - ((ave % MOD) * (ave % MOD)) % MOD + MOD) % MOD;
			cout << ans << endl;
		}
	}
	return;
}

/*====================*/

signed main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios_close;
	int _ = 1; // cin >> _;
	while (_--)
		Solve();
	return 0;
}