抽刀断水水更流，举杯浇愁愁更愁。 Cake题意 给定长为 \(n\) 的数组 \(d\) ，以及一个起始位置 \(a\) 。你会按照如下顺序删除数组中的数： 首先删除 \(d_a\) 。 选出和已删除位置相邻的两
给定长为 \(n\) 的数组 \(d\)，以及一个起始位置 \(a\)。你会按照如下顺序删除数组中的数：
-
首先删除 \(d_a\)。
-
选出和已删除位置相邻的两个数中更小的那一个删除。
接下来有两种操作：
-
操作 \(1\)：将任意一个数 \(d_i\) 提高到第 \(x\) 大，其中 \(x\leq 10\)。
-
操作 \(2\)：询问删除某个数前会删除多少个数。
\(1\leq n\leq 2.5\times 5\times 10 ^ 5,1\leq q \leq 5\times 10 ^ 5,1\leq d_i\leq n\)
数据保证 \(d_i\) 互不相同。
分析注意到，起始位置 \(a\) 不变，不难想到整个序列将别分成两部分分别进行讨论。
仔细推敲可以发现，我们每次的走法一定是走到某个较大值后掉头，遇到某个更大值再掉头……反复如此。
那接下来的想法就很自然了，对于我们来说最有价值的事实上是一个 最大值，因为它最有可能成为往这个方向上扩张的阻碍。
只有当另一边被走完或者另一边出现比当前最大值更大的值，我们才会删除这个值。
所以对于每次操作，我们仅需要找到询问点到起始位置之间的 区间最大值，然后再找到另一边第一个比这个值大的值的位置。前者使用线段树容易维护，后者线段树二分亦不难解决。
对于每次修改，因为每次都是修改到前十名，那我们暴力修改即可。同时注意 \(d_i\) 互不相同并且小于等于 \(n\) 的特点，这是容易进行维护的。
CODE#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10, INF = 1e15;
inline int read()
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
int n, a, m;
int d[N], rk[N], arr[N];
struct Tree{
int tr[N << 2];
inline void build(int k, int l, int r){
if(l == r) { tr[k] = d[l]; return; }
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
tr[k] = max(tr[k << 1], tr[k << 1 | 1]);
}
inline void change(int k, int l, int r, int x, int v){
if(r < x || l > x) return;
if(l == r && l == x) { tr[k] = v; return; }
int mid = (l + r) >> 1;
change(k << 1, l, mid, x, v), change(k << 1 | 1, mid + 1, r, x, v);
tr[k] = max(tr[k << 1], tr[k << 1 | 1]);
}
inline int query(int k, int l, int r, int x, int y){
if(r < x || l > y) return -INF;
if(l >= x && r <= y) return tr[k];
int mid = (l + r) >> 1;
return max(query(k << 1, l, mid, x, y), query(k << 1 | 1, mid + 1, r, x, y));
}
inline int upper_bound_left(int k, int l, int r, int x, int y, int v){
if(r < x || l > y) return -1;
if(tr[k] < v) return -1;
if(l == r) return l;
int mid = (l + r) >> 1, res = upper_bound_left(k << 1 | 1, mid + 1, r, x, y, v);
if(res != -1) return res;
else return upper_bound_left(k << 1, l, mid, x, y, v);
}
inline int upper_bound_right(int k, int l, int r, int x, int y, int v){
if(r < x || l > y) return -1;
if(tr[k] < v) return -1;
if(l == r) return l;
int mid = (l + r) >> 1, res = upper_bound_right(k << 1, l, mid, x, y, v);
if(res != -1) return res;
else return upper_bound_right(k << 1 | 1, mid + 1, r, x, y, v);
}
}T;
char s[N];
signed main()
{
n = read(), a = read();
for(register int i = 1; i <= n; i++){
d[i] = read();
if(n - d[i] + 1 <= 10) rk[n - d[i] + 1] = i;
}
T.build(1, 1, n);
m = read();
int Maxn = n;
while(m--){
scanf("%s", s + 1);
if(s[1] == 'E'){
int lst = min(n, (int)10), pos = read(), val = read();
for(register int i = 1; i <= 10; i++) if(rk[i] == pos) lst = i;
for(register int i = lst - 1; i >= val; i--) rk[i + 1] = rk[i];
rk[val] = pos;
for(register int i = val; i >= 1; i--) Maxn++, T.change(1, 1, n, rk[i], Maxn); //暴力修改
}
if(s[1] == 'F'){
int pos = read();
if(pos == a) { puts("0"); continue; }
if(pos < a){
int mx = T.query(1, 1, n, pos, a - 1);
int k = T.upper_bound_right(1, 1, n, a + 1, n, mx);
if(k == -1) k = n + 1;
printf("%lld\n", k - pos - 1);
}
else{
int mx = T.query(1, 1, n, a + 1, pos);
int k = T.upper_bound_left(1, 1, n, 1, a - 1, mx);
if(k == -1) k = 0;
printf("%lld\n", pos - k - 1);
}
}
}
return 0;
}