题解 P2003 【平板】

HOOCCOOH

2015-10-25 20:34:28

Solution

这题N太小了,导致暴力也能过,但是我们要追求更高效率的算法。 事实上,可以在O(NlogN+NlogH)时间内解决这个问题。 我们可以维护[1,H]区间中每个x的高度,先给平板从低到高排序,一个个加入,只用查询两点的当前高度以及修改平板覆盖区间范围即可,所以当然是用线段树啦=w= 所以即使N,H在10^5范围也没事啦 ```cpp #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <cctype> using namespace std; typedef long long ll; typedef unsigned long long ull; int iRead() { int ret = 0; int ch; while(!isdigit(ch = getchar()) && ch != '-'); bool bm = (ch == '-'); if(bm) ch = getchar(); while(ret = ret * 10 + (ch - '0'), isdigit(ch = getchar())); return bm ? -ret : ret; } const int N = 103; const int M = 10003; struct iT { int s; int val; bool mark; iT *l, *r; }ss[M * 4], *sp = ss; void iDown(iT *c) { if(c->mark) { c->l->val = c->r->val = c->val; c->l->mark = c->r->mark = true; c->mark = false; } } iT *iMake(int l, int r) { iT *c = sp++; if(l + 1 == r) *c = (iT){1, 0, false, NULL, NULL}; else { int m = l + r >> 1; *c = (iT){r - l, 0, false, iMake(l, m), iMake(m, r)}; } return c; } void iSet(iT *c, int l, int r, int val) { if(l <= 0 && r >= c->s) { c->val = val; c->mark = true; return; } iDown(c); int m = c->s >> 1; if(l < m) iSet(c->l, l, r, val); if(m < r) iSet(c->r, l - m, r - m, val); } int iQuery(iT *c, int pos) { if(c->s == 1) return c->val; iDown(c); int m = c->s >> 1; if(pos < m) return iQuery(c->l, pos); else return iQuery(c->r, pos - m); } struct iQ { int y; int a, b; bool operator<(const iQ &r) const {return y < r.y;} }arr[N]; int main() { iT *head = iMake(0, M); int n = iRead(); for(int i = 0; i < n; ++i) { int y = iRead(), a = iRead(), b = iRead(); arr[i] = (iQ){y, a, b}; } sort(arr, arr + n); int ans = 0; for(int i = 0; i < n; ++i) { ans += arr[i].y - iQuery(head, arr[i].a); ans += arr[i].y - iQuery(head, arr[i].b - 1); iSet(head, arr[i].a, arr[i].b, arr[i].y); } printf("%d\n", ans); return 0; } ```