题解 P2003 【平板】
HOOCCOOH
2015-10-25 20:34:28
这题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;
}
```