题目
给定一个长度为
n
n
n的排列
p
p
p，求有多少区间
[
l
,
r
]
[l,r]
[l,r]满足，
p
[
l
]
+
p
[
r
]
=
m
a
x
p
[
i
]
p[l]+p[r]=max{p[i]}
p[l]+p[r]=maxp[i]，其中
l
<
=
i
<
=
r
l<=i<=r
l<=i<=r
题解
预处理出左边第一个大于
i
i
i的数和右边第一个大于
i
i
i的数(单调栈维护一下即可)左端点显然只能在
(
L
,
i
)
(L,i)
(L,i)，右端点只能在
(
i
,
R
)
(i,R)
(i,R)，枚举长度较小的区间判断是否可行即可
code
#include <bits/stdc++.h>
using namespace std
;
const int N
= 2e5 + 100;
int n
, top
;
int a
[N
], s
[N
], L
[N
], R
[N
], pos
[N
];
int main() {
scanf("%d", &n
);
for (int i
= 1; i
<= n
; ++i
) {
scanf("%d", &a
[i
]);
pos
[a
[i
]] = i
;
}
s
[top
= 0] = 0;
for (int i
= 1; i
<= n
; ++i
) {
while (top
&& a
[i
] > a
[s
[top
]]) top
--;
L
[i
] = s
[top
], s
[++top
] = i
;
}
s
[top
= 0] = n
+ 1;
for (int i
= n
; i
>= 1; --i
) {
while (top
&& a
[i
] > a
[s
[top
]]) top
--;
R
[i
] = s
[top
], s
[++top
] = i
;
}
int ans
= 0;
for (int i
= 1; i
<= n
; ++i
) {
if (i
- L
[i
] < R
[i
] - i
) {
int Max
= a
[i
];
for (int j
= L
[i
] + 1; j
< i
; ++j
) {
int tmp
= a
[j
];
if (pos
[Max
- tmp
] > i
&& pos
[Max
- tmp
] < R
[i
]) ++ans
;
}
}
else {
int Max
= a
[i
];
for (int j
= i
+ 1; j
< R
[i
]; ++j
) {
int tmp
= a
[j
];
if (pos
[Max
- tmp
] > L
[i
] && pos
[Max
- tmp
] < i
) ++ ans
;
}
}
}
printf("%d\n", ans
);
return 0;
}
