尺取り

https://qiita.com/drken/items/ecd1a472d3a0e7db8dce
と同じ内容

尺取り法は以下の形式の問題を解くときに使える可能性のあるテクニック
長さnの数列a1,a2,,,anにおいて
条件を満たす区間のうち最小の長さを求めよ
条件を満たす区間のうち最大の長さを求めよ
条件を満たす区間を数え上げよ

例１．
長さnの正の整数列a1,a2,,,anと整数xが与えられる。整数列の連続する部分列でその総和がx以下となるものを数え上げよ(実際の出題はQ個のクエリがあって各クエリごとにxが与えられる)

区間の左端leftを固定し、right=left,left+1,left+2,,,と調べていって条件を満たさなくなる場所を検出することで実現する

```
int main() {
	int n, Q;
	cin >> n >> Q;
	vector<ll>a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int j = 0; j < Q; ++j) {
		ll x;
		cin >> x;
		ll res = 0;
		for (int left = 0; left < n; ++left) {
			ll sum = 0;
			int right = left;
			while (right < n&&sum + a[right] <= x) {
				sum += a[right];
				++right;
			}
			res += (right - left);
		}
		cout << res << endl;
	}
	return 0;
}
```
しかしこれでは各leftに対してO(n)かかるので全体でO(n^2)かかってしまう。

ここで、f(left)は広義単調増加関数であることを利用して高速化する。具体的にはf(left)まで求まっている時に次のf(left+1)を求めるときはright=f(left)から出発して条件を満たさなくなるまでインクリメントしていく

```
int main() {
	int n,Q;
	cin >>n>> Q;
	vector<ll>a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int j = 0; j < Q; ++j) {
		ll x; cin >> x;
		ll res = 0;
		//区間の左端leftで場合分け//
		int right = 0;//毎回rightを使いまわす//
		ll sum = 0;//sumも使いまわす
		for (int left = 0; left < n; ++left) {
			while (right < n&&sum + a[right] <= x) {
				sum += a[right];
				++right;
			}
			//breakした状態でrightは条件を満たす最大
			res += (right - left);

			if (right == left)++right;//rightがleftに重なったらrightも動かす
			else sum -= a[left];//leftのみがインクリメントされるのでsumからa[left]を引く
		}
		cout << res << endl;
	}

	return 0;
}
```

```
int right = 0;     
for (int left = 0; left < n; ++left) {
    while (right < n && (right を 1 個進めたときに条件を満たす)) {
        /* 実際に right を 1 進める */
        // ex: sum += a[right];
        ++right;
    }

    /* break した状態で right は条件を満たす最大なので、何かする */
    // ex: res += (right - left);

    /* left をインクリメントする準備 */
    // ex: if (right == left) ++right;
    // ex: else sum -= a[left];
}
```
この形式は汎用性が高いっぽい

例
長さnの正の整数列a1,a2,,,,anと整数xが与えられる。整数列の連続する部分列でその総和がx以上となるもののうち最小の長さを求めよ（実際の出題はQ個のクエリがあって各クエリごとにxが与えられ条件を満たす区間がないときは０を出力)

```
int main() {
	int Q;
	cin >> Q;
	for (int query = 0; query < Q; ++query) {
		int n; cin >> n;
		ll x; cin >> x;
		vector<ll>a(n);
		for (int i = 0; i < n; ++i)cin >> a[i];
		int res = n + 1;
		int right = 0;
		ll sum = 0;
		for (int left = 0; left < n; ++left) {
			while (right < n&&sum < x) {
				sum += a[right];
				++right;
			}
			if (sum < x)break;//これ以上leftを進めてもダメ
			res = min(res, right - left);
			//leftをインクリメントする準備//
			if (right == left)++right;
			else sum -= a[left];
		}
		if (res < n + 1)cout << res << endl;
		else cout << 0 << endl;
	}
	
	return 0;
}
```
abc 038 c 単調増加

```
int main() {
	int n;
	cin >> n;
	vector<ll>a(n);
	for (int i = 0; i < n; ++i)cin >> a[i];
	ll res = 0;
	int right = 1;
	for (int left = 0; left < n; ++left) {
		while (right < n && (right <= left || a[right - 1] < a[right])) {
			++right;
		}
		res += right - left;
		if (left == right)++right;
	}
	cout << res << endl;
	return 0;
}
```
ABC 130 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>
#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 main() {
	int N;
	ll K;
	vector<ll>a;
	cin >> N >> K;
	a.resize(N);
	for (int i = 0; i < N; ++i)cin >> a[i];
	ll res = 0;
	int right = 0;
	ll sum = 0;
	for (int left = 0; left < N; ++left) {
		//[left,right)の総和がK以上となる最小のrightを求める
		while (right < N&&sum < K) {
			sum += a[right];
			++right;
		}
		if (sum < K)break;
		res += (ll)(N - right + 1);
		if (right == left)++right;
		else sum -= a[left];
	}
	cout << res << endl;
	return 0;
}
```
ARC 022 B
長さnの正の整数列a1,a2,…,anが与えられる。整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。 

```
#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;
}
////////////////////////////////////////

int main() {
	int n;
	int A[100100];
	cin >> n;
	for (int i = 0; i < n; ++i)cin >> A[i];
	int right = 0;
	int res = 0;
	set<int>member;
	for (int left = 0; left < n; ++left) {
		while (right < n && !member.count(A[right])) {
			member.insert(A[right]);
			++right;
		}
		res = max(res, right - left);
		if (left == right)++right;
		else {
			member.erase(A[left]);
		}
	}
	cout << res << endl;
	return 0;
}
```
setで管理する

ABC098 D Xorsum
長さnの正の整数列a1,a2,…,an が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。

```
#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;
}
////////////////////////////////////////

int main() {
	int n;
	cin >> n;
	vector<ll>a(n);
	for (int i = 0; i < n; ++i)cin >> a[i];
	ll res = 0;
	ll right = 0;
	int sum = 0;
	for (int left = 0; left < n; ++left) {
		while (right < n && (sum^a[right]) == (sum + a[right])) {
			sum += a[right];
			++right;
		}
		res += right - left;
		if (left == right)++right;
		else {
			sum -= a[left];
		}
	}
	cout << res << endl;
	return 0;
}
```
ABC 017 D サプリメント
dp[I]:=最初のI個のサプリまで吸収する方法の数(I個目を吸収した段階で一旦区切る)
dp[0]=1
dp[I]=区間[j,i）が複数種類のサプリがないという条件を満たすようなjについてのdp[j]の総和
各Iに
対して上記のようなjの範囲は尺取り法によって求めることができます。jの範囲が[left,i)で与えられるとき
dp[I]=dp[left]+dp[left+1]+....+dp[I-1]という風になる
累積和を用いて計算量を落とす。
sum[I+1]=dp[0]+dp[1]+...+dp[I]として
dp[I]=sum[I]-sum[left]と更新すればよい