P5482 题解

· · 个人记录

提供一个新的思路。

思路

拿到不等式先化式子。

ax + b > c \iff ax>c-b

这是显然的。

考虑把 (a, c-b) 看作二维平面上的一个点 (X, Y)，上述不等式就变成了 xX>Y。这个式子的含义就是点 (X,Y)在斜率等于 x 的正比例函数的下面。

于是对于每个询问，就可以看作给你一个正比例函数（一条过原点的直线），询问平面上有多少个点在这条直线的下面。

这个问题怎么处理呢？由于直线一定过原点，所以一个点在它下面当且仅当这个点的极角在这个范围内：

\begin{cases} (-\tan x,\tan x),x\geq 0\\ (\tan x,-\tan x),x<0 \end{cases}

那我们考虑对整个平面的所有点极角排序。为了避免分类讨论，我们重定义极角大小，让第二象限的极角最小，第一象限的极角最大。

然后我们只要求极角大小比点 (-1, -k) 大，比 (1, k) 小的点的个数就可以了。

由于是维护平面上的点，树状数组不太可行了，只能考虑动态开点线段树和平衡树。平衡树是比较常规的做法。

参考代码

参考代码极其毒瘤，用了函数对象，template，指针，lambda 表达式等众多毒瘤语法，仅供参考，有时间再写一个比较清新的。

#include <cctype>
#include <cstdio>
#include <algorithm>

struct FSI
{
    template<typename T>
    FSI& operator>>(T &res)
    {
        res = 0; T f = 1; char ch = getchar();
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
        while (isdigit(ch)) { res = res * 10 + (ch - '0') * f; ch = getchar(); }
        return *this;
    }
} read;

using i64 = long long;
using PII = std::pair<int, int>;
const int N = 1e5 + 10;

struct less
{
    bool operator()(const PII &a, const PII &b)
    {
        auto getPlain = [](PII p)
        {
            if (p.first < 0) {
                if (p.second > 0) return 0;
                else return 1;
            }
            else {
                if (p.second < 0) return 2;
                else return 3;
            }
        };
        auto cmpPlain = [](PII a, PII b)
        { return 1ll * a.first * b.first < 0 || 1ll * a.second * b.second < 0; };
        if (cmpPlain(a, b)) return getPlain(a) < getPlain(b);
        return 1ll * a.second * b.first < 1ll * b.second * a.first;
    }
};
struct leq
{
    bool operator()(const PII &a, const PII &b)
    {
        auto getPlain = [](PII p)
        {
            if (p.first < 0) {
                if (p.second > 0) return 0;
                else return 1;
            }
            else {
                if (p.second < 0) return 2;
                else return 3;
            }
        };
        auto cmpPlain = [](PII a, PII b)
        { return 1ll * a.first * b.first < 0 || 1ll * a.second * b.second < 0; };
        if (cmpPlain(a, b)) return getPlain(a) < getPlain(b);
        return 1ll * a.second * b.first <= 1ll * b.second * a.first;
    }
};
struct node
{
    PII val;
    int w, size;
    node *l, *r;
} tr[N];
int m, idx, cnt, tot;
node *root = tr;
PII point[N];
bool vis[N];

node* New(PII v)
{
    node *u = tr + ++idx;
    u->val = v;
    u->size = 1;
    u->w = rand();
    u->l = u->r = tr;
    return u;
}
void maintain(node *u)
{ u->size = u->l->size + u->r->size + 1; }
template<typename T>
std::pair<node*, node*> split(node *u, PII v, T cmp)
{
    if (u == tr) return std::make_pair(tr, tr);
    std::pair<node*, node*> t;
    if (cmp(u->val, v)) {
        t = split(u->r, v, cmp);
        u->r = t.first;
        t.first = u;
    }
    else {
        t = split(u->l, v, cmp);
        u->l = t.second;
        t.second = u;
    }
    maintain(u);
    return t;
}
node* merge(node *x, node *y)
{
    if (x == tr) return y;
    if (y == tr) return x;
    if (x->w < y->w) {
        x->r = merge(x->r, y);
        maintain(x);
        return x;
    }
    else {
        y->l = merge(x, y->l);
        maintain(y);
        return y;
    }
}
void insert(PII v)
{
    auto t = split(root, v, less());
    root = merge(t.first, merge(New(v), t.second));
}
void remove(PII v)
{
    auto a = split(root, v, less());
    auto b = split(a.second, v, leq());
    b.first = merge(b.first->l, b.first->r);
    root = merge(a.first, merge(b.first, b.second));
}

int main(void)
{
    tr[0].l = tr[0].r = tr;
    read >> m;
    for (int T = 1; T <= m; ++T) {
        static char str[10];
        scanf("%s", str);
        if (str[0] == 'A') {
            ++tot;
            int a, b, c;
            read >> a >> b >> c;
            point[++cnt] = std::make_pair(a, c - b);
            insert(point[cnt]);
        }
        else if (str[0] == 'D') {
            int x;
            read >> x;
            if (!vis[x]) {
                --tot;
                vis[x] = 1;
                remove(point[x]);
            }
        }
        else {
            int k;
            read >> k;
            auto a = split(root, std::make_pair(-1, -k), leq());
            auto b = split(a.second, std::make_pair(1, k), less());
            printf("%d\n", b.first->size);
            root = merge(a.first, merge(b.first, b.second));
        }
    }
    return 0;
}