\(des\)
存在参数数组 \(a\)，\(a\) 升序排列
\[a_1 < a_2 < \cdots < a_m, m <= 10
\]
\]
存在长度为 \(n\) 价值数组 \(val\)
存在 \(3\) 中操作
- 使区间 \([l, r]\) 内的 \(val\) 增加 \(x\)
- 单点修改 \(x\)
- 给定区间 \([l, r]\) ，定义 \(f(x)\) 表示最大的 \(i\) 是的 \(a_i <= x\)
求 \(\sum_{i = l} ^ {r} f(i)\)
\(sol\)
如果没有操作2，也就是说元素不会减小，同时 \(f(x)\) 也不会减小，所有的元素
\(f(x)\) 增加一共会有 \(O(nm)\)。这里可以用线段树维护，第 \(i\) 个点维护的是
\(f(i)\) 还需要增加多少才可以增加，单次操作1相当于对区间 \([l, r]\) 做减法
，显然如果某个时刻存在某个数 \(<= 0\)，这是 \(f(x)\) 需要增加，改变相关信息
，可以线段树维护区间最小值来实现。那么如果存在操作2是一样的，不过可能会
存在 \(f(x)\) 的减小的情况，并不会对时间复杂度产生大的影响
由于一共只会存在 \(O((n + q)m)\) 次增加，时间复杂度 O((n + 1)mlogn)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
const int N = 1e5 + 10;
#define gc getchar()
#define Rep(i, a, b) for(int i = a; i <= b; i ++)
#define LL long long
inline int read() {int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
inline LL readLL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
int W[N << 2], F[N << 2], Minn[N << 2];
int A[15], Val[N];
int n, m, q;
#define lson jd << 1
#define rson jd << 1 | 1
void Build_tree(int l, int r, int jd) {
if(l == r) {
int x = lower_bound(A + 1, A + m + 1, Val[l]) - A;
if(A[x] > Val[l]) x --;
W[jd] = x;
Minn[jd] = A[x + 1] - Val[l];
return ;
}
int mid = (l + r) >> 1;
Build_tree(l, mid, lson), Build_tree(mid + 1, r, rson);
Minn[jd] = min(Minn[lson], Minn[rson]);
W[jd] = W[lson] + W[rson];
}
void Push_down(int jd) {
F[lson] += F[jd], F[rson] += F[jd];
Minn[lson] += F[jd], Minn[rson] += F[jd];
F[jd] = 0;
}
void Sec_G(int l, int r, int jd, int x, int y, int num) {
if(x <= l && r <= y) {
Minn[jd] -= num;
F[jd] -= num;
return ;
}
if(F[jd] != 0) Push_down(jd);
int mid = (l + r) >> 1;
if(x <= mid) Sec_G(l, mid, lson, x, y, num);
if(y > mid) Sec_G(mid + 1, r, rson, x, y, num);
Minn[jd] = min(Minn[lson], Minn[rson]);
}
void Dfs_G(int l, int r, int jd) {
if(l == r) {
int b = A[W[jd] + 1] - Minn[jd];
Val[l] = b;
int x = lower_bound(A + 1, A + m + 1, b) - A;
if(A[x] > b) x --;
W[jd] = x;
Minn[jd] = A[x + 1] - b;
return ;
}
if(F[jd]) Push_down(jd);
int mid = (l + r) >> 1;
if(Minn[lson] <= 0) Dfs_G(l, mid, lson);
if(Minn[rson] <= 0) Dfs_G(mid + 1, r, rson);
Minn[jd] = min(Minn[lson], Minn[rson]);
W[jd] = W[lson] + W[rson];
}
void Poi_G(int l, int r, int jd, int x, int num) {
if(l == r) {
Val[l] = num;
int x = lower_bound(A + 1, A + m + 1, Val[l]) - A - 1;
W[jd] = x;
Minn[jd] = A[x + 1] - Val[l];
return ;
}
if(F[jd]) Push_down(jd);
int mid = (l + r) >> 1;
if(x <= mid) Poi_G(l, mid, lson, x, num);
else Poi_G(mid + 1, r, rson, x, num);
W[jd] = W[lson] + W[rson];
Minn[jd] = min(Minn[lson], Minn[rson]);
}
int Answer;
void Sec_A(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) {
Answer += W[jd];
return ;
}
if(F[jd]) Push_down(jd);
int mid = (l + r) >> 1;
if(x <= mid) Sec_A(l, mid, lson, x, y);
if(y > mid) Sec_A(mid + 1, r, rson, x, y);
}
int main() {
n = read(), m = read(), q = read();
Rep(i, 1, m) A[i] = read();
A[m + 1] = (1 << 30);
Rep(i, 1, n) Val[i] = read();
Build_tree(1, n, 1);
Rep(t, 1, q) {
int opt = read();
if(opt == 1) {
int l = read(), r = read(), x = read();
Sec_G(1, n, 1, l, r, x);
if(Minn[1] <= 0) Dfs_G(1, n, 1);
} else if(opt == 2) {
int p = read(), x = read();
Poi_G(1, n, 1, p, x);
} else {
int x = read(), y = read();
Answer = 0;
Sec_A(1, n, 1, x, y);
cout << Answer << "\n";
}
}
return 0;
}