今天应该是8月以来最简单的一次，我也是捡了个漏

言归正传：

今天主要讲了各类STL容器的使用方法，这里简单普及一下几种常见的STL容器的内置函数，以及都能解决什么问题：

1 unordered_set/set/multiset:{

性质：无序集合，键值对可重复，能自动去重和排序，主要用于数据过大，需要二分答案或需要递增数据结构的题

内置函数:1 删除：set.erase()//可以划定删除范围，通常为两个数

2 添加： set.insert()

3 双向迭代：set.begin(), set,rbegin()

4 清空：set.clear()

5 查找：set.count()//查找数量，set.find()//查找位置

6 二分类型操作：set.lower_bound(),set.upper_bound()

}

2 map:{
性质：有序无重复键值对专用容器，可以代替哈希

内置函数 :1 初始化：map<pair<>>//一般为两种不同类型，在字符串哈希中一般用来存储字符和下标：map<string,int>

2 count():返回个数

3 find():若存在则返回下标，没有返回end()

4 二分操作：map.lower_bound(),map.upper_bound()

其余基本和set差不多，所有含map类型的容器都支持上述操作

}

3 vector(比较熟悉，直接上代码){
q.push_back(数据) 把元素添加到末尾

q.pop_back() 把末尾元素删除

q.size() 或 q.length() 获取长度

q[i] 获取下标为 i 的元素

q.front()获取首位元素，也可以使用下标 q[0]

q.back() 获取末尾元素，也可以使用下标 q[q.size()-1]

q.clear() 清空容器

q.begin() 返回一个迭代器，指向容器的第一个元素

q.end() 返回一个迭代器，指向容器的最后一个元素的后一位

q.erase(q.begin()+1, q.begin()+4) 删除容器中下标 到下标 的元素，删除其他范围同理。

}

其余容器都是建立在这三种容器之上，底层实现：红黑树

今日例题：

1 Air Conditioners{

1. 题意：有k个空调分别分布在数组的k个位置上，并且每个空调都有其对应的温度。现在我们定义数组ai的温度为min(tj+|aj-i|),求最终每个格子的温度值

2. 思路：一开始看到这个公式我就没有想到用dp,直到意识tj和aj的下标必须相同。所以这题我们初始化一个无限大的dp数组（注意，此题的无限大必须超过1e9，不然会WA），然后再遍历两遍数组寻找温度加下标差的最小值，步骤如下：

1 先将 dp[原来有空调的下标] 和 空调的温度之间 取min,好之后计算每个下标的最小值

2 第一遍正序扫描数组，取min(dp[i],dp[i-1]+1):上一个最小值加1，不难发现题目中的样例基本连续。”第二遍倒序扫描取min(dp[i],dp[i+1]+1)

3. 算法：线性dp

}

核心代码：

for(int i=1;i<=k;i++){
        dp[bia[i]]=min(dp[bia[i]],tem[i]);//初始化，每个有空调的dp下标
      }
      for(int i=2;i<=n;i++){
        dp[i]=min(dp[i],dp[i-1]+1);//每个空调的温度只受左边温度的影响
      }
      for(int i=n-1;i>=1;i--){
        dp[i]=min(dp[i],dp[i+1]+1);//受右边影响
      }

2 In love{

1. 题意：有一组线段，输入格式为一个字符外加线段的左端点和右端点，+表示调价，-表示删去，请你判断对于每一次删除和添加，是否存在一对线段满足不相交。有则输出YES,无则输出No

2. 思路：这题是一道裸的mutiset容器的练手题。这里我们需要知道这个容器的一些用法：

             1 删除某个值：set.erase(set.find(s));

             2 添加：set.insert(s);

             3 左右端点查找(针对于此题的关键用法):set.begin(),set.rbegin();

         了解了这些用法以后，我们就可以AC。因为在这个多重集中如果存在一个最大左端点使得其大于最大右端点，那么这个多重集中一定存在不相交的一对线段

3. 算法：动态数据结构

}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    multiset<int> l,r;//主要是set容器的应用
    while(t--){
        char c;
        int x,y;
        cin>>c>>x>>y;
        if(c=='+'){
            l.insert(x);//添加线段
            r.insert(y);
        }
        else{
            l.erase(l.find(x));//删除线段
            r.erase(r.find(y));
        }
        if(!l.empty()&&*l.rbegin()>*r.begin()){//迭代，如果线段最左端大于线段最右端，输出YES
            cout<<"YES"<<endl;
        }
        else cout<<"NO"<<endl;
    }
}

3 Data structures fan{

1. 题意：给定一个01串和一个数组，其长度相等，其中还有两种不同的询问方式：1 l r：将01串中的第l个数到第r个数取反。2 c={0,1}:将01串中为c的下标全部找出并对应到数组中取异或值。对于每次第二种询问，你需要输出其对应的异或值

2. 思路：又是区间异或，这种题目显然又是要借助异或的性质做题。首先看到数据范围我们就意识到不能纯模拟取反去做。这里又提到异或的性质：自反性和分配性。假设某一段中为0的区间异或值为7,为1的区间异或值为3,总的异或值为8,那么7^8,3^8,代回到01串中，我们发现这其实就已经实现了自反，也就意味着一个数异的异或值就是取反值，最终变成了模拟答案即可

}

先是两种异或值的初始化：

 for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]^num[i];
            if(s[i]=='0') xor0^=num[i];//0的初始
            else xor1^=num[i];//1的初始
        }

再是取反：

              int l,r;
              cin>>l>>r;
              long long val=pre[r]^pre[l-1];
              xor1^=val;
              xor0^=val;

4 Divide and summarize{

1. 题意：有一个数组，你可以计算出整个初始数组中的最大值与最小值的和除以2并向下取整的值，而整个数组又被分割成了两段，一段是大于这个值的数组，一段是小于这个值的数组，请你判断在经过若干次分割后的某一个数组和是否可能等于s,能则输出YES,没有输出NO

2. 思路：这题的过程模拟起来大概就是1变2,2变4,4变8,8变16,。因此这题如果用递归去做的话时间复杂度为O(nlogn),可以接受。而在这之前我们需要明确两件事：

1 这个数组中的下标是否重要？能否进行排序

2 排序的目的是什么？

先说答案：一点不重要，而且要排序

因为我们并不关心这个数组中的每一项的值，而是要求每一段可能分割出来的数组和，排序一是为了能快速求出mid，也就是分割点的值，二是为了二分。二分是为了能快速的分割数组，找出第一个小于这个分割点的值，并且记录这个下标，好进行下一步的递归

3. 算法：递归，二分，排序

}

核心代码：

void solve(int l,int r){
    ll sum=pre[r]-pre[l-1];
    us.insert(sum);//加入出现过的区间和
    if(a[l]==a[r]) return;
    ll mid=(a[l]+a[r])/2;//计算分割点
    int pos=upper_bound(a+1,a+n+1,mid)-a-1;//二分查找第一个大于mid的位置
    solve(l,pos);//递归
    solve(pos+1,r);
}

5 Vessels(一题多解){
1.题意：有一组容器，并且给了你各个容器的大小，此外还有q次询问：1 l w:在容器l内倒入w升水

                2 c:输出第c个容器内水的容量

             对于每个询问2，你需要输出对应的值

3. 思路：这题有两种解法，可以用难想一点的并查集，也可以用集合（更推荐），这里分享一下集合的思路（因为有大佬用的并查集）：

首先定义一个set，用来维护还未装满水的容器，要按下标顺序进行排序，之后好二分查找下一个未装满水的容器的位置。之后对于每一个询问1，如果这个容器是满的或者倒了以后会变满，那么二分查找下一个未满容器的位置，不断的用容器内的剩余容量减去倒的水，直到为0或到最后一个容器为止

4. 算法：动态数据结构，并查集

}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N];
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
void uni(int a,int b){
    int ra=find(a),rb=find(b);
    if(ra!=rb) fa[ra]=rb;
}
int main(){
    int n,q; cin >> n;
    vector<long long> water(n+1),cap(n+1);
    for(int i=1;i<=n;i++){
        cin>>water[i];
        fa[i]=i;//初始化父节点数组
    } 
    cin >> q;
    fa[n+1]=n+1;
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int id,wa;
            cin >> id >> wa;
         int pos=find(id);
         while(wa>0&&pos<=n){
            int re=water[pos]-cap[pos];//算差值
            if(wa<=re){//如果能装下
                cap[pos]+=wa;//加入
                wa=0;
            }
            else{
                wa-=re;//溢出的话，减去当前剩余容量
                cap[pos]=water[pos];
                uni(pos,pos+1);//合并
                pos=find(pos);//找到没满的容器
            }
         }
        }
         else if(t==2){
         int y;
         cin>>y;
         cout<<cap[y]<<endl;
         }
    }
}

6 Array Restoration{

1. 题意：有一个长度为q的数组，其中有一些数是未知的，在数组中对应值为0。现在你有q次操作，可以选择任意区间[l,r]使得区间内的值都为i，求一个初始数组使得经过q次操作后等于现在给出的数组

2. 思路：首先因为是按顺序1到q来，因此q是必须出现的，如果两个相同数之间存在更小的数，则这个序列一定不合法，同样，如果不存在q，则这个序列也不合法。接下来就是怎么填数的问题：

1 如果没有q,优先填q

2 如果一个数x分别在左右两端存在，则填max({x});

3 如果实在没找到一个出现过的数，统一用1代替

维护max({X})其实也很简单，这里我一开始用的是集合来维护，当所有x第一次出现时，填充进集合，最后出现时删除即可

}

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int num[N];
int l[N],r[N];
set<int> st;//这里一开始决定用集合维护
int main(){
    int n,m;
    cin >> n >> m;
    int mx=0,mn=1e9;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        mx=max(mx,num[i]); mn=min(mn,num[i]);
    }
    for(int i=n;i>=1;i--){
        if(!r[num[i]]) r[num[i]]=i;//右区间的填充
    }
    for(int i=1;i<=n;i++){
        if(!l[num[i]]) l[num[i]]=i;//左区间的填充
    }
    for(int i=1;i<=n;i++){
        if(num[i]==0){
            if(mx<m) num[i]=m,mx=m;//如果没有出现m，优先选择m
            else if(st.size()) num[i]=*--st.end();//两边出现过
            else num[i]=1;//实在没出现过用1代替
        }
        else{
            if(l[num[i]]==i&&l[num[i]]<r[num[i]]) st.insert(num[i]);//第一次出现时插入
            if(r[num[i]]==i&&l[num[i]]<r[num[i]]) st.erase(num[i]);//最后一次出现时弹出
            if(st.size()){
                if(num[i]<(*--st.end())){//如果相同数之间出现了更小值
                    cout<<"NO";
                    return 0;
                }
            }
        }
    }
        if(mx<m) cout<<"NO";//最终仍没出现m
        else cout<<"YES"<<endl;
        for(int i=1;i<=n;i++) cout<<num[i]<<" ";
    }