王清楚

编辑于 2020-05-18 14:52

【题解】厦门大学程序设计大赛月赛（同步赛）

兰德索尔的瞭望塔-solution

白话文题意

二维直角坐标系中，给定两个 $x$ 轴上的定点 $O, A$ 和第一象限内（非 $x$ 轴）上的若干个点 $B, C, D...$ 。某两个点 $P, Q$ 和 $x$ 轴上的定点构成的三角形可能存在包含关系，求三角形个数最多的包含关系，满足除了 $OA$ 外，两个三角形不能存在其它共边，保证给出的点不重复。

分析

首先让我们来分析样例给的一张示意图。这张图中存在的包含关系个数最多的三角形显然是 $\triangle OAB, \triangle OCA$ 和 $\triangle ODA$ 。让我们来看一下如何得到这样的结果。
图片说明
考虑如何满足严格包含的条件：为了让两个三角形 $\triangle OAB, \triangle OAC$ 满足其中之一严格包含另一个三角形，由于 $OA$ 边是固定的，不难得出当且仅当 $\angle COA > \angle BOA$ 且 $\angle CAO > \angle BAO$ 时，满足严格包含关系；对于其它三角形也同理。

接下来考虑如何计算以某个点为顶点的三角形，最多包含了多少个其它三角形。记给定的点为 $X_1, X_2, ..., X_n$ ， $f[i]$ 为 $\triangle OAX_i$ 最多包含的三角形个数，容易知道：

$\begin{aligned}f[i] = \max \{f[j] + 1, 1\}, && \angle X_iOA > \angle X_jOA 且 \angle X_iAO > \angle X_jAO \end{aligned}$

直接枚举每两个点计算上面的式子是 $O(n^2)$ 的。但注意到，如果 $f[j]$ 能够用来更新 $f[i]$ 时，点 $X_j$ 到点 $O, A$ 与 $x$ 轴的夹角一定小于 $X_i$ 到点 $O, A$ 与 $x$ 轴的夹角。

因此，我们可以按照 $X_i$ 到 $O, A$ 与 $x$ 轴的夹角从小到大的顺序来计算答案。如何统计？首先对所有给定的点 $X_i$ ，做关于原点的极角排序，这样我们保证了 $\angle X_iOA$ 是有序的，那么 $\angle X_iAO$ 呢？我们可以对 $\angle X_iAO$ 离散化，然后在统计答案的过程中，使用权值线段树维护不同大小的 $\angle X_iAO$ 对应的答案。

具体地说，我们可以将 $\angle X_iAO$ 排序后离散化，令 $rk[X_i]$ 表示角 $\angle X_iAO$ 在所有角中的大小，并建立维护最大值的权值线段树， $T[1, rk[X_i]-1]$ 表示所有 $\angle X_kAO < \angle X_iAO$ 且 $\angle X_kOA < X_iOA$ 的 $f[k]$ 最大值。

在每次统计答案时，区间查询 $[1, rk[X_i]-1]$ 中 $f$ 的最大值，并单点修改 $T[rk[X_i]] += 1$ 。按照 $\angle X_iOA$ 的顺序从小到大统计答案，最后整棵线段树中根节点维护的最大值即为我们所求的答案。

细节：如何处理 $\angle X_iOA$ 相同时的情况？如果 $\angle X_iOA = \angle X_{i-1}OA$ ，则先将所有对权值线段树的操作暂存，直到遇见下一个 $\angle X_kOA > \angle X_iOA$ 时再对线段树进行修改，就可以保证不影响每次统计的答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100050;

struct Point {
    int id, pos;
    int x, y;
} pt[maxn];

int n, idx[maxn], x;
int qpos[maxn], qval[maxn];

bool cmp1(const Point &a, const Point &b) {
    return atan2(a.y, a.x - x) > atan2(b.y, b.x - x);
}

bool equal1(const Point &a, const Point &b) {
    return atan2(a.y, a.x - x) == atan2(b.y, b.x - x);
}

bool cmp2(const Point &a, const Point &b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

bool equal2(const Point &a, const Point &b) {
    return atan2(a.y, a.x) == atan2(b.y, b.x);
}

class SegTree {
public:
    #define lson (rt << 1)
    #define rson (rt << 1) | 1
    int a[maxn << 2];
    void init() {
        memset(a, 0, sizeof a);
    }
    void pushup(int rt) {
        a[rt] = max(a[lson], a[rson]);
    }
    void build(int rt, int l, int r, int x[]) {
        if (l == r) {
            a[rt] = x[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, x);
        build(rson, mid + 1, r, x);
        pushup(rt);
    }
    void update(int rt, int l, int r, int pos, int val) {
        if (pos == 0)
            return;
        if (l == r) {
            a[rt] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else
            update(rson, mid + 1, r, pos, val);
        pushup(rt);
    }
    int query(int rt, int l, int r, int ql, int qr) {
        if (ql > r || qr < l)
            return 0;
        if (ql <= l && r <= qr)
            return a[rt];
        int mid = (l + r) >> 1;
        return max(query(lson, l, mid, ql, qr), query(rson, mid + 1, r, ql, qr));
    }
} T;

template<class T>void read(T &x) {
    T a = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        f = ch == '-' ? -1 : f, ch = getchar();
    while (ch >= '0' && ch <= '9')
        a = a * 10 + ch - '0', ch = getchar();
    x = a * f;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        read(x);
        for (int i = 0; i < n; i++) {
            read(pt[i].x), read(pt[i].y);
            pt[i].id = i + 1;
        }
        sort(pt, pt + n, cmp1);

        int cnt = 1;
        pt[0].pos = cnt, idx[pt[0].id] = cnt++;
        for (int i = 1; i < n; i++) {
            if (equal1(pt[i], pt[i-1]))
                pt[i].pos = pt[i-1].pos,
                idx[pt[i].id] = idx[pt[i-1].id];
            else
                pt[i].pos = cnt, idx[pt[i].id] = cnt++;
        }

        T.init();
        sort(pt, pt + n, cmp2);

        int tmp = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || equal2(pt[i], pt[i-1])) {
                int pos = idx[pt[i].id],
                    size = T.query(1, 1, n, 1, pos - 1);
                qpos[tmp] = pos, qval[tmp++] = size + 1;
            } else {
                for (int j = 0; j < tmp; j++) {
                    T.update(1, 1, n, qpos[j], qval[j]);
                }
                tmp = 0;
                int pos = idx[pt[i].id],
                    size = T.query(1, 1, n, 1, pos - 1);
                qpos[tmp] = pos, qval[tmp++] = size + 1;
            }
        }

        for (int j = 0; j < tmp; j++)
            T.update(1, 1, n, qpos[j], qval[j]);
        printf("%d\n", T.a[1]);
    }
    return 0;
}

题解：环鸽的数列

利用特征方程 $\alpha^2=3\alpha+2$ ，我们可以解出特征根 $\alpha=\frac{3\pm\sqrt{17}}{2}$ 。再用待定系数法可得到 $F$ 的通项公式：
$ $F_n=\frac{1}{\sqrt{17}}\left(\left(\frac{3+\sqrt{17}}{2} \right)^n-\left(\frac{3-\sqrt{17}}{2} \right)^n \right)$ $我们可以先暴力跑一遍得到$ 17 $的二次剩余为$ 473844410$ ，然后处理出两个模意义下的特征根。于是我们可以用两颗线段树分别对应两个特征根，维护区间加等比数列、区间求和的操作。

具体维护方法就是懒标记记录区间等比数列的首项，下传操作就是左子树直接继承，右子树利用通项推得。区间更新直接等比数列求和即可。标记的合并直接相加即可。注意预处理两个特征根的 $1$ 至 $n$ 次方。

题解_环鸽的CHONG

考虑分治。对于一个序列区间 $[l,r]$ ,，如果存在元素 $a_{mid}$ 在此区间内唯一，那么只需考虑 $[l,mid-1]$ 和 $[mid+1,r]$ 。
如何找出唯一元素。用map保存每个元素左右侧最近的和自己相同的元素的位置，则对于每个元素是否在 $[l,r]$ 内有相同元素可直接判断。如果从左侧或右侧开始扫描，最坏情况下最后找到唯一元素，那么 $T(n)=T(n-1)+O(n)=O(n^2)$ 。
如果从两次同时向中间开始寻找，最坏情况下唯一元素在中间， $T(n) = T(n/2)+O(n)=O(nlogn)$ 。