lower_bound,BIT,next_permutation

lower_boundは、探索したいkey以上のイテレータを返す
upper_boundは、探索したいkeyより大きいイテレータを返す
binary_searchはkeyがあるかどうかをbool値で返す。

```
int main() {
	vector<int>a = { 1,4,4,7,7,8,8,11,13,19 };
	cout << binary_search(a.begin(), a.end(), 4) << endl;//True
	cout << binary_search(a.begin(), a.end(), 9) << endl;//False
	cout << binary_search(a.begin(), a.end(), 3) << endl;//False
	return 0;
}
```

```
int main() {
	vector<int>a = { 1,4,4,7,7,8,8,11,13,19 };
	auto iter1 = lower_bound(a.begin(),a.end(), 4);
	auto iter2 = lower_bound(a.begin(), a.end(), 6);
	auto iter3 = lower_bound(a.begin(), a.end(), 7);
	auto iter4 = lower_bound(a.begin(), a.end(), 19);
	auto iter5 = lower_bound(a.begin(), a.end(), 20);
	//値の表示
	cout << "_______value_________" << endl;
	cout << "iter1=" << *iter1 << endl;//iter1=4
	cout << "iter2=" << *iter2 << endl;//iter2=7
	cout << "iter3=" << *iter3 << endl;//iter3=7
	cout << "iter4=" << *iter4 << endl;//iter4=19
	cout << "iter5=" << *iter5 << endl;//iter5=1326115891

	//先頭からの距離
	cout << "_________from___________" << endl;
	cout << "iter1=" << iter1 - a.begin() << endl;//iter1=1
	cout << "iter2=" << iter2 - a.begin() << endl;//iter2=3
	cout << "iter3=" << iter3 - a.begin() << endl;//iter3=3
	cout << "iter4=" << iter4 - a.begin() << endl;//iter4=9
	cout << "iter5=" << iter5 - a.begin() << endl;//iter5=10

	//末尾までの距離
	cout << "__________to____________" << endl;
	cout << "iter1=" << a.end() - iter1<< endl;//iter1=9
	cout << "iter2=" << a.end() - iter2 << endl;//iter2=7
	cout << "iter3=" << a.end() - iter3 << endl;//iter3=7
	cout << "iter4=" << a.end() - iter4 << endl;//iter4=1
	cout << "iter5=" << a.end() - iter5 << endl;//iter5=0

	return 0;
}
```
lower_boundのイテレータから先頭のイテレータを引くと、あるkeyより小さい要素の個数を求めることができる。
末尾のイテレータからlower_boundのイテレータを引くと、あるkey以上の要素の個数を求めることができる。

```
#define ALL(a)  (a).begin(),(a).end()

int main() {

    //ソートする必要があるのじゃ…
    vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};

    //イテレータを返す
    auto Iter1 = upper_bound(ALL(a), 4);
    auto Iter2 = upper_bound(ALL(a), 6);
    auto Iter3 = upper_bound(ALL(a), 7);
    auto Iter4 = upper_bound(ALL(a), 19);
    auto Iter5 = upper_bound(ALL(a), 20);

    //値の表示
    cout << "----------value----------" << endl;
    cout << "Iter1 = " << *Iter1 << endl; //Iter1 = 7
    cout << "Iter2 = " << *Iter2 << endl; //Iter2 = 7
    cout << "Iter3 = " << *Iter3 << endl; //Iter3 = 8
    cout << "Iter4 = " << *Iter4 << endl; //Iter4 = 1326115891
    cout << "Iter5 = " << *Iter5 << endl; //Iter5 = 1326115891

    //先頭からの距離
    cout << "----------from----------" << endl;
    cout << "Iter1 = " << Iter1 - a.begin() << endl; //Iter1 = 3
    cout << "Iter2 = " << Iter2 - a.begin() << endl; //Iter2 = 3
    cout << "Iter3 = " << Iter3 - a.begin() << endl; //Iter3 = 5
    cout << "Iter4 = " << Iter4 - a.begin() << endl; //Iter4 = 10
    cout << "Iter5 = " << Iter5 - a.begin() << endl; //Iter5 = 10

    //末尾までの距離
    cout << "----------to----------" << endl;
    cout << "Iter1 = " << a.end() - Iter1 << endl; //Iter1 = 7
    cout << "Iter2 = " << a.end() - Iter2 << endl; //Iter2 = 7
    cout << "Iter3 = " << a.end() - Iter3 << endl; //Iter3 = 5
    cout << "Iter4 = " << a.end() - Iter4 << endl; //Iter4 = 0
    cout << "Iter5 = " << a.end() - Iter5 << endl; //Iter5 = 0

    return 0;
}
```
二分探索

```
int BinarySearch(vector<int>vec, int key) {
	int left = 0, right = vec.size(), mid;
	while (left < right) {
		mid = (left + right) / 2;
		if (vec[mid] == key) {
			return mid;
		}
		else if (key < vec[mid]) {
			right = mid;
		}
		else if (vec[mid] < key) {
			left = mid + 1;
		}
	}
	return -1;
}
```

lower_boundを使った二分探索

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

int main() {
    vector<int> vec = {1, 1, 2, 2, 4, 5, 5, 6, 8, 8, 8, 10, 15};
    int key = 5;
    auto iter = lower_bound(vec.begin(), vec.end(), key);

    // 5 を検索
    if (iter != vec.end() && *iter == key) {
        cout << key << " is found at " << distance(vec.begin(), iter) << "\n";
    } else {
        cout << key << "is NOT found." << "\n";
    }

    return 0;
}
```

例題abc 061-C

```
int main() {
	int N;
	ll K;
	ll A[100010] = {}; 
	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		A[a] += b;
	}
	for (int i = 1; i < 100010; ++i) {
		if (K <= A[i]) {
			cout << i << endl;
			break;
		}
		K -= A[i];
	}
	return 0;
}
```
普通にやるとこんな感じ

```
// ABC061_C
#include <iostream>
#include <vector>
#include <algorithm>  // std::copy()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
using namespace std;
typedef long long ll;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり

int main() {
    // input
    ll N, K, a, b;
    cin >> N >> K;
    vector<ll> num(100000+1, 0);
    REP(i, N) {
        cin >> a >> b;
        num[a] += b;
    }

    // 各数が何個あるかの累積和を計算
    vector<ll> partial;
    COPY(num, partial);  // copy vec to partial
    partial_sum(num.begin(), num.end(), partial.begin());

    // K 個以上となる最小のインデックスを求める
    auto iter = lower_bound(partial.begin(), partial.end(), K);
    cout << IDX(partial, iter) << "\n";

    return 0;
}
```

abc077-c
snuke festival
https://abc077.contest.atcoder.jp/tasks/arc084_a

```
int main() {
	int N;
	cin >> N;
	vector<int>A(N), B(N), C(N);
	for (int i = 0; i < N; ++i)cin >> A[i];
	for (int i = 0; i < N; ++i)cin >> B[i];
	for (int i = 0; i < N; ++i)cin >> C[i];
	sort(A.begin(), A.end());
	sort(C.begin(), C.end());
	ll count = 0;
	for (int i = 0; i < N; ++i) {
		count += ((lower_bound(A.begin(), A.end(), B[i])-A.begin())*(C.end()-upper_bound(C.begin(), C.end(), B[i])));
	}
	cout << count << endl;
	return 0;
}
```
BIT(binary indexed tree)とは
整数列 a1,a2,...,an に対して, 以下のクエリを O(log(n)) で実現するデータ構造.

sum(i): a1+a2+...+ai を求める
add(i,x): ai に x を加える

```
class BIT
{
public:
	vector<int>bit;
	int M;

	BIT(int M) :
		bit(vector<int>(M + 1, 0)), M(M) {};
	int sum(int i) {
		if (!i)return 0;
		return bit[i] + sum(i - (i&-i));
	}

	void add(int i, int x) {
		if (i > M)return;
		bit[i] += x;
		add(i + (i&-i), x);
	}
};
```
ABC119-D

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
// vector v において、x の前方と後方の index を求める
template<class T> int former(const vector<T> &v, T x) {
	return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}//前方のindex(自分自身を含んでよい場合)
template<class T> int latter(const vector<T> &v, T x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin();
}//後方のindex(自分自身を含んで良い場合)

int main() {
	int A, B, Q;
	cin >> A >> B >> Q;
	vector<ll>s(A);
	vector<ll>t(B);
	for (int i = 0; i < A; ++i)cin >> s[i];
	for (int i = 0; i < B; ++i)cin >> t[i];
	s.push_back(1e15); s.push_back(-1e15);
	t.push_back(1e15); t.push_back(-1e15);
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	for (int i = 0; i < Q; ++i) {
		ll x;
		cin >> x;
		ll res = 1e17;
		for (int j = 0; j < 2; ++j) {
			//最初にs
			ll first = (j ? s[(lower_bound(s.begin(), s.end(), x) - s.begin())]:s[lower_bound(s.begin(),s.end(),x)-s.begin()-1]);
			for (int k = 0; k < 2; ++k) {
				ll second = (k ? t[lower_bound(t.begin(), t.end(), x) - t.begin()] : t[lower_bound(t.begin(), t.end(), x) - t.begin() - 1]);
				chmin(res, abs(x - first) + abs(first - second));
			}
		}
		for (int j = 0; j < 2; ++j) {
			//最初にt
			ll first = (j ? t[(lower_bound(t.begin(), t.end(), x) - t.begin())] : t[lower_bound(t.begin(), t.end(), x) - t.begin() - 1]);
			for (int k = 0; k < 2; ++k) {
				ll second = (k ? s[lower_bound(s.begin(), s.end(), x) - s.begin()] : s[lower_bound(s.begin(), s.end(), x) - s.begin() - 1]);
				chmin(res, abs(x - first) + abs(first - second));
			}
		}
		cout << res << endl;
	}

	return 0;
}
```
next_permutation

abc 054 c

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int N, M;
int G[10][10];
bool visited[10];
int ans = 0;

int main() {
	cin >> N >> M;
	memset(G, 0, sizeof(G));
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		a--, b--;
		G[a][b] = 1;
		G[b][a] = 1;
	}
	vector<int>v;
	int res = 0;
	for (int i = 1; i < N; ++i)v.push_back(i);
	sort(v.begin(), v.end());
	do {
		int now = 0;
		for (int i = 0; i < v.size(); ++i) {
			if (G[now][v[i]] == 0)break;
			now = v[i];
			if (i == v.size() - 1)res++;
		}
	} while (next_permutation(v.begin(), v.end()));
	cout << res << endl;
	return 0;

}
```