又双叒叕是题外话

今天模拟考是原题大战。

$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$的哈希数组

现在的目标就是:资瓷单点修改和区间查询(正反都要)

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

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

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

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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");
}
}

 评论