Description
Output
6 8 2 7 4 3 5 9 3 2 5 3 1 2 4 3 1 4 2 2 6 3 1 7 5 1 3 3 6 4
Sample Output
5 4 6 9
Data Constraint
Hint
题解
到过来做就是一道裸的可持久化线段树了
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N =
200010;
const int LG =
33;
#define child int t0, int &t, int l = 1, int r = 1e9
#define mid ((l + r) >> 1)
#define ls a[t0].l, a[t].l, l, mid
#define rs a[t0].r, a[t].r, mid + 1, r
struct NOTE
{
int l,r,s;
}a[N *
2 * LG];
int root[N *
2];
int tim;
int tot;
int f[N];
int n, m, x, y, k, op;
void rev(child)
{
a[t = ++tot] = a[t0], ++a[t].s;
if (l == r)
return;
if (x <= mid)
rev(ls);
else rev(rs);
}
int ask(child)
{
if (l == r)
return l;
int tmp = a[a[t0].l].s - a[a[t].l].s;
if (k <= tmp)
return ask(ls);
return k -= tmp, ask(rs);
}
int main()
{
freopen(
"news.in",
"r",stdin);
freopen(
"news.out",
"w",stdout);
scanf(
"%d%d",&n,&m);
for (
int i =
1; i <= n; i++)
scanf(
"%d", f + i);
for (
int i = n; i >=
1; i--)
{
x = f[i];
++tim;
root[tim] = root[tim -
1];
rev(root[tim -
1], root[tim]);
}
while (m--)
{
scanf(
"%d", &op);
if (op ==
1)
{
--tim;
continue;
}
if (op ==
2)
{
scanf(
"%d", &x);
++tim;
root[tim] = root[tim -
1];
rev(root[tim -
1], root[tim]);
continue;
}
scanf(
"%d%d%d", &x, &y, &k);
printf(
"%d\n", ask(root[tim - x +
1], root[tim - y]));
}
}
