思路：好像是第一次这么印象深刻的写线段树，说实话，这个题确实很有意思，值得学习。
看了大神讲解视频，但是自己写的还是超时了。
参考来自 https://blog.csdn.net/yiqzq/article/details/81211652 个人认为可以作为模板
#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> #include <stack> #include <set> #include <cctype> #define eps 1e-8 #define INF 0x3f3f3f3f #define MOD 1e9+7 #define PI acos(-1) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e5 + 5; int n, q; int MIN[maxn << 2];//记录区间最小值 int lazy[maxn << 2];//延迟标记减法 int ans[maxn << 2];//记录答案数量 int b[maxn << 2];//记录b数组 //线段树基本操作,pushup和pushdown void pushup(int rt) { MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]); ans[rt] = ans[rt << 1] + ans[rt << 1 | 1]; } void pushdown(int rt) { if(lazy[rt]) { lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; MIN[rt << 1] -= lazy[rt]; MIN[rt << 1 | 1] -= lazy[rt]; lazy[rt] = 0; } } //建树 void build(int l, int r, int rt) { lazy[rt] = 0; ans[rt] = 0; if(l == r) { scanf("%d", &b[rt]); MIN[rt] = b[rt]; return ; } int m = (l + r) >> 1; build(lson); build(rson); pushup(rt); } //区间更新,需要注意当NIN减为0的时候,要ans++并且重新将b的值赋给MIN void updata(int L, int R, int l, int r, int rt) { if(L <= l && R >= r) { MIN[rt]--; if(MIN[rt]) { lazy[rt]++; return; } else { if(l == r) { ans[rt]++; MIN[rt] = b[rt]; return; /*血的教训,这个return不能放大括号外面,因为如果递归到某个节点MIN是0 但是又不是叶子节点,那么还是需要继续递归直到找到叶子节点为止 */ } } } pushdown(rt); int m = (l + r) >> 1; if(L <= m) updata(L, R, lson); if(R > m) updata(L, R, rson); pushup(rt); } //查询 int query(int L, int R, int l, int r, int rt) { if(L <= l && R >= r) { return ans[rt]; } pushdown(rt); int m = (l + r) >> 1; int sum = 0; if(m >= L) sum += query(L, R, lson); if(m < R) sum += query(L, R, rson); return sum; } int main() { while(~scanf("%d%d", &n, &q)) { build(1, n, 1); for(int i = 1; i <= q; i++) { char op[10]; int a, b; scanf("%s%d%d", op, &a, &b); if(op[0] == 'q') { printf("%d ", query(a, b, 1, n, 1)); } else { updata(a, b, 1, n, 1); } } } return 0; }
#include<queue> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 1e5 + 5; int add[maxn << 2]; int tree[maxn << 2]; int MAX[maxn << 2]; int a[maxn]; void build(int l, int r,int rt) { add[rt] = 0; MAX[rt] = (int)-1e9; tree[rt] = 0; if (l == r){ add[rt] = 0; tree[rt] = 0; MAX[rt] = -a[l]; return; } int m = (l + r) >> 1; build(lson); build(rson); tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]); } void PushDown(int rt) { if (add[rt]){ add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; MAX[rt << 1] += add[rt]; MAX[rt << 1 | 1] += add[rt]; add[rt] = 0; } } void update1(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R){ add[rt]++; MAX[rt]++; return; } PushDown(rt); int m = (l + r) >> 1; if (L <= m)update1(L, R, lson); if (R > m)update1(L, R, rson); tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]); } void update2(int L, int R, int l, int r, int rt) { if (l == r){ if (MAX[rt] >= 0){ tree[rt]++; MAX[rt] = -a[l]; } return; } PushDown(rt); int m = (l + r) >> 1; if (L <= m&&MAX[rt << 1] >= 0)update2(L, R, lson); if (R > m&&MAX[rt << 1 | 1] >= 0)update2(L, R, rson); tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]); } int query(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R){ return tree[rt]; } int m = (l + r) >> 1, ans = 0; if (L <= m)ans += query(L, R, lson); if (R > m)ans += query(L, R, rson); return ans; } void Print(int l, int r, int rt) { if (l == r){ cout << rt << " = " << MAX[rt] << endl; return; } cout << rt << " = " << MAX[rt] << endl; int m = (l + r) >> 1; if (l <= m)Print(lson); if (r > m)Print(rson); } int main() { std::ios::sync_with_stdio(false); int n, q; while (cin >> n >> q){ for (int i = 1; i <= n; i++) cin >> a[i]; build(1, n, 1); string flag; int l, r; for (int i = 0; i < q; i++){ cin >> flag >> l >> r; if (flag == "add"){ update1(l, r, 1, n, 1); update2(l, r, 1, n, 1); //Print(1, n, 1); } else cout << query(l, r, 1, n, 1) << endl; } } return 0; }