白駿7578号:工場
11869 ワード
工場。
白駿7578号:工場
アイデア
A列入力を受信すると,マシンの識別番号をインデックスの配列としてそのマシンのA列における位置を記録する.
B列入力を受け取ると、A列がインデックスの何番にあるかを求め、その位置から、右から最後のセグメントまで、接続行の個数を求める.
こんな感じで!
コード#コード#
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000001;
int N;
vector<int> arr(MAX);
vector<int> tree(MAX*4);
void update(int start, int end, int idx, int node) {
if (idx < start || end < idx) return;
if (start == end) {
tree[node]++;
return;
}
update(start, (start+end)/2, idx, node*2);
update((start+end)/2+1, end, idx, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int query(int start, int end, int left, int right, int node) {
if (end < left || right < start) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
int x;
for (int i = 0; i < N; i++) {
cin >> x;
arr[x] = i;
}
long long ans = 0;
for (int i = 0; i < N; i++) {
cin >> x;
int pos = arr[x];
ans += query(0, MAX-1, pos, MAX-1, 1);
update(0, MAX-1, pos, 1);
}
cout << ans;
return 0;
}
おしゃべり
答えがintの範囲を超えていることに注意してください.
Reference
この問題について(白駿7578号:工場), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-7578번-공장
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000001;
int N;
vector<int> arr(MAX);
vector<int> tree(MAX*4);
void update(int start, int end, int idx, int node) {
if (idx < start || end < idx) return;
if (start == end) {
tree[node]++;
return;
}
update(start, (start+end)/2, idx, node*2);
update((start+end)/2+1, end, idx, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int query(int start, int end, int left, int right, int node) {
if (end < left || right < start) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
int x;
for (int i = 0; i < N; i++) {
cin >> x;
arr[x] = i;
}
long long ans = 0;
for (int i = 0; i < N; i++) {
cin >> x;
int pos = arr[x];
ans += query(0, MAX-1, pos, MAX-1, 1);
update(0, MAX-1, pos, 1);
}
cout << ans;
return 0;
}
Reference
この問題について(白駿7578号:工場), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-7578번-공장テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol