【线段树入门】P3353 在你窗外闪耀的星星（区间求和）

 1  1 //笔记-自用
 2  2 //#pragma GCC optimize("Ofast")
 3  3 //#pragma GCC optimize("unroll-loops")
 4  4 #define _CRT_SECURE_NO_WARNINGS
 5  5 #define All(a) a.begin(),a.end()
 6  6 #define INF 2147483647
 7  7 #include<bits/stdc++.h>
 8  8 #include<numeric>
 9  9 using namespace std;
10 10 typedef unsigned long long ull;
11 11 #define int long long//再也不用担心开longlong了><
12 12 typedef pair<int, int>PII;
13 13 const int N = 1e5 + 5;
14 14 #define lc p<<1
15 15 #define rc p<<1|1
16 16 struct node {
17 17     int l, r, sum, add;
18 18 }tr[N * 4];
19 19 int w[N];
20 20 void pushup(int p) {
21 21     tr[p].sum = tr[lc].sum + tr[rc].sum;
22 22 }
23 23 void pushdown(int p) {
24 24     if (tr[p].add) {
25 25         tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
26 26         tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
27 27         tr[lc].add += tr[p].add;
28 28         tr[rc].add += tr[p].add;
29 29         tr[p].add = 0;
30 30     }
31 31 }
32 32 void build(int p, int l, int r) {
33 33     tr[p] = { l,r,w[l],0 };
34 34     if (l == r)return;
35 35     int mid = tr[p].l + tr[p].r >> 1;
36 36     build(lc, l, mid);
37 37     build(rc, mid + 1, r);
38 38     pushup(p);
39 39 }
40 40 void update(int p, int x, int y, int k) {
41 41     if (x <= tr[p].l && tr[p].r <= y) {
42 42         tr[p].sum += k * (tr[p].r - tr[p].l + 1);
43 43         tr[p].add += k;
44 44         return;
45 45     }
46 46     pushdown(p);
47 47     int mid = tr[p].l + tr[p].r >> 1;
48 48     if (x <= mid)update(lc, x, y, k);
49 49     if (y > mid)update(rc, x, y, k);
50 50     pushup(p);
51 51 }
52 52 int query(int p, int x, int y) {
53 53     if (x <= tr[p].l && tr[p].r <= y) {
54 54         return tr[p].sum;
55 55     }
56 56     int mid = tr[p].l + tr[p].r >> 1;
57 57     pushdown(p);
58 58     int sum = 0;
59 59     if (x <= mid)sum += query(lc, x, y);
60 60     if (y > mid)sum += query(rc, x, y);
61 61     return sum;
62 62 }
63 63 signed main() {
64 64     ios::sync_with_stdio(false);
65 65     cin.tie(nullptr);
66 66     cout.tie(nullptr);
67 67     int n, m;
68 68     cin >> n >> m;
69 69     while (n--) {
70 70         int a, b;
71 71         cin >> a >> b;
72 72         w[a] += b;
73 73     }
74 74     build(1, 1, 100000);
75 75     int MAX = 0;
76 76     for (int i = 1; i <= 100000; i++) {
77 77         MAX = max(MAX, query(1, i, i + m - 1));
78 78     }
79 79     cout << MAX;
80 80 }