E – Lynyrd Skynyrd

题目大意

给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\)，处理\(q\)个询问：在数组的字段\([l,r]\)内是否存在排列的环形偏移。

解法

考虑正向扫描，处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置，并同时更新自己所在的位置供下一次循环进行使用：

// Input these data:
scanf("%d%d%d", &n, &m, &q);
// Make position mapping;
for (int i = 1; i <= n; i++)
    scanf("%d", &perm[i]), pos[perm[i]] = i;
// Make it circular;
perm[0] = perm[n];
for (int i = 1; i <= m; i++)
{
    scanf("%d", &arr[i]);
    // Get the previous position of current number in the permutation;
    int x = perm[pos[arr[i]] - 1];
    // Save data and update the nearest position;
    fa[0][i] = pre[x], pre[arr[i]] = i;
}

然后我们可以考虑倍增：一个位置上的数按照环形序列往回跳多少步。这就是正常操作了。之后，我们可以考虑处理出一个\(g[][]\)倍增数组：用来记录一个位置往回跳\(n-1\)步在数组中所处的位置：

for (int i = 1; (1 << i) <= m; i++)
    for (int j = 1; j <= m; j++)
        fa[i][j] = fa[i - 1][fa[i - 1][j]];
for (int i = 1; i <= m; i++)
{
    int l = n - 1, p = i;
    for (int j = 19; j >= 0; j--)
        if (l & (1 << j))
            p = fa[j][p];
    // Get the position of the previous (n - 1) big steps;
    g[0][i] = p;
}

然后就可以像 ST 表一样操作了：对于一对询问\((l,r)\)，我们可以在\(g\)中找最大的数（也就是最靠近\(r\)的数），然后判断是否大于\(l\)来进行合法验证。

完整代码

// E.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 200;
int perm[MAX_N], pos[MAX_N];
int arr[MAX_N], pre[MAX_N], n, m, q, fa[20][MAX_N], g[20][MAX_N], lg[MAX_N];
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &perm[i]), pos[perm[i]] = i;
    perm[0] = perm[n];
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &arr[i]);
        int x = perm[pos[arr[i]] - 1];
        fa[0][i] = pre[x], pre[arr[i]] = i;
    }
    for (int i = 1; (1 << i) <= m; i++)
        for (int j = 1; j <= m; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    for (int i = 1; i <= m; i++)
    {
        int l = n - 1, p = i;
        for (int j = 19; j >= 0; j--)
            if (l & (1 << j))
                p = fa[j][p];
        g[0][i] = p;
    }
    for (int i = 2; i <= m; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; (1 << i) <= m; i++)
        for (int j = 1; j + (1 << i) - 1 <= m; j++)
            g[i][j] = max(g[i - 1][j], g[i - 1][j + (1 << (i - 1))]);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        int ans = max(g[k][l], g[k][r - (1 << k) + 1]);
        if (ans >= l)
            putchar('1');
        else
            putchar('0');
    }
    return 0;
}

F – U2

题意分析

给出\(n\)个点，考虑每两个\(x\)坐标不相同的点组成一个二次项系数固定的抛物线，请问有多少个点互相组成的抛物线图形内部不包含除自身之外任何一点？

解法

这道题还是相当有意思的。我们考虑删掉没用的点：注定不会被考虑的点。我们可以设点\(A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)\)，其中\(A,B\)组成抛物线\(y=x^2+bx+c\)。\(A,B\)能继续存在的条件是\(y_3<x_3^2+bx_3+c\)。我们可以得到很多这样的不等式，然后发现可以归纳成\(y_3-x_3^2<bx_3+c\)，所以我们在读入点信息时，把点\((x,y)\)的形式置换成\((x,y-x^2)\)，然后考虑求上凸包即可。

代码

// F.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
using namespace std;
const int MAX_N = 101000;
pair<ll, ll> prs[MAX_N];
ll n, tmpx, tmpy, q[MAX_N], tot;
bool check(int a, int b, int c)
{
    ll x1 = prs[b].first - prs[a].first, y1 = prs[b].second - prs[a].second;
    ll x2 = prs[c].first - prs[b].first, y2 = prs[c].second - prs[b].second;
    return x1 * y2 - x2 * y1 >= 0;
}
int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &tmpx, &tmpy);
        prs[i].first = tmpx, prs[i].second = tmpy - tmpx * tmpx;
    }
    sort(prs + 1, prs + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        while (tot >= 1 && prs[q[tot]].first == prs[i].first)
            tot--;
        while (tot >= 2 && check(q[tot - 1], q[tot], i))
            tot--;
        q[++tot] = i;
    }
    printf("%d", tot - 1);
    return 0;
}