1. prefix sum

prefix sumは累積を表す
ぎじゅつ
prefix sum:推定値の保存
DPの問題に近いように見えます.

質問する

11659区間と4を求めます

区間求和問題は問題の制限が大きいため,時間制限内に通過できない.
O(NM)の時間が必要です.

prefix sumを使って
以上のようにpre表が記入されていれば4,6の和を求めることができる.
このようにあらかじめ計算して出力すると,N回の繰り返し文を迂回するだけなので,O(N)だけで問題を終わらせることができる.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	vector<ll> a(n+1);
	vector<ll> pre(n+1);
	pre[0] = 0;
	for (i = 1; i <= n; ++i) {
		int temp;
		cin >> temp;
		a.push_back(temp);
		pre[i] = pre[i - 1] + temp;
	}
	while (m--) {
		int s, e;
		cin >> s >> e;
		int ans = 0;
		cout << pre[e]-pre[s-1] << '\n';
	}
}

しかし、このようにして中間的に値下がりすれば、何のメリットもありません.
したがって、「セグメントツリー」を使用すると、演算プロセスにO(logn)の時間がかかります.

11660区間加算5

この問題も区間と4を求めることに似ている.

欲しい部分の上と左を除いて、共通の部分を加えればいいです.
では、このような方式のためにpre[i][j]をどのように実施するのか.
正解は次のとおりです.
𝑎𝑛𝑠 = 𝑝𝑟𝑒[𝑐][𝑑] − 𝑝𝑟𝑒[𝑎 − 1][d] − 𝑝𝑟𝑒[c][𝑏 − 1] + 𝑝𝑟𝑒[𝑎 − 1][𝑏 − 1]
正解を求めるためには、次の式で求めることができます.
𝑝𝑟𝑒[𝑖][𝑗] = 𝑝𝑟𝑒[𝑖][𝑗 − 1] + 𝑝𝑟𝑒[𝑖 − 1][𝑗] − 𝑝𝑟𝑒[𝑖 − 1][𝑗 − 1] + 𝐴[𝑖][𝑗];

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
int a[1025][1025];
int pre[1025][1025];

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= n; ++j) {
			cin >> a[i][j];
			pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
		}
	}
	while (m--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		cout << pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1] << '\n';
	}
}

2. two pointer

デュアルポインタは、アレイ内の2つの異なる要素を指す点を操作し、問題を解決します.

質問する

2003ツリーの和2

この問題はprefix sumだけでは不可能です.O(n^3)の時間が必要だからです.

最も簡単な解法はtwo pointerを用い,所望の値より小さい場合はb,1より大きい場合は1を加える.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
vector<ll> a;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (i = 0; i < n; ++i) {
		ll temp;
		cin >> temp;
		a.push_back(temp);
	}

	int s = 0, e = 0;
	ll sum = 0;
	ll ans = 0;
	while (1) {
		if (sum >= m) sum -= a[s++];
		else if (e == n) break;
		else sum += a[e++];
		if (sum == m) ans += 1;

	}
	cout << ans << '\n';
}

1484ダイエット

これはダイエットの問題です.アレイに平方数を加えて、二重ポインタで解きましょう.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
vector<ll> a;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll d = 0;
	cin >> d;

	for (ll i = 1; i < 200001; ++i) {
		a.push_back(i * i);
	}
	vector<ll> ans;
	ll s = 0, e = 0;
	ll diff = 0;
	while (1) {
		if (e >= a.size()) break;
		diff = a[e] - a[s];
		if (diff < d) e++;
		if(diff>d) s++;
		if (diff == d) {
			ans.push_back(sqrt(a[e]));
			e++;
		}
	}

	if (!ans.size()) {
		cout << "-1" << '\n';

	}
	else {
		for (ll i : ans) {
			cout << i << '\n';
		}
	}
	return 0;
}

1253はい

この問題には2つの落とし穴がある.
1.数値に負/正があります.
[原句]自分以外なら何でもいい.
したがって,二重ポインタと並べ替えを用いて解くことができる.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n = 0;
	cin >> n;

	vector<ll> a(n);
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	ll ans = 0;
	for (int i = 0; i< n; ++i) {
		int s = 0, e = n - 1;
		ll target = a[i];
		while (s < e) {
			ll sum = a[s] + a[e];
			if (sum < target) {
				s+=1;
			}
			else if (sum > target) {
				e-=1;
			}
			else if(sum==target){
				if (s != i and e != i) {
					//cout << target << ' ' << a[s] << ' ' << a[e] << '\n';
					ans += 1;
					break;
				}
				else if (s == i) {
					s += 1;
				}
				else if(e==i){
					e -= 1;
				}
			}

		}
		
	}
	cout << ans << '\n';
}