题目描述：
解题思路：
首先我们化简式子，画出来根号里面为 \(0\)，所以分子是一个区间和，分母经过观察就是 \(n\)。
所以这个式子就是区间的平均值。
但是问题来了我们怎么求 一个区间中所有子区间的平均值的最大值？
这里需要一个结论：只有长度小于等于 \(4\) 的子区间才有用。
证明:两个数的平均值一定小于等于这两个数中的较大值。因为所有长度大于等于 \(2\) 的区间都是有用的，所以一个长度大于等于 \(4\) 的区间一定可以拆分成多个长度小于 \(4\) 的区间。
那么我们用线段树维护长度为 \(2\) 和 \(3\) 的区间的和即可。
修改注意极限情况。
代码实现：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e5 + 10;
int a[N], val[N], sum[N];
struct SegTree{
int maxn[N << 2], tag[N << 2];
void pushup(int op){
int ls = op << 1, rs = op << 1 | 1;
maxn[op] = max(maxn[ls], maxn[rs]);
return;
}
void pushdown(int op){
int ls = op << 1, rs = op << 1 | 1;
if(tag[op] != 0){
maxn[ls] += tag[op], tag[ls] += tag[op];
maxn[rs] += tag[op], tag[rs] += tag[op];
tag[op] = 0;
}
return;
}
void build(int l, int r, int op){
maxn[op] = 0, tag[op] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(l, mid, op << 1);
build(mid + 1, r, op << 1 | 1);
pushup(op);
}
void update(int l, int r, int op, int x, int y, int val){
if(x <= l && r <= y){
tag[op] += val, maxn[op] += val;
return;
}
int mid = (l + r) >> 1;
pushdown(op);
if(mid >= x) update(l, mid, op << 1, x, y, val);
if(mid + 1 <= y) update(mid + 1, r, op << 1 | 1, x, y, val);
pushup(op);
}
int query(int l, int r, int op, int x, int y){
if(x <= l && r <= y) return maxn[op];
int mid = (l + r) >> 1, res = -0x3f3f3f3f3f3f;
pushdown(op);
if(mid >= x) res = max(res, query(l, mid, op << 1, x, y));
if(mid + 1 <= y) res = max(res, query(mid + 1, r, op << 1 | 1, x, y));
pushup(op);
return res;
}
}t, t1;
int n, q;
void solve(){
int op, l, r;
cin >> op >> l >> r;
if(op == 1){
int x; cin >> x;
t.update(1, n + 1, 1, l, l, x);
if(l + 1 <= r) t.update(1, n + 1, 1, l + 1, r, 2 * x);
t.update(1, n + 1, 1, r + 1, r + 1, x);
if(l == r){
t1.update(1, n + 2, 1, l, l + 2, x);
}else if(l + 1 == r){
t1.update(1, n + 2, 1, l, l, x);
t1.update(1, n + 2, 1, r, r + 1, 2 * x);
t1.update(1, n + 2, 1, r + 2, r + 2, x);
}else{
t1.update(1, n + 2, 1, l, l, x);
t1.update(1, n + 2, 1, l + 1, l + 1, 2 * x);
if(l + 2 <= r) t1.update(1, n + 2, 1, l + 2, r, 3 * x);
t1.update(1, n + 2, 1, r + 1, r + 1, 2 * x);
t1.update(1, n + 2, 1, r + 2, r + 2, x);
}
}else{
if(l == r) cout << "1 0 1" << endl;
else if(r == l + 1){
if(t.query(1, n + 1, 1, l + 1, r) % 2 == 0)
cout << "1 " << t.query(1, n + 1, 1, l + 1, r) / 2 << " 1" << endl;
else
cout << "1 " << t.query(1, n + 1, 1, l + 1, r) << " 2" << endl;
}
else if(t.query(1, n + 1, 1, l + 1, r) * 3 > t1.query(1, n + 2, 1, l + 2, r) * 2){
if(t.query(1, n + 1, 1, l + 1, r) % 2 == 0)
cout << "1 " << t.query(1, n + 1, 1, l + 1, r) / 2 << " 1" << endl;
else
cout << "1 " << t.query(1, n + 1, 1, l + 1, r) << " 2" << endl;
}else{
if(t1.query(1, n + 2, 1, l + 2, r) % 3 == 0)
cout << "1 " << t1.query(1, n + 2, 1, l + 2, r) / 3 << " 1" << endl;
else
cout << "1 " << t1.query(1, n + 2, 1, l + 2, r) << " 3" << endl;
}
}
}
signed main(){
freopen("variance.in", "r", stdin);
freopen("variance.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++)
cin >> a[i], sum[i] = sum[i - 1] + a[i];
t.build(1, n + 1, 1);
for(int i = 2; i <= n; i++)
t.update(1, n + 1, 1, i, i, sum[i] - sum[i - 2]);
t1.build(1, n + 2, 1);
for(int i = 3; i <= n; i++)
t1.update(1, n + 2, 1, i, i, sum[i] - sum[i - 3]);
while(q--) solve();
return 0;
}
/*
5 4
1 -2 3 -4 5
2 1 5
1 2 4 4
2 1 2
2 2 4
*/