描述

兩種操作:

1. (1, x, y) 表示 x 點權值增加 y

2. (2, x, y) 表示求 [x, y] 區間的最大值與次大值的差.

分析

• 可以采用線段樹
• 對于操作1, 就是單點修改
• 操作2, 先找到區間最大值, 然后把這個點清零, 再求一遍區間最大值. 相減輸出. 最后單點修改改回原狀態.
• 有許多細節需要注意.

代碼

#include #include using namespace std;const int INF = 1000000000; const int maxn = 100000 + 10;struct SegmentTree {int n;int x, y1, y2, d, p, q;int maxv[maxn<<2];#define lc (o<<1)#define rc (o<<1^1)#define M (L+R>>1)void update(int o) {maxv[o] = max(maxv[lc], maxv[rc]);}void modify(int o, int L, int R) {if(L == R) { maxv[o] += d; return; }if(x <= M) modify(lc, L, M); else modify(rc, M+1, R);update(o);}void query1(int o, int L, int R) {if(y1 <= L && R <= y2) {if(d < maxv[o]) d = maxv[o], p = L, q = R;return;}if(y1 <= M) query1(lc, L, M);if(y2 > M) query1(rc, M+1, R);}int query2(int o, int L, int R) {if(y1 <= L && R <= y2) return maxv[o];int ret = 0;if(y1 <= M) ret = max(ret, query2(lc, L, M));if(y2 > M) ret = max(ret, query2(rc, M+1, R));return ret;}int remove(int o, int L, int R) {if(L == R) { maxv[o] = 0; return L; }int ret = (maxv[lc] == d ? remove(lc, L, M) : remove(rc, M+1, R));update(o);return ret;}void find(int o, int L, int R) {if(L == p && R == q) { x = remove(o, L, R); return; }int ret = 0;if(!x && p <= M && maxv[lc] >= d) find(lc, L, M);if(!x && q > M && maxv[rc] >= d) find(rc, M+1, R);update(o);}void Modify() {modify(1, 1, n);}void Query() {d = 0; x = 0;query1(1, 1, n);if(!d) { printf("0\n"); return; }find(1, 1, n);printf("%d\n", d-query2(1, 1, n));modify(1, 1, n);}} seg;int main() {int n, m;scanf("%d %d", &n, &m);seg.n = n;for(int i = 1; i <= m; i++) {int q, x, y;scanf("%d %d %d", &q, &x, &y);if(q == 1) {seg.x = x;seg.d = y;seg.Modify();} else {seg.y1 = x;seg.y2 = y;seg.Query();}}return 0; }

總結

以上是生活随笔為你收集整理的CODEVS-2018-反病毒软件-线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。