STL

vector

模板（基本操作）

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    //顺序访问
    vector<int>obj;
    for(int i=0;i<10;i++)
    {
        obj.push_back(i);   
    } 

    cout<<"直接利用数组："; 
    for(int i=0;i<10;i++)//方法一 
    {
        cout<<obj[i]<<" ";
    }

    cout<<endl; 
    cout<<"利用迭代器：" ;
    //方法二，使用迭代器将容器中数据输出 
    vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素 
    for(it=obj.begin();it!=obj.end();it++)
    {
        cout<<*it<<" ";
    }
    return 0;
}

vector + lower_bound(upper_bound)

//查询
    int pl=(lower_bound(v[c].begin(),v[c].end(),l)-v[c].begin());
//修改
    //1.lower_bound返回地址，所以直接取值
    (*lower_bound(a.begin(),a.end(),x))++;

    //2.将位置取出来，再做更改，更直观
    int pl=lower_bound(a.begin(),a.end(),x)-a.begin();
    a[pl]++;

P3939

直接用vector< int> v[N]保存值域中每个数出现的位置，查询和修改都用二分查找即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+10;
vector<int> v[N];
int n,m,l,r,c,x,op;
int a[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=m;++i){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&l,&r,&c);
            int pl=(lower_bound(v[c].begin(),v[c].end(),l)-v[c].begin());
            int pr=(upper_bound(v[c].begin(),v[c].end(),r)-v[c].begin()-1);
            printf("%d\n",pr-pl+1);
        }else{
            scanf("%d",&x);
            int tx=a[x];
            int ty=a[x+1];
            if(tx!=ty){
                int pl=lower_bound(v[tx].begin(),v[tx].end(),x)-v[tx].begin();
                int pr=lower_bound(v[ty].begin(),v[ty].end(),x+1)-v[ty].begin();
                v[tx][pl]++;
                v[ty][pr]--;
                //(*lower_bound(v[tx].begin(),v[tx].end(),x))++;
                //(*lower_bound(v[ty].begin(),v[ty].end(),x+1))--;
                swap(a[x],a[x+1]);
            }
        }
    }
    return 0;
}

STL迭代器

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了* ，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator.