STL
#include<bits/stdc++.h>
using namespace std;
signed main() {
// pair pair pair pair pair pair pair pair pair pair pair
// 构造
// pair<int,int> a(3,5); //构建一个(3,5)数对
// cout << a.first << " " << a.second << endl;
// a = make_pair(4,6); //构建一个(4,6)数对
// cout << a.first << " " << a.second << endl;
// a.second = 7;
// cout << a.first << " " << a.second << endl;
//pair 等价 构造结构体方法
// pair<int , string> stu[4];
// for(int i=1;i<=3;i++){
// stu[i].first = i;
// stu[i].second = "'askjhfdas'";
// }
// for(auto s:stu) {
// cout << s.first << endl;
// cout << s.second << endl;
// }
//三元组:
// pair<int , pair<int , int>> b(1,pair<int,int>(2,3));
// cout << b.first << b.second.first << b.second.second << endl;
//pair -> cmp
//a < b ? a.first < b.first || (a.first == b.first && a.second < b.second)
//array array array array array array array array array
//构造
// array<int , 5> a; //构建一个int类型定长数组 == a[5]
// a[1] = 2;
// for(int i=0;i<5;i++) cout << a[i] << endl;
//定义全局返回0 2 0 0 0 非全局返回 -1746135328 2 0 2 1933250560
//stack stack stack stack stack stack stack stack stack stack
// stack <int> s;
//主要方法:top,pop,push,size,empty
//s.top();//访问栈顶元素
//cout << s.top() << endl;
//s.pop();//弹出栈顶元素
//s.push();//从栈顶插入元素
//s.empty() //空返回True else false
//从上往下打印整个栈
// while(!s.empty()) {
// cout << s.top() << endl;
// s.pop();
// }
// s.push(1);
// s.push(2);
// cout << s.size() << endl; //返回栈的个数
//queue queue queue queue queue queue queue queue queue queue
//队列
//queue<int> q;
//主要方法: push,pop,front,back
// q.push(1);
// q.push(3);
// q.push(2);//从队尾插入
// cout << q.front() << " " << q.back() << endl;
// q.pop();//从队头弹出
// cout << q.front() << " " << q.back() << endl;
//queue dfs模板
// queue<int> q;
// q.push(s);
// while(!q.empty()) {
// int x = q.front();
// q.pop();
// for(auto y : adj[x]) {
// q.push(y);
// }
// }
//priority_queue priority_queue priority_queue priority_queue priority_queue
//默认为大根堆
//priority_queue<int> v;
// v.push(3);v.push(1);v.push(2);
// while(!v.empty()) {
// cout << v.top() << endl;
// v.pop();
// }
//如何改为小根堆? 1手动取反
//priority_queue<int> v;
// v.push(-3);v.push(-1);v.push(-2);
// while(!v.empty()) {
// int x = v.top();
// cout << -x << endl;
// v.pop();
// }
//如何改为小根堆? 2特殊写法
// priority_queue<int,vector<int>,greater<int> > v;
// v.push(3);v.push(1);v.push(2);
// while(!v.empty()) {
// cout << v.top() << endl;
// v.pop();
// }
//deque deque deque deque deque deque deque deque 双端队列
//deque<int> d;
// d.push_front();//头插 O(1)
// d.pop_front();//头删
// d.push_back();//尾插 O(1)
// d.pop_back();//尾删
// d.front()//访问头部
// d.back()//访问尾部
// d.size()//访问队列总个数
// d.empty()
// cout << d[1] << endl;支持按照下标访问 ,栈和队列不支持
//vector() vector() vector() vector() vector() vector() vector()
//vector<int> v;
//vector<int> v{1,2,3};
//vector<int> v(3,100); //初始化三个100 100,100,100
//vector<int> v{3,100}; //一开始就放3,100两个元素
//for(int x:v)cout << x << endl;
//v.resize(100)//扩大容器空间到100
//访问容器大小:v.size();
//for(int i=0;i<v.size() - 1;i++) cout << i << endl;
//v.size是null类型 会打印0->正无穷
//for(int i=0;i<(int)v.size() - 1;i++) cout << i << endl;
//强制转换之后就不会了
//v.clear();//清空容器内所有数据,但不释放内存,容器空间依旧还在
// v.push_back();//末尾插入元素
//v.pop_back(); //末尾删除元素
//迭代器:
//v.begin();v.end();
// vector<int>::iterator it = v.begin();
// cout << *it << endl;
// it++;
// cout << *it << endl;
//遍历整个:
//for(vector<int>::iterator it = v.begin();it!=v.end();it++)
// cout << *it << endl;
// for(auto it = v.begin();it!=v.end();it++) {
// *it = *it + 1;
// cout << *it << endl;
// }
// v.insert(v.begin()+1,4);
// for(vector<int>::iterator it = v.begin();it!=v.end();it++)
// cout << *it << endl;
//在第二个位置之前插入4
//v.erase(v.begin()+2);删除第三个位置
//&&&引用
// for(int x : v) {
// x += 1;
// }
// for(auto x:v) cout << x << endl;//1,2,3
// for(int &x : v) {
// x += 1;
// }
// for(auto x:v) cout << x << endl;//2,3,4
//sort(v.begin(),v.end());//排序递增
// auto it1 = lower_bound(v.begin(),v.end(),2);//返回大于等于2的第一个位置;
// cout << *it1 << endl;//2
// auto it2 = upper_bound(v.begin(),v.end(),2);//返回大于2的第一个位置;
// cout << *it2 << endl;//3
//it2 - it1可以看大于等于和大于之间有几个元素
//set set set set set set set set set set set set set set
//1
// set<int> s;
// vector<int> v{3,2,8,4,2};
// for(auto x:v) {
// s.insert(x);
// for(auto t:s)
// cout << t << " ";
// cout << endl;
// }
// 3
// 2 3
// 2 3 8
// 2 3 4 8
// 2 3 4 8 说明: set里同样的数据只存储一次,且按照顺序存入
//2
// vector<int> v{3,2,8,4,2};
// set<int> s(v.begin(),v.end());
// for(auto x:s)cout<< x << endl; //2 3 4 8
//3
//s.erase(x);//删除某个存在的x 也可以删除迭代器(某个位置)
//vector迭代器可以多个相加:v.begin() + 5
//set迭代器只能一个一个加或减 it++ t--
//4
//s.count(x);//查询x是否存在 存在返回1 else 返回0
// set<int> s{1,2,3,4};
// for(auto x:s)cout << x << endl;
// if(s.count(5))cout << 1 << endl;
// else cout << 0 << endl; //0
// if(s.count(4))cout << 1 << endl;
// else cout << 0 << endl; //1
//5
//s.lower_bound()大于等于的第一个位置 upper_bound()大于的第一个位置
// set<int> s{1,2,3,4,5};
// auto it = s.upper_bound(2);
// // cout << *it << endl;//3
// // auto it2 = prev(it);
// // cout << *it2 << endl;//2
// // auto it3 = it - 1;
// // cout << *it3 << endl;//报错
// it--;
// auto it4 = it;
// cout << *it4 << endl; //2
//set作为堆来使用
// s.insert(x);
// *prev(s.end());//返回最大值
// s.erase(prev(s.end()));//删除最大值
//map map map map map map map map map map map map map map map map
//1
// map<int,int> m;
// m[1] = 3;
// m[9] = 4;
// m[3] = 0;
//for(auto x:m) cout << x.first << " " << x.second << endl;
// 1 3
// 3 0
// 9 4
//如果赋值: 赋值一个不存在的会重新新建
//m[2] = 3;
//for(auto x:m) cout << x.first << " " << x.second << endl;
//2.1
// if(m[2] != 0)cout << m[2] << endl;
// for(auto x:m) cout << x.first << " " << x.second << endl;
// // 1 3
// // 2 0
// // 3 0
// // 9 4
//2.2
// if(m.count(2) != 0)cout <<" YES" << endl;
// else cout << "NO" << endl;
// for(auto x:m) cout << x.first << " " << x.second << endl;
// // NO
// // 1 3
// // 3 0
// // 9 4
//3
// m.erase(1);
// for(auto x:m) cout << x.first << " " << x.second << endl;
// //3 0
// //9 4
//4
// map<int,int> m;
// m[1] = 1;
// m[2] = 2;
// auto it = m.begin();
// // cout << it -> first << " " << it -> second;//1 1
// for(auto [key,val] : m) cout << key<< " " << val << endl;
// //1 1
// //2 2
//multiset multiset multiset multiset multiset multiset
//1
// multiset<int> s;
// s.insert(1);
// s.insert(2);
// s.insert(2);
// s.insert(3);
// for(auto x:s) cout << x << endl; //1 2 2 3不会去重
//2
// multiset<int> s;
// s.insert(1);
// s.insert(2);
// s.insert(2);
// s.insert(3);
// // s.erase(2);
// // for(auto x:s)cout << x << endl; //1 , 3;
// s.erase(s.find(2)); //找到第一个2的迭代器
// for(auto x:s)cout << x << endl; //1 , 2, 3;
//3
//s.count(x);//时间复杂度与查询的个数有关
//unordered_map unordered_set (乱序)
//内部实现为hash表的set和map 接近O(1)
//不支持lower_bound查询
//会被卡而且常数不是特别好,慎用
//string string string string string string string string string string
// string s = "123";
// int a = stoi(s); //string转int
// cout << a+10 << endl;//133
// string s = "123";
// int a = stoll(s); //string转long long
// cout << a+10 << endl;//133
// int a = 123;
// string s = to_string(a); //int -> string
// cout << s << endl;
// long long a = 123;
// string s = to_string(a); //long long -> string
// cout << s << endl;
// string s = "123";
// s+="123";
// cout << s; //123123
// string s = "123";
// s.push_back('1');
// cout << s << endl;//1231
// string s = "123";
// //s.c_str(); string -> char
// //puts(s.c_str());
// string s = "11111116789";
// s.replace(3,4,"2"); //11126789 从下标第3的位置连续四个 替换成“2”
// cout << s << endl;
//s.find('x',y);//从下标为y的位置找第一个x出现的位置
// string s = "123456";
// string t = s.substr(1,5);//从下标为1的位置开始 连续5个
// cout << t << endl; //23456
//algorithm algorithm algorithm algorithm algorithm algorithm algorithm
//unique(a.begin(),a.end());//去重
// 输入数组 a[]={1,2,3,4,4,5,6,6,6,7,8,6,7,8}。
// 输出数组 a[]={1,2,3,4,5,6,7,8,6,7,8}。
//reverse(a.begin(),a.end());//翻转
//123456 -> 654321
//vector <int> a{1,2,3,4,5};//旋转
// rotate(a.begin(),a.begin()+2,a.begin()+4);
// for(auto x:a)cout << x << endl; //3 4 1 2 5
// rotate(a.begin(),a.begin()+2,a.end());
// for(auto x:a)cout << x << endl; //3 4 5 1 2
//rotate(x,y,z);//把y->z的数据放到位置x之前
// vector <int> v{1,2,3,4,5};
// auto it = min_element(v.begin(),v.end()); //返回最小位置迭代器
// cout<< *it << " " << it - v.begin() << endl;//1 0
// auto it1 = max_element(v.begin(),v.end()); //返回大位置迭代器
// cout<< *it1 << " " << it1 - v.begin() << endl;//5 4
//lower_bound(),upper_bound()最好就用于vector;
//next_permutation()返回下一个排列
// int a[10];
// int n = 5;
// for(int i=0;i<5;i++) a[i] = i + 1;
// while(true) {
// for(int i=0;i<n;i++)cout << a[i] << " ";
// cout << endl;
// if(!next_permutation(a,a+n)) break;
// }
}