数据结构

线段树扫描线

线段树

区间修改，区间查询的线段树模板（查询区间最值）

#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; #define int long long int n,m; int a[N]; struct Node { int l,r; int sum,add; }tr[N*4]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 |1].sum; } void pushdown(int u) { auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 |1 ]; if(root.add) { left.add += root.add, left.sum += (left.r - left.l + 1) * root.add; right.add += root.add, right.sum += (right.r - right.l + 1) * root.add; root.add = 0; } } void build(int u,int l,int r) { tr[u] = {l,r}; if(l == r) { tr[u].sum = a[l], tr[u].add = 0; return; } int mid = l + r >> 1; build(u << 1, l , mid), build(u << 1 | 1, mid + 1 , r); pushup(u); } void modify(int u,int l,int r,int v) { if(tr[u].l >= l && tr[u].r <= r) { tr[u].sum += (tr[u].r - tr[u].l + 1)*v; tr[u].add += v; return ; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r, v); if(r > mid) modify(u << 1 | 1,l , r , v); pushup(u); } int query(int u,int l,int r) { if(tr[u].l >= l && tr[u].r <=r ) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; int sum = 0; if(l <= mid) sum = query(u << 1,l,r); if(r > mid) sum += query(u << 1 | 1, l, r); return sum; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n ; ++ i) cin >> a[i]; build(1,1,n); char op; int l,r,d; while(m--) { cin >> op >> l >> r; if(op == 'Q') { cout << query(1,l,r) << endl; } else if(op == 'C') { cin >> d; modify(1,l,r,d); } } return 0; }

扫描线

#include<bits/stdc++.h> using namespace std; const int N = 10005; int n; double a[2*N]; int len; struct Segment { double x,y1,y2; int k; bool operator < (const Segment &S) const { return x < S.x; } }Seg[2*N]; struct Node { int l,r; int cnt; double len; }tr[8*N]; int find(double y) { return lower_bound(a,a+len,y) - a; } void pushup(int u) { if(tr[u].cnt > 0) { tr[u].len = a[tr[u].r + 1] - a[tr[u].l]; } else if(tr[u].l == tr[u].r) tr[u].len = 0; else tr[u].len = tr[u<<1].len + tr[u<<1|1].len; } void build(int u,int l,int r) { tr[u] = {l,r,0,0}; if(l != r) { int mid = l + r >> 1; build(u <<1, l , mid), build(u <<1 |1, mid+1, r); } } void modify(int u,int l,int r,int k) { if(tr[u].l >= l && tr[u].r <= r) { tr[u].cnt += k; pushup(u); } else { int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u <<1, l, r,k); if(r > mid) modify(u<<1|1, l, r, k); pushup(u); } } void out(Segment S) { cout << S.x << ' ' <<S.y1 << ' ' << S.y2 << endl; } int main() { int ca = 0; while(~scanf("%d",&n) && n) { for(int i = 0; i < n; ++ i) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); Seg[i<<1] = {x1,y1,y2,1}, Seg[i<<1|1] = {x2,y1,y2,-1}; a[i<<1] = y1, a[i<<1|1] = y2; } sort(Seg,Seg+2*n); sort(a,a+2*n); len = unique(a,a+2*n) - a; build(1, 0, len-2); double ans = 0; for(int i = 0; i < 2*n; ++ i) { //out(Seg[i]); if(i > 0) ans += tr[1].len * (Seg[i].x - Seg[i-1].x); modify(1, find(Seg[i].y1) , find(Seg[i].y2) - 1, Seg[i].k); } printf("Test case #%d\n",++ca); printf("Total explored area: %.2lf\n\n",ans); } }