题解 P2003 【平板】
题解

这题N太小了,导致暴力也能过,但是我们要追求更高效率的算法。

事实上,可以在O(NlogN+NlogH)时间内解决这个问题。

我们可以维护[1,H]区间中每个x的高度,先给平板从低到高排序,一个个加入,只用查询两点的当前高度以及修改平板覆盖区间范围即可,所以当然是用线段树啦=w=

所以即使N,H在10^5范围也没事啦


#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;
}
评论