白駿10999号:区間と2を求めます
21066 ワード
区間と2を求めます
白駿10999号:区間と2を求めます
アイデア
セグメント長が最大Nであるため、セグメントに存在するすべてのノードを変更するには、Nlognを使用する必要があります.
この領域に存在するすべてのノードを更新しないでください.このノードは更新する必要があります.後で訪問する時に更新してみてはいかがでしょうか.
適切なセグメントにのみ更新され、そのセグメントを表すノードの左、右childにマークされます.後でこのchildにアクセスすると、値を更新して、左childと右childに再タグ(リーフノードであれば、できないでしょう?)できました.
これでログタイムに更新できます!!
白先生が丁寧に説明してくれたセグメンテーションツリーは後で更新しますね!を読んでください.
Propage関数は,その区間の和を格納するノードにアクセスする際にlazy[node]が存在する場合,すなわち,以前更新を遅らせて表示されていた場合,その区間の和を格納するノードに区間寸法の割合で更新を遅らせる差を加える.そしてまた2人の子供に更新を押して、ほほほ、後で訪問する時に更新してください.いつの日かリフノードに到着し、爆弾の移転は終わりました.
コード#コード#
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
int N, M, K;
vector<long long> arr(MAX), tree(1<<21), lazy(1<<21);
long long init(int start, int end, int node) {
if (start == end) return tree[node] = arr[start];
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
void propagate(int start, int end, int node) {
if (lazy[node]) {
tree[node] += (end-start+1)*lazy[node];
if (start != end) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
}
long long query(int start, int end, int left, int right, int node) {
propagate(start, end, 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);
}
void update(int start, int end, int left, int right, long long diff, int node) {
propagate(start, end, node);
if (end < left || right < start) return;
if (left <= start && end <= right) {
tree[node] += (end-start+1)*diff;
if (start != end) {
lazy[node*2] += diff;
lazy[node*2+1] += diff;
}
return;
}
update(start, (start+end)/2, left, right, diff, node*2);
update((start+end)/2+1, end, left, right, diff, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
init(0, N-1, 1);
for (int i = 0; i < M+K; i++) {
int q, a, b;
cin >> q;
if (q == 1) {
long long c;
cin >> a >> b >> c;
update(0, N-1, a-1, b-1, c, 1);
}
else if (q == 2) {
cin >> a >> b;
cout << query(0, N-1, a-1, b-1, 1) << '\n';
}
}
return 0;
}
おしゃべり
どうしてこんな斬新な考えがあるの?頭を殴られたような気がします.
Reference
この問題について(白駿10999号:区間と2を求めます), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-10999번-구간-합-구하기-2
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
int N, M, K;
vector<long long> arr(MAX), tree(1<<21), lazy(1<<21);
long long init(int start, int end, int node) {
if (start == end) return tree[node] = arr[start];
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
void propagate(int start, int end, int node) {
if (lazy[node]) {
tree[node] += (end-start+1)*lazy[node];
if (start != end) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
}
long long query(int start, int end, int left, int right, int node) {
propagate(start, end, 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);
}
void update(int start, int end, int left, int right, long long diff, int node) {
propagate(start, end, node);
if (end < left || right < start) return;
if (left <= start && end <= right) {
tree[node] += (end-start+1)*diff;
if (start != end) {
lazy[node*2] += diff;
lazy[node*2+1] += diff;
}
return;
}
update(start, (start+end)/2, left, right, diff, node*2);
update((start+end)/2+1, end, left, right, diff, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
init(0, N-1, 1);
for (int i = 0; i < M+K; i++) {
int q, a, b;
cin >> q;
if (q == 1) {
long long c;
cin >> a >> b >> c;
update(0, N-1, a-1, b-1, c, 1);
}
else if (q == 2) {
cin >> a >> b;
cout << query(0, N-1, a-1, b-1, 1) << '\n';
}
}
return 0;
}
Reference
この問題について(白駿10999号:区間と2を求めます), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-10999번-구간-합-구하기-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol