这题正解是前缀和,我用线段树练练手><
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 }
标签:P3353,int,线段,mid,long,build,闪耀,sum,define From: https://www.cnblogs.com/iscr/p/17896534.html