题解 CF452F Permutation

又双叒叕是题外话

今天模拟考是原题大战。

$T1$ 是这题。
$T2$ 是某次 $CF\ Div1\ E$ 题。
$T3$ 反正是某道神仙题。

~~像我这样的菜鸡只能来做做相对可做的T1~~

~~虽然只是相对可做但是还是被全场切穿了啊喂~~

~~内心OS：这个不订正的理由真的nice~~

思路

我们看到题面要求求的三元组，然后瞎变形一下

\begin{aligned} a_j - a_i &= a_k - a_i\\ a_i + a_k &= 2 a_j \\ a_k &= 2a_j - a_i\\ \end{aligned}

这样子，我们开始试图枚举 $j$ ，之后我们就有一个美妙的性质

在 $j$ 确定的情况下，对于一个 $a_i$ 有对应的 $a_j$ 可以组成三元组当且仅当

$2a_j - a_i$ 存在（废话）

$2a_j - a_i$ 与 $a_j$ 在 $a_i$ 的不同侧

（如果第二点看不懂可以直接看下面的进一步推导）

我们用 $s_i$ 表示 $i$ 这个数在 $j$ 左边的位置有没有出现过

那么我们可以把上面的两点东西给弄出来，那么就是

$\forall\ 1 \leq 2a_j - a_i \leq n, s_{a_i} \neq s_{2a_j - a_i}$

变换一下，变成不能组成三元组的条件，那就是

$\forall\ 1 \leq 2a_j - a_i \leq n, s_{a_i} = s_{2a_j - a_i}$

表示在图上，那就可以画成这样↓

（就是红色部分和绿色部分是对称的）
（反正这个意思感性理解一下）

好，然后我们接下来可以愉快地对 $s$ 进行哈希了。

我们接下来考虑如何动态地维护 $s$ 的哈希数组

现在的目标就是：资瓷单点修改和区间查询（正反都要）

实际上一个线段树就可以解决了

每个节点维护正反两个哈希值

就可以轻松写意地切掉此题。

这是我在模拟考时候写的代码，丑的一批。

代码实现

#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define mod 998244353
#define lc(a) (a << 1)
#define rc(a) (a << 1 | 1)
#define add(a, b) ((a) + (b) >= mod ? (a) + (b) - mod : (a) + (b))
#define minus(a, b) ((a) < (b) ? (a) - (b) + mod : (a) - (b))
#define mul(a, b) ((a) * (ll)(b) % mod)

int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}
int a[300010];
int s[300010];
int powmod[300010];
struct SEG{
    int l;
    int r;
    int sum;
    int rev;

    SEG operator + (const SEG &b) const { // 为了方便查询的时候我把push_up给直接写成这种形式了
        if(l == -1)  // (SEG){-1, -1, -1, -1}  代表空的一段
            return b;
        if(b.l == -1)
            return (SEG){l, r, sum, rev};
        return (SEG){l, b.r, add(mul(sum, powmod[b.r - b.l + 1]), b.sum), add(mul(b.rev, powmod[r - l + 1]), rev)};
    }
};
struct SEG_Tree{
    SEG t[2400000];

    void push_up(int cur){
        t[cur] = t[lc(cur)] + t[rc(cur)];
    }

    void build(int cur, int l, int r){
        t[cur].l = l;
        t[cur].r = r;
        t[cur].sum = t[cur].rev = 0;
        if(l == r){
            t[cur].sum = t[cur].rev = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lc(cur), l, mid);
        build(rc(cur), mid + 1, r);
        push_up(cur);
    }

    void modify(int cur, int pos, int c){
        if(t[cur].l == t[cur].r){
            t[cur].sum = t[cur].rev = c;
            return ;
        }
        if(pos <= t[lc(cur)].r)
            modify(lc(cur), pos, c);
        else
            modify(rc(cur), pos, c);
        push_up(cur);
    }

    SEG query(int cur, int l, int r){
        if(t[cur].l > r || t[cur].r < l)
            return (SEG){-1, -1, -1, -1};
        // printf("[%d, %d], query(%d, %d), {%d, %d}\n", t[cur].l, t[cur].r, l, r, t[cur].sum, t[cur].rev);
        if(t[cur].l >= l && t[cur].r <= r)
            return t[cur];
        return query(lc(cur), l, r) + query(rc(cur), l, r);
    }
}t;

int main(){
    int n = inp();
    for(int i = 1; i <= n; i++)
        a[i] = inp();
    powmod[0] = 1;
    for(int i = 1; i <= n; i++)
        powmod[i] = (powmod[i - 1] << 1) % mod;
    t.build(1, 1, n);
    bool flg = false;
    for(int i = 1; i <= n; i++){
        t.modify(1, a[i], 1);
        // printf("--------------------\na[i] = %d\n", a[i]);
        if((a[i] << 1) - 1 <= n){
            if(a[i] > 1 && t.query(1, 1, a[i] - 1).sum != t.query(1, a[i] + 1, (a[i] << 1) - 1).rev){
                flg = true;
                break;
            }
        } else {
            if(a[i] < n && t.query(1, a[i] + 1, n).rev != t.query(1, (a[i] << 1) - n, a[i] - 1).sum){
                flg = true;
                break;
            }
        }
    }
    if(flg){
        printf("YES\n");
    } else {
        printf("NO\n");
    }
}

Dilute

题解 CF452F Permutation

又双叒叕是题外话

思路

代码实现