由于一直无法理解扩展欧几里得算法以及背不下代码，于是花了半节生物课推了一个可以使用普通gcd快速幂代替扩展欧几里得算法的东西….qwq
扩展欧几里得算法解的是方程$ax+by=c$，我们先把方程做一些处理，设$d=gcd(a,b)$,如果$c\ mod\ d \neq 0$，则原方程无整数解，否则方程两边同时除以$d$得到新方程$ex+fy=g$。
将该方程放到膜$f$意义下可得$ex=g(mod\ f)$，然后因为$e$与$g$互质，所以方程两边同时乘$e^{-1}$(可以通过快速幂求出)可得$x=e^{-1}g(mod\ f)$，于是解出$x$,将$x$代入原方程即可解出$y$。
虚树+树形DP
建虚树的时候，清空数组可能被卡
由于需要查询原树上两点之间权值最小的边，所以用到了树剖。
LCA一开始用的欧拉序列，后来发现树剖也可以接受。
// luogu-judger-enable-o2
#include
#include
#include
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using int_t = int_fast64_t;
const int_t LARGE = 300000;
int_t read()
{
int_t x;
scanf("%lld", &x);
return x;
}
void print(int_t x)
{
printf("%lld", x);
}
struct Struct
{
int_t depth;
int_t vertex;
};
bool operator<(const Struct a, const Struct b)
{
return a.depth < b.depth;
}
struct Edge
{
int_t to;
int_t weight;
};
vector graph[LARGE + 1];
int_t counter = 0;
Struct ST[LARGE * 2 + 2 + 1][20];
int_t dfsSeq[LARGE + 1];
int_t depth[LARGE + 1];
int_t values[LARGE + 1];
int_t maxChild[LARGE + 1];
int_t size[LARGE + 1];
int_t T_ST[LARGE + 1];
int_t ST_T[LARGE + 1];
int_t top[LARGE + 1];
int_t ST2[LARGE + 1][20];
int_t parent[LARGE + 1];
int_t pow2[LARGE + 1];
int_t DFSN[LARGE + 1];
int_t first[LARGE + 1];
int_t n, m;
void pushedge(int_t from, int_t to, int_t weight)
{
graph[from].push_back({to, weight});
graph[to].push_back({from, weight});
}
int_t DFS0(int_t vertex, int_t from = -1, int_t depth = 1)
{
ST[++counter][0] = {depth, vertex};
dfsSeq[++dfsSeq[0]] = vertex;
if (from == -1)
values[vertex] = (int64_t)0x7fffffff;
size[vertex] = 1;
int_t maxChildID = -1;
int_t maxChildN = 0;
for (auto &edge : graph[vertex])
{
if (edge.to != from)
{
values[edge.to] = edge.weight;
int_t x = DFS0(edge.to, vertex, depth + 1);
ST[++counter][0] = {depth, vertex};
if (x > maxChildN)
{
maxChildN = x;
maxChildID = edge.to;
}
size[vertex] += x;
}
}
maxChild[vertex] = maxChildID;
return size[vertex];
}
void DFS(int_t vertex, int_t from = -1, int_t depth = 1)
{
parent[vertex] = from;
if (from == -1)
top[vertex] = vertex;
ST_T[0]++;
ST_T[ST_T[0]] = vertex;
T_ST[vertex] = ST_T[0];
if (maxChild[vertex] > 0)
{
top[maxChild[vertex]] = top[vertex];
DFS(maxChild[vertex], vertex, depth + 1);
}
::depth[vertex] = depth;
for (auto &edge : graph[vertex])
{
if (edge.to != from && edge.to != maxChild[vertex])
{
top[edge.to] = edge.to;
DFS(edge.to, vertex, depth + 1);
}
}
}
void init()
{
DFS0(1);
DFS(1);
for (int_t i = 1; i <= n; i++)
ST2[i][0] = values[ST_T[i]];
for (int_t j = 1; pow2[j] <= n; j++)
{
for (int_t i = 1; i + pow2[j] - 1 <= n; i++)
{
ST2[i][j] = std::min(ST2[i][j - 1], ST2[i + pow2[j - 1]][j - 1]);
}
}
for (int_t j = 1; pow2[j] <= counter; j++)
{
for (int_t i = 1; i + pow2[j] - 1 <= counter; i++)
{
ST[i][j] = std::min(ST[i][j - 1], ST[i + pow2[j - 1]][j - 1]);
}
}
for (int_t i = 1; i <= counter; i++)
{
if (first[ST[i][0].vertex] == 0)
{
first[ST[i][0].vertex] = i;
}
}
for (int_t i = 1; i <= n; i++)
{
DFSN[dfsSeq[i]] = i;
}
}
int_t getLCA(int_t v1,int_t v2) {
int_t top1=top[v1];
int_t top2=top[v2];
while(top1!=top2){
if(depth[top1] b)
// std::swap(a, b);
// int_t k = log2(b - a + 1);
// return std::min(ST[a][k], ST[b - pow2[k] + 1][k]).vertex;
//}
int_t queryST2(int_t a, int_t b)
{
if (a > b)
return 0x7fffffff;
int_t k = log2(b - a + 1);
// printf("ST2 %d(rt:%d) %d(rt:%d) k = %d = %d\n",a,ST_T[a],b,ST_T[b],k,std::min(ST2[a][k],ST2[b-pow2[k]+1][k]));
// cout< depth[v2])
std::swap(v1, v2);
result = std::min(result, queryST2(T_ST[v1] + 1, T_ST[v2]));
return result;
}
auto func = [&](int_t a, int_t b) -> bool {
return DFSN[a] < DFSN[b];
};
struct Processor
{
std::unordered_map> graph;
bool rich[LARGE + 1];
int_t n;
int_t querys[LARGE * 2 + 1];
int_t cnt = 0;
void pushedge(int_t from, int_t to)
{
// if(graph.count(from)==false) graph[from]=vector();
// if(graph.count(to)==false) graph[to]=vector();
graph[from].push_back(to);
graph[to].push_back(from);
}
void process()
{
cnt = 0;
graph.clear();
n = read();
querys[++cnt] = 1;
for (int_t i = 1; i <= n; i++)
{
int_t x;
x = read();
querys[++cnt] = x;
rich[x] = true;
}
std::sort(&querys[1], &querys[cnt + 1], func);
int_t size = cnt;
for (int_t i = 1; i < size; i++)
{
querys[++cnt] = getLCA(querys[i], querys[i + 1]);
}
std::sort(&querys[1], &querys[cnt + 1], func);
cnt = (std::unique(&querys[1], &querys[cnt + 1]) - &querys[1]);
std::stack stack;
for (int_t i = 1; i <= cnt; i++)
{
int_t vertex = querys[i];
if (stack.empty())
{
stack.push(vertex);
continue;
}
while (getLCA(stack.top(), vertex) != stack.top())
stack.pop();
pushedge(stack.top(), vertex);
stack.push(vertex);
}
print(search(1));
putchar('\n');
for (int_t i=1;i<=cnt;i++)
rich[querys[i]] = false;
}
int_t search(int_t vertex, int_t from = -1)
{
int_t result = 0;
for (auto x : graph[vertex])
{
if (x != from)
{
if (rich[x])
{
result += minEdge(x, vertex);
}
else
{
result += std::min(minEdge(x, vertex), search(x, vertex));
}
}
}
return result;
}
} p;
int main()
{
// freopen("data.txt","r",stdin);
// freopen("out1.txt","w",stdout);
for (int_t i = 1; i <= 21; i++)
{
pow2[0] = 1;
pow2[i] = pow2[i - 1] * 2;
}
n = read();
for (int_t i = 1; i <= n - 1; i++)
{
int_t from, to, weight;
from = read();
to = read();
weight = read();
pushedge(from, to, weight);
}
init();
int_t m = read();
for (int_t i = 1; i <= m; i++)
{
p.process();
}
return 0;
}
我的内心十分激动，甚至想写一篇博客qwq
写了接近五个月的模板，总算过了。
然而现在我也不知道一开始的代码哪里有问题..
https://www.luogu.org/problemnew/show/P3384
// luogu-judger-enable-o2
#include
#include
#include
#include
#include
using std::cin;
using std::endl;
using std::cout;
using std::vector;
using std::min;
using std::swap;
using std::max;
using std::string;
typedef long long int int_t;
const int_t LARGE = 100000;
int_t p;
struct Node {
Node* left;
Node* right;
int_t sum;
int_t mark;
int_t begin;
int_t end;
Node(int_t begin, int_t end) {
left = right = NULL;
sum = mark = 0;
this->begin = begin;
this->end = end;
}
int_t length() {
return end - begin + 1;
}
void pushdown() {
if (left) {
left->add(mark);
}
if (right) {
right->add(mark);
}
mark = 0;
}
void add(int_t val) {
mark += val;
sum += length() * val;
mark %= p;
sum %= p;
}
void maintain() {
if (begin == end) return;
sum = (left->sum + right->sum) % p;
}
} *root;
Node* build(int_t begin, int_t end, int_t* data) {
Node* node = new Node(begin, end);
if (begin == end) {
node->sum = data[begin];
} else {
int_t mid = (begin + end) / 2;
node->left = build(begin, mid, data);
node->right = build(mid + 1, end, data);
node->maintain();
}
return node;
}
int_t querySum(int_t begin, int_t end, Node* node = root) {
if (end < node->begin || begin > node->end) return 0;
if (node->begin >= begin && node->end <= end) return node->sum;
node->pushdown();
return (querySum(begin, end, node->left) + querySum(begin, end, node->right)) % p;
}
void update(int_t begin, int_t end, int_t value, Node* node = root) {
if (end < node->begin || begin > node->end) return;
if (node->begin >= begin && node->end <= end) {
node->add(value);
return;
}
node->pushdown();
update(begin, end, value, node->left);
update(begin, end, value, node->right);
node->maintain();
}
int_t parent[LARGE + 1];
int_t depth[LARGE + 1];
int_t heavyChild[LARGE + 1];
int_t size[LARGE + 1];
int_t top[LARGE + 1];
int_t nodeValues[LARGE + 1];
//线段树上的某个点对应着原树上的那个点
int_t ST_T[LARGE + 1];
//原树上的某个点对应线段树上的某个点
int_t T_ST[LARGE + 1];
int_t segValues[LARGE + 1];
vector graph[LARGE + 1];
int_t DFS1(int_t vertex, int_t from = 0, int_t depth0 = 1) {
parent[vertex] = from;
depth[vertex] = depth0;
int_t currSize = 1;
int_t currMaxChd = -1;
int_t currMaxSize = 0;
for (int_t i = 0; i < graph[vertex].size(); i++) {
int_t& target = graph[vertex][i];
if (target == from) continue;
int_t temp = DFS1(target, vertex, depth0 + 1);
if (temp > currMaxSize) {
currMaxSize = temp;
currMaxChd = target;
}
currSize += temp;
}
heavyChild[vertex] = currMaxChd;
size[vertex] = currSize;
return currSize;
}
void DFS2(int_t vertex) {
if (vertex <= 0) return;
T_ST[vertex] = ++ST_T[0];
ST_T[T_ST[vertex]] = vertex;
segValues[ST_T[0]] = nodeValues[vertex];
if (graph[vertex].empty() == false) {
top[heavyChild[vertex]] = top[vertex];
DFS2(heavyChild[vertex]);
}
for (int_t i = 0; i < graph[vertex].size(); i++) {
int_t& target = graph[vertex][i];
if (target == heavyChild[vertex]) continue;
if (target == parent[vertex]) continue;
top[target] = target;
DFS2(target);
}
}
int_t treeSum(int_t v1, int_t v2) {
int_t sum = 0;
int_t top1 = top[v1];
int_t top2 = top[v2];
while (top[v1] != top[v2]) {
if (depth[top1] < depth[top2]) {
swap(top1, top2);
swap(v1, v2);
}
sum += querySum(T_ST[top1], T_ST[v1]);
sum %= p;
v1 = parent[top1];
top1 = top[v1];
}
if (depth[v1] > depth[v2]) swap(v1, v2);
sum += querySum(T_ST[v1], T_ST[v2]);
return sum % p;
}
void treeAdd(int_t v1, int_t v2, int_t value) {
int_t top1 = top[v1];
int_t top2 = top[v2];
while (top[v1] != top[v2]) {
if (depth[top1] < depth[top2]) {
swap(top1, top2);
swap(v1, v2);
}
update(T_ST[top1], T_ST[v1], value);
v1 = parent[top1];
top1 = top[v1];
}
if (depth[v1] > depth[v2]) swap(v1, v2);
update(T_ST[v1], T_ST[v2], value);
}
int main() {
int_t n, m, root;
cin >> n >> m >> root>>p;
for (int_t i = 1; i <= n; i++) {
cin >> nodeValues[i];
}
for (int_t i = 1; i <= n - 1; i++) {
int_t from, to;
cin >> from>>to;
graph[from].push_back(to);
graph[to].push_back(from);
}
DFS1(root);
top[root] = root;
DFS2(root);
::root = build(1, n, segValues);
for (int_t i = 1; i <= m; i++) {
int_t opt;
cin>>opt;
if (opt == 1) {
int_t v1, v2, value;
cin >> v1 >> v2>>value;
treeAdd(v1, v2, value);
} else if (opt == 2) {
int_t v1, v2;
cin >> v1>>v2;
cout << treeSum(v1, v2) % p << endl;
} else if (opt == 3) {
int_t v, value;
cin >> v>>value;
update(T_ST[v], T_ST[v] + size[v] - 1, value);
} else if (opt == 4) {
int_t v;
cin>>v;
cout << querySum(T_ST[v], T_ST[v] + size[v] - 1) % p << endl;
}
}
}
题目见https://www.luogu.org/problemnew/show/P3317
题意：
求$$\sum _{T}\prod _{e \in T} w_e\prod _{e\notin T}(1-w_e)\ \ \ \ \ T是原图的一颗生成树$$
这个式子可能没有办法直接计算，所以我们需要作以下修改
$$\prod _{e}(1-w_e) \sum _T \prod _{e\in T}\frac {w_e} {1-w_e}$$
这个式子跟原来的式子是等价的。
这样的话 $$\sum _T \prod _{e\in T}\frac {w_e} {1-w_e}$$就可以使用矩阵树定理计算了
注意 可能会出现除数为0的情况 所以所有涉及到除法的地方都要特判 如果除0 就需要改为除一个特别小的数
// luogu-judger-enable-o2
#include
#include
#include
#include
#include
using std::cin;
using std::endl;
using std::cout;
typedef int64_t int_t;
typedef double real_t;
const int_t LARGE=50;
const real_t EPS=1e-9;
struct Matrix {
int_t n,m;
real_t data[LARGE+1][LARGE+1];
Matrix(int_t n,int_t m) {
this->n=n;
this->m=m;
for(int_t i=1; i<=n; i++) {
for(int_t j=1; j<=m; j++) {
data[i][j]=0;
}
}
}
real_t& operator()(int_t r,int_t c) {
return data[r][c];
}
Matrix operator-(Matrix another) {
Matrix result(n,m);
for(int_t i=1; i<=n; i++) {
for(int_t j=1; j<=m; j++) {
result(i,j)=data[i][j]-another(i,j);
}
}
return result;
}
//对该矩阵执行高斯消元
void gauss() {
//枚举消哪一个未知数
for(int_t i=1; i<=n; i++) {
//枚举对哪一行进行消元
for(int_t j=i+1; j<=n; j++) {
real_t x=data[i][i];
if(fabs(x)>n;
real_t result=1;
//度数矩阵
Matrix A(n,n);
//邻接矩阵
Matrix B(n,n);
for(int_t i=1; i<=n; i++) {
for(int_t j=1; j<=n; j++) {
cin>>B(i,j);
}
}
for(int_t i=1; i<=n; i++) {
for(int_t j=i+1; j<=n; j++) {
real_t x=(1-B(i,j));
if(fabs(x)
手推出来的为数不多的几道数学题，突然很想写一篇博客..
http://lifecraft-mc.com:81/problem/1026
题意：设d(ij)表示ij的约数个数，求
#\sum _{i=1}^N \sum _{j=1}^M d(ij)#
,$N,M\leq 50000$ 50000组数据
首先，$d(ij)=\sum _{x|i}\sum _{y|j}[gcd(x,y)==1]$(其中[gcd(x,y)==1]表示gcd(x,y)=1时，值为1，否则为0)
一个很好的处理[xxx]的方法:$[x==1]=\sum _{i|x}\mu(i)$
然后可得#\sum _{i=1}^N\sum _{j=1}^M\sum _{x|i}\sum _{y|j} [gcd(x,y)==1]=\sum _{i=1}^N\sum _{j=1}^M\sum _{x|i}\sum _{y|j}\sum _{k|gcd(x,y)}\mu(k)#
有一个结论，一个数n的约数的集合中每个数除以k所得的集合等于n/k约数的集合，所以枚举k可以得到
#\sum _{k=1}^N\sum _{i=1}^{\frac N k}\sum _{j=1}^{\frac M k}\sum _{x|i}\sum _{y|j}\mu(k)#
原先我们根据i j来枚举x y 现在我们根据x y来枚举i j
#\sum _{k=1}^N \mu(k) \sum _{x=1}^{\frac N k} \sum _{y=1}^{\frac M k} \sum _{x|i}\sum _{y|j} = \sum _{k=1}^N \mu(k) \sum _{x=1}^{\frac N k} \sum _{y=1}^{\frac M k} \frac N {kx} \frac M {ky}#
继续
#\sum _{k=1}^N\mu(k)\sum _{x=1}^{\frac N k}\frac N{kx}\sum _{y=1}^{\frac M k}\frac M{ky}#
可以发现最后两个求和符号有相似的外形，所以我们可以把他们统一起来，设
#f(n)=\sum _{x=1}^N \frac N x#
原式可变形为
#\sum _{k=1}^N \mu(k)f(\frac N k)f(\frac M k)#
这样的话可以预处理出所有的f(n),每组询问就可以在sqrt(N)的时间内处理.
注意几个问题
1.求值结束之后，不能直接除以多项式的长度，而应该乘以其逆元
2.如果写迭代版本，进行位翻转时一定要全部翻转。
附代码(http://lifecraft-mc.com:81/problem/1087):
#include
#include
#include
#include
#include
#include
#include
#include
using std::cin;
using std::endl;
using std::cout;
using std::vector;
using std::swap;
using std::ostream;
using std::istream;
typedef unsigned long long int int_t;
typedef vector vec_t;
const int_t mod=479ull*(1ull<<21)+1;
const int_t g=3;
int_t fastPower(int_t base,int_t index){
int_t result=1;
while(index){
if(index&1){
result=(result*base)%mod;
}
index>>=1;
base=(base*base)%mod;
}
return result;
}
inline int_t inv(int_t x){
return fastPower(x,mod-2);
}
int_t g0(int_t n){
return fastPower(g,(mod-1)/n);
}
int_t reverse(int_t x,int_t size){
int_t result=0;
for(int_t i=0;i>=1;
}
result|=(x&1);
return result;
}
vec_t FNT(vec_t rec){
if(rec.size()==1) return rec;
vec_t a0,a1;
for(int_t i=0;i>=1;
}
return result%mod;
}
int main(){
int_t n,m;
cin>>n>>m;
int_t length=upper2n(n+m+2);
vec_t A(length,0),B(length,0);
for(int_t i=0;i<=n;i++)cin>>A[i];
for(int_t i=0;i<=m;i++)cin>>B[i];
A=FNT(A);
B=FNT(B);
for(int_t i=0;i
可以生成王境泽的gif
https://sorry.xuty.tk/wangjingze/
64位汇编器下，%rax等寄存器的大小为8字节，不可以直接mov到%eax等4字节寄存器
__asm__ (指令列表:输出表:输入表:修改标识)
输入 输出表格式”寄存器”（c表达式）
寄存器前可用= +修饰
=：表明该表达式只能写，只能放在输出表里
+标明改表达式可读可写，同样只能放在输出表里
留空，标明该表达式只读
各种表达式约束
r:I/O,表示使用一个通用寄存器,由GCC在%eax/%ax/%al、%ebx/%bx/%bl、%ecx/%cx/%cl、%edx/%dx/%dl中选取一个GCC认为是合适的;
q:I/O,表示使用一个通用寄存器,与r的意义相同;
g:I/O,表示使用寄存器或内存地址;
m:I/O,表示使用内存地址;
a:I/O,表示使用%eax/%ax/%al;
b:I/O,表示使用%ebx/%bx/%bl;
c:I/O,表示使用%ecx/%cx/%cl;
d:I/O,表示使用%edx/%dx/%dl;
D:I/O,表示使用%edi/%di;
S:I/O,表示使用%esi/%si;
f:I/O,表示使用浮点寄存器;
t:I/O,表示使用第一个浮点寄存器;
u:I/O,表示使用第二个浮点寄存器;
A:I/O,表示把%eax与%edx组合成一个64位的整数值;
o:I/O,表示使用一个内存位置的偏移量;
V:I/O,表示仅仅使用一个直接内存位置;
i:I/O,表示使用一个整数类型的立即数;
n:I/O,表示使用一个带有已知整数值的立即数;
F:I/O,表示使用一个浮点类型的立即数;
// luogu-judger-enable-o2
#include
#include
#include
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::string;
struct Node;
typedef int int_t;
typedef Node* NodePtr;
struct Node {
NodePtr left;
NodePtr right;
NodePtr parent;
int_t size;
int_t id;
int_t priority;
Node(int_t id) {
left = right = parent = 0;
size = 1;
this->id = id;
priority = rand();
}
int_t leftSize() {
if (left) return left->size;
else return 0;
}
void maintain() {
size = 1;
if (left) {
size += left->size;
left->parent = this;
}
if (right) {
size += right->size;
right->parent = this;
}
}
};
typedef pair pair_t;
NodePtr root = 0;
//??left??right??????????¡Á??¡Â,¡¤????¡Â?¨´
NodePtr merge(NodePtr left, NodePtr right) {
if (left == 0) {
return right;
} else if (right == 0) {
return left;
} else {
if (left->priority > right->priority) {
left->right = merge(left->right, right);
left->maintain();
return left;
} else {
right->left = merge(left, right->left);
right->maintain();
return right;
}
}
}
//??node¡¤????????¡Â??????¡Á¨®¡À???¡Á??¡Â??size??????
pair_t split(NodePtr node, int_t size) {
if (node == 0) {
return make_pair((NodePtr) 0, (NodePtr) 0);
} else if (node->leftSize() == size) {
pair_t result = make_pair(node->left, node);
node->parent = 0;
node->left = 0;
node->maintain();
return result;
} else if (node->leftSize() > size) {
pair_t result = split(node->left, size);
node->left = result.second;
if (result.first)
result.first->maintain();
node->maintain();
return make_pair(result.first, node);
} else if (node->leftSize() < size) {
pair_t result = split(node->right, size - node->leftSize() - 1);
node->right = result.first;
node->maintain();
if (result.second)
result.second->maintain();
return make_pair(node, result.second);
}
}
//??node??????????¡¤???????
void mid(NodePtr x = root) {
if (x == 0) return;
mid(x->left);
cout << x->id << " ";
mid(x->right);
}
void pre(NodePtr x = root) {
if (x == 0) return;
cout << x->id << " ";
pre(x->left);
pre(x->right);
}
inline int_t getRank(NodePtr node) {
int_t k = node->leftSize();
while (node->parent != 0) {
node->maintain();
if (node == node->parent->right) {
k += node->parent->leftSize() + 1;
}
node = node->parent;
}
return k;
}
//返回以root为根的树中 有k个比他小的元素的指针
NodePtr kth(NodePtr node, int_t k) {
if (node->leftSize() == k) return node;
else if (k < node->leftSize()) return kth(node->left, k);
else return kth(node->right, k - node->leftSize() - 1);
}
void pushTop(NodePtr node) {
int_t k = getRank(node);
pair_t result = split(root, k);
pair_t result2 = split(result.second, 1);
root = merge(result2.first, merge(result.first, result2.second));
}
void pushBottom(NodePtr node) {
int_t k = getRank(node);
pair_t result = split(root, k);
pair_t result2 = split(result.second, 1);
root = merge(merge(result.first, result2.second), result2.first);
}
//移动node d个位置
//本函数有毒 建议重写
void move(NodePtr node, int_t d) {
if (d == 0) return;
int_t k = getRank(node);
//将node从序列里拿出来
pair_t pair1 = split(root, k);
pair_t pair2 = split(pair1.second, 1);
root = merge(pair1.first, pair2.second);
if (d == -1) {
pair_t pair = split(root, k - 1);
root = merge(merge(pair.first, node), pair.second);
} else {
pair_t pair = split(root, k + 1);
root = merge(merge(pair.first, node), pair.second);
}
}
static Node * positions[100000 + 1];
int main() {
//????¡À¨¤????i???¨¦??????????
srand(19260817);
int_t n, m;
cin >> n>>m;
for (int_t i = 1; i <= n; i++) {
int_t val;
cin>>val;
root = merge(root, positions[val] = new Node(val));
}
for (int_t i = 1; i <= m; i++) {
// root->parent = 0;
string operation;
cin>>operation;
if (operation == "Top") {
int_t id;
cin>>id;
pushTop(positions[id]);
} else if (operation == "mid") {
mid();
} else if (operation == "pre") {
pre();
} else if (operation == "exit") {
return 0;
} else if (operation == "Bottom") {
int_t id;
cin>>id;
pushBottom(positions[id]);
} else if (operation == "Insert") {
int_t id, t;
cin >> id>>t;
move(positions[id], t);
} else if (operation == "Ask") {
int_t id;
cin>>id;
cout << getRank(positions[id]) << endl;
} else if (operation == "Query") {
int_t k;
cin>>k;
cout << kth(root, k - 1)->id << endl;
}
root->parent = 0;
}
return 0;
}