2 条题解
-
0
C33 线段树+贪心 P1937 [USACO10MAR] Barn Allocation G
// 贪心+线段树 O(nlogn) #include <bits/stdc++.h> using namespace std; #define ls(p) (p << 1) #define rs(p) (p << 1 | 1) const int N = 100005; int n, m, c[N], ans; struct line{int l, r;} s[N]; // 区间 struct tree{int l, r, mi, lazy;} tr[N * 4]; // 线段树 void pushup(int p) { tr[p].mi = min(tr[ls(p)].mi, tr[rs(p)].mi); } void pushdown(int p) { if (tr[p].lazy) { tr[ls(p)].mi -= tr[p].lazy; tr[rs(p)].mi -= tr[p].lazy; tr[ls(p)].lazy += tr[p].lazy; tr[rs(p)].lazy += tr[p].lazy; tr[p].lazy = 0; } } void bt(int p, int l, int r) { tr[p] = {l, r, c[l]}; if(l==r) return; int m = (l + r) >> 1; bt(ls(p), l, m);bt(rs(p), m+1, r); pushup(p); } void change(int p, int l, int r) { if (tr[p].l > r || tr[p].r < l) return; if (tr[p].l >= l && tr[p].r <= r) { tr[p].mi--; tr[p].lazy++; return; } pushdown(p); change(ls(p), l, r); change(rs(p), l, r); pushup(p); } int query(int p, int l, int r) { if (tr[p].l > r || tr[p].r < l) return 2e5; if (tr[p].l >= l && tr[p].r <= r)return tr[p].mi; pushdown(p); return min(query(ls(p), l, r), query(rs(p), l, r)); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &c[i]); for (int i = 1; i <= m; i++)scanf("%d%d", &s[i].l, &s[i].r); sort(s + 1, s + m + 1,[](const line &n1,const line &n2){return n1.r<n2.r;}); // 按右端排序 bt(1, 1, n); for (int i = 1; i <= m; i++) { int l = s[i].l, r = s[i].r; if (!query(1, l, r))continue; change(1, l, r); ans++; } printf("%d\n", ans); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:04:37
C33 线段树+贪心 P1937 [USACO10MAR] Barn Allocation G
// 贪心+线段树 O(nlogn) #include <bits/stdc++.h> using namespace std; #define ls(p) (p << 1) #define rs(p) (p << 1 | 1) const int N = 100005; int n, m, c[N], ans; struct line{int l, r;} s[N]; // 区间 struct tree{int l, r, mi, lazy;} tr[N * 4]; // 线段树 void pushup(int p) { tr[p].mi = min(tr[ls(p)].mi, tr[rs(p)].mi); } void pushdown(int p) { if (tr[p].lazy) { tr[ls(p)].mi -= tr[p].lazy; tr[rs(p)].mi -= tr[p].lazy; tr[ls(p)].lazy += tr[p].lazy; tr[rs(p)].lazy += tr[p].lazy; tr[p].lazy = 0; } } void bt(int p, int l, int r) { tr[p] = {l, r, c[l]}; if(l==r) return; int m = (l + r) >> 1; bt(ls(p), l, m);bt(rs(p), m+1, r); pushup(p); } void change(int p, int l, int r) { if (tr[p].l > r || tr[p].r < l) return; if (tr[p].l >= l && tr[p].r <= r) { tr[p].mi--; tr[p].lazy++; return; } pushdown(p); change(ls(p), l, r); change(rs(p), l, r); pushup(p); } int query(int p, int l, int r) { if (tr[p].l > r || tr[p].r < l) return 2e5; if (tr[p].l >= l && tr[p].r <= r)return tr[p].mi; pushdown(p); return min(query(ls(p), l, r), query(rs(p), l, r)); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &c[i]); for (int i = 1; i <= m; i++)scanf("%d%d", &s[i].l, &s[i].r); sort(s + 1, s + m + 1,[](const line &n1,const line &n2){return n1.r<n2.r;}); // 按右端排序 bt(1, 1, n); for (int i = 1; i <= m; i++) { int l = s[i].l, r = s[i].r; if (!query(1, l, r))continue; change(1, l, r); ans++; } printf("%d\n", ans); return 0; }
- 1
