#include<iostream>
using namespace std;

const int N = 100010;
//head 表示头结点的指针是多少
//e[i] 表示节点i的值是多少
//ne[i] 表示节点i的next指针是多少
//idx 储存当前已经用到了哪个点
int head,e[N],ne[N],idx;

//初始化
void init()
{
    head = -1;//数组模拟使用-1来表示空
    idx = 0;
}

//将x插入到头结点的位置`在这里插入代码片`
void add_to_head(int x)
{
    e[idx] = x;//存下值
    ne[idx] = head;//存下next指针
    head = idx;//更新头结点
    idx ++;
}

//将x插入到下标为k的结点后面
void add(int k,int x)
{
	e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

//删除下标是k的后面的点
void remove(int k)
{
    ne[k] = ne[ne[k]];//指向下一个的下一个
}

int main()
{
    return 0;
}

#include<iostream>
using namespace std;

const int N = 100010;
int n;
int e[N],l[N],r[N],idx; //这里就不用定义头结点和尾结点了，我们可以使用第0个点和第1个点偷懒，e[N]代表结点中存储的值，r[N]代表每一个结点的下一个点的指针（也就是数组存储中的下标），l[N]代表每一个结点上一个点的指针，idx记录现在已经使用到了哪个数组下标

//初始化
void init(){
    //0表示左端点，1表示右端点
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

//第k点的右边插入   在k的左边插入一个新的点直接调用add(l[k],x)，也就是在k的左边插入等于在k的左边第一个点的右边插入一个点
void add(int k,int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}

//删除结点
void remove(int k){
    r[l[k]] = r[k]; //k点左边的第一个点的右指针指向k点的右结点，直接跳过k点
    l[r[k]] = l[k]; //k点右边的第一个点的左指针指向k点的左结点，直接跳过k点
}

int main(){
	return 0;
}

#include<iostream>
using namespace std;

const int N = 100010;
int stk[N],tt;//stk数组所代表的就是栈，tt代表的是栈顶元素的下标

//插入
stk[++ tt] = x;//就是将新的元素放在了数组的最右端，并且将其下标记录

//删除栈顶元素
tt --;//栈顶元素的下标记录减一，就相当于删除了栈顶元素

//判断是否为空
if(tt > 0) not empty;
else empty;

//取出栈顶元素
stk[tt];

int main()
{
    return 0;
}

#include<iostream>
using namespace std;

const int N = 100010;
int q[N],hh,tt;//hh表示队头元素，tt表示队尾元素

//插入
h[++tt] = x;

//弹出
hh++;

//判断是否为空
if(hh <= tt) not empty;
else empty;

//取出队头元素
q[hh];
 
int main()
{
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;

int n,stk[N],tt;//stk数组模拟栈，tt记录栈顶元素

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false); //输入优化，使得cin的输入更快
    cin >> n;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= x)tt--; //判断栈顶元素是否大于等于当前插入元素
        if(tt) cout << stk[tt] <<" ";  //如果栈不为空，并且上一个判断完成，说明此时的栈顶元素就满足条件
        else cout << "-1 ";            //如果栈为空，并且上一个判断完成，说明这些数据中这个数的左边没有满足条件的数
        stk[++tt] = x;                 //向栈中插入新的元素
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1000010; //数据范围较大，注意使用scanf和printf输入输出，或者使用ios优化和tie优化

int n,k;
int a[N],q[N];//a数组是用来存储数组，q数组是用来存储队列

int main()
{
    int hh = 0,tt = -1;//hh表示队头，tt表示队尾
    scanf("%d%d",&n,&k);
    for(int i = 0; i < n; i ++) scanf("%d",&a[i]);
    
    for(int i = 0; i < n; i ++){
        //判断队头是否滑出窗口，每一次最多向后移动一位，所以就算是滑出也只有一位的差距，所以只用写出一个判断不需要使用循环，判断滑出窗口后就将对头向后移动一位就能重新进入窗口了。
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        //判断新进队列的数和当前队列中的队尾哪个数字大，如果当前队列队尾数字更大，就直接去掉这个数字，因为寻找最小值，那么当前读入的数字一定比当前队列队尾数字更大的话，那么它就一定是作为窗口中的最小值
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[++ tt] = i;//插入数据
        if(i >= k - 1) printf("%d ",a[q[hh]]);//输出，队列是一个一个进的，所以前k - 1个数字依次进入窗口中的时候，窗口中的数字还不是k个，这个时候还没有输出，所以需要判断一下
    }
    
    puts("");
    
    //最大值做法基本一致，只需要更改输入时的判断条件即可
    hh = 0,tt = -1;
    scanf("%d%d",&n,&k);
    for(int i = 0; i < n; i ++) scanf("%d",&a[i]);
    
    for(int i = 0; i < n; i ++){
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] < a[i]) tt --;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d ",a[q[hh]]);
    }
    
    puts("");
    return 0;
}

for(int i = 0; i < n; i ++){
    bool flag = true;
    for(int j = 0; j < n; j ++){
        if(s[j] != p[j]){
            flag = false;
            break;
        }
    }
}

#include <iostream>
using namespace std;
const int N = 100010,M = 1000010;
int n,m;
char p[N],s[M];//s数组就是模板字符串，p数组就是目标字符串
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    
    //求next数组，其实与KMP核心思想类似，差别就是拿着两个相等的字符串再进行比较，去寻找模板字符串中的每个i所能对应的最大的j。然后将这个j更新到next数组中
    for(int i = 2, j = 0; i <= n; i ++){ //首先，i从2开始
        while(j && p[i] != p[j + 1]) j = ne[j]; //如果j不为0，并且字符不匹配，那么就相当于将目标字符串向前移动
        if(p[i] == p[j + 1]) j ++;//如果匹配成功，那么就能将j向后移动
        ne[i] = j; //更新next
    }
    
    //KMP核心
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++;
        if(j == n){
            printf("%d ",i - n);
            j = ne[j];
        }
    } 
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;、
  
int son[N][26],cnt[N],idx;//son[N][26]表示所有的结点，每一个结点有26个字母（不同的题目不一样），当需要创建结点的时候就直接从其中使用就是了，cnt[N]记录所有结点以当前结点为终点的字符串的数量是多少，idx记录当前使用到的下标
char str[N];

//向Trie树中存储字符串
void insert(char str[]){
    int p = 0;//p表示当前从存储到了哪个结点，最开始是从根节点开始，所以p=0
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;//如果该结点的这个地方没有链接字符，就使用新的结点，让其链接起来，并且将idx++
        p = son[p][u];//移动到下一个结点,注意，如果这是最后一重循环的话，下一个结点才是你当前存储的字符串的最后一个结点。
    }
    cnt[p] ++;//当前字符串存储完毕，该字符串存储的最后一个结点代表的字符串数量加一
}

//在Trie数中查找字符串
int query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;//如果当前结点没有链接到应该连接的下一个字符，就说明该数中储存的字符串集合没有所查找的字符串
        p = son[p][u];
    }
    
    return cnt[p];//如果按照链接的查找能够遍历完目标字符串的所有字符，那么就返回尾结点的字符串数量，如果为0的话说明该字符串集合中存在的其实是目标字符串的一个母串
}

int main()
{
    int n;
    cin >> n;
    char op[2];
    while(n --){
        cin >> op >> str;
        if (*op == 'I') insert(str);//插入
        else printf("%d\n", query(str));//搜索
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;

int n,m;
int p[N];//每个点的父结点

int find(int x){//实现祖宗结点的的查找和路径压缩优化
     if(p[x] != x) p[x] = find(p[x]); //如果这个点不是父节点那么就让它的父节点等于它的祖宗结点
     return p[x];
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) p[i] = i;//初始化所有点的父节点
    while(m --){
        char op[2];//如果使用字符变量而不是使用字符串的话，使用scanf读入的时候会读入些莫名其妙的空格或者回车
        int a,b;
        scanf("%s%d%d",&op,&a,&b);        
        if(op[0] == 'M') p[find(a)] = find(b);
        else{
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
const int N = 100010;

int n,m;
int p[N],cnt[N];

int find(int x){
     if(p[x] != x) p[x] = find(p[x]);
     return p[x];
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) p[i] = i, cnt[i] = 1;
    
    while(m --){
        char op[2];
        int a,b;
        cin >> op;
        
        if(op[0] == 'C'){
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            p[find(a)] = find(b);
            cnt[b] += cnt[a]; //连通块中点的数量的维护
        }
        else if(op[1] == '1'){
            cin >> a >> b;
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }else{
            cin >> a;
            cout << cnt[p[a]] << endl;
        }
    }    
    return 0;
}

//堆的初始化，首先可以使用一个一个插入的方法，但是这个初始化的方法的时间复杂度是O(logn),另一种方法是将所有的数据先读入数组中，然后对n/2前的所有数进行一次down的操作，就能实现时间复杂度为O(n)的堆初始化
for(int i = n / 2; i; i --) down(i);
//down()函数 注意：size的初始化一定要放在调用down函数之前
void down(int x){
    int t = x;
    if(x * 2 <= size && h[x * 2] > h[t]) t = x * 2;
    if(x * 2 + 1 <= size && h[x * 2 + 1] > h[t]) t = x * 2 + 1;
    if(t != x)
    {
        swap(h[t],h[x]);
        down(t);
    }
}
//up函数
void up(int x){
    while(x / 2 && h[x/2] > h[x]){
        swip(h[x/2],h[x]);
        x /= 2;
    }
}