/* 二叉搜索树 */struct Node//树结点
{int w;Node *l,*r;//左右儿子指针
};
typedef Node* tree;//define成指针类型方便操作void insert(tree &root,int x)//建树
{if(!root)//找到空结点，赋值{root=new(Node);root->w=x;root->l=root->r=NULL;}else if(x<root->w)//插入值比当前根结点小，往左子树搜insert(root->l,x);else if(x>root->w)//插入值比当前根结点大，往右子树搜insert(root->r,x);
}vector<int> depth[N];//存储层序遍历结果
void level(tree root,int d)//层序遍历 ,d 表示当前是第几层
{if(root)//结点不空才有操作{depth[d]=root->w;level(root->l,d+1);//先搜左子树level(root->r,d+1);//再搜右子树}
}void dfs(tree root)
{
// cout<< root->w <<' ';//先序输出if(root->l)//子树不空才能搜dfs(root->l);
// cout<< root>w <<' ';//中序输出if(root->r)dfs(root->r);
// cout<< root->w <<' ';//后序输出
}int mian()
{int n;cin>>n;tree root=NULL;//初始化一定要置空for(int i=0,x;i<n;i++){cin>>x;insert(root,x);}return 0;
}
/* 模拟堆（小顶堆 ） PS:大顶堆只需要将下面所有'<'换成'>'*/int h[N],cnt;//堆数组，堆中当前元素个数void up(int u)//插入堆时使用
{while(u/2&&h[u]<h[u/2])//父节点存在，并且父节点的值比当前结点大则进行交换{swap(h[u],h[u/2]);u/=2;}
}int mian()
{int n;cin>>n;for(int i=1,x;i<=n;i++){cin>>h[++cnt];up(i);}
}
/*常用技巧*/for(auto it:array)//foreach语句，遍历array容器中的所有元素
{}stoi(s) //将字符串s转换成整型sort(a,a+n,greater<int>())//按递减顺序排序isdigit(x) //判断x是不是数字，返回bool
isalpha(x) //判断x是不是字母s.substr(idx) //将字符串 s 中从下标idx开始的所有字符截取并返回
s.substr(idx,length) //将字符串 s 中从下标idx开始的连续length个字符截取并返回
s.find(x) //在s字符串中查找字符串x，存在返回第一个x所在位置的下标，不存在返回-1/*常用STL*/
map
stack//栈
queue//队列
set//去重排序数组
vector//变长数组
priority_queue//优先队列（大顶堆）
deque//双端队列
