首先感谢这位大佬对我的问题的回答!

不一定保证完全没有bug,有bug可以反馈一下我争取在下一个版本改
做题的时候不要用,很可能有bug!!!!而且可能不是最优化的
支持的操作:
区间修改
区间加法(2)
区间减法(3)
区间乘法(1)
区间查询
区间和(4)
区间最大值(5)
区间最小值(6)
单点查询及其应用
区间中位数(7)(不够完善,未进行小数的处理)
其他:对int以上取模(未完善,很多没有加上呢还)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define ll long long
int n, p = INT_MAX, m;
int w[N];
struct Node
{
int l, r;
int add, sum, malt;
int maxn, minn;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].sum = tr[u].sum % p;
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
}
void pushdown(int u)
{
tr[u << 1].maxn = tr[u << 1].maxn * tr[u].malt + tr[u].add;
tr[u << 1].minn = tr[u << 1].minn * tr[u].malt + tr[u].add;
tr[u << 1 | 1].maxn = tr[u << 1 | 1].maxn * tr[u].malt + tr[u].add;
tr[u << 1 | 1].minn = tr[u << 1 | 1].minn * tr[u].malt + tr[u].add;
tr[u << 1].sum = ((ll)tr[u << 1].sum * tr[u].malt + (ll)tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1)) % p;
tr[u << 1 | 1].sum = ((ll)tr[u << 1 | 1].sum * tr[u].malt + (ll) tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % p;
tr[u << 1].add = ((ll)tr[u << 1].add * tr[u].malt + tr[u].add) % p;
tr[u << 1 | 1].add = ((ll)tr[u << 1 | 1].add * tr[u].malt + tr[u].add) % p;
tr[u << 1].malt = (ll)tr[u << 1].malt * tr[u].malt % p;
tr[u << 1 | 1].malt = (ll)tr[u << 1 | 1].malt * tr[u].malt % p;
tr[u].add = 0;
tr[u].malt = 1;
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, 0, w[r], 1, w[r], w[r]};
else
{
tr[u] = {l, r, 0, 0, 1, 0, 0};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void change(int u, int l, int r, int malt, int add)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].maxn = tr[u].maxn * malt + add;
tr[u].minn = tr[u].minn * malt + add;
tr[u].sum = ((ll)tr[u].sum * malt + (ll)add * (tr[u].r - tr[u].l + 1)) % p;
tr[u].add = ((ll)tr[u].add * malt + add) % p;
tr[u].malt = (ll)tr[u].malt * malt % p;
}
else
{
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) change(u << 1, l, r, malt, add);
if(r > mid) change(u << 1 | 1, l, r, malt, add);
pushup(u);
}
}
int querysum(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
ll res = 0;
if(l <= mid)
{
res += querysum(u << 1, l, r);
res = res % p;
}
if(r > mid)
{
res += querysum(u << 1 | 1, l, r);
res = res % p;
}
return res;
}
double getmiddleidx(int l,int r)
{
if((r - l + 1) % 2)
{
return querysum(1, (r - l) / 2 + 1, (r - l) / 2 + 1);
}
else
{
return querysum(1, (r - l + 1) / 2, (r - l + 1) / 2 + 1) / 2;
}
}
int querymax(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if(l <= mid) v = querymax(u << 1, l, r);
if(r > mid) v = max(v, querymax(u << 1 | 1, l, r));
return v;
}
int querymin(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].minn;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int w = 0x3f3f3f3f;
if(l <= mid) w = querymin(u << 1, l, r);
if(r > mid) w = min(w, querymin(u << 1 | 1, l, r));
return w;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];
build(1, 1, n);
cin >> m;
while(m --)
{
int op;
int l, r;
int c;
cin >> op;
if(op == 2)
{
cin >> l >> r >> c;
change(1, l, r, 1, c);
}
else if(op == 1)
{
cin >> l >> r >> c;
change(1, l, r, c, 0);
}
else if(op == 3)
{
cin >> l >> r >> c;
change(1, l, r, 1, -c);
}
else if(op == 4)
{
cin >> l >> r;
cout << querysum(1, l, r) << endl;
}
else if(op == 5)
{
cin >> l >> r;
cout << querymax(1, l, r) << endl;
}
else if(op == 6)
{
cin >> l >> r;
cout << querymin(1, l, r) << endl;
}
else if(op == 7)
{
cin >> l >> r;
cout << getmiddleidx(l, r) << endl;
}
}
return 0;
}
挖坑时间到
后面争取先修好bug,然后加上求众数,把一个数弄成区间最小值的等等,有建议评论区见。
一个高斯消元调了三个月qwq
真实
我……还没调一小时就放弃了加油!
我……一个LCA调一个下午
哈哈真实
我之前一个双指针调3天
哈哈真实
我之前一个双指针调3天