天下一プログラマーコンテスト2016予選B D - 天下一数列にクエリを投げます

問題

問題概要

区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。

解法

segtreeぽいな感はある。90度回転させてみるのは思いつかない。 解法は公式解説がわかりやすい。

https://tenka1-2016-qualb.contest.atcoder.jp/data/other/tenka1-2016-qualb/editorial.pdf

今回作らなければならないsegtreeは
-区間に⼀様に数を⾜す
-区間の中での最⼩値を取得
なので遅延segtreeは以下の 変更するのは以下の5点? 下の問題の時はは3か所て書いたけど、5かな、あとは、lazyの初期化部分とかも気をつけないと、今回は加える数字だから、遅延がない=0

mmxsrup.hatenablog.com

(1)遅延情報の適用方法 -lazyにはその区間に加えなければならないが、また加えていない値が入っているので、加える
(2)遅延情報の伝搬方法 -lazyはその区間に加える値なので、lazyを子に伝搬するときは加える
(3)値のマージ -segはその区間の最小値を入れるので、minをとる
(4)欲しい値の戻り値 -(3)と同じことをするだけ
(5)遅延情報の更新 -updateで新たに範囲に加える値が来るので、それをlazyに加える
の5箇所を変更すればいいのかな?

ミス

難しいい。遅延segtreeはだいぶわかっってきた。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//区間に⼀様に数を⾜すと区間の中での最⼩値を取得をできるsegtree
const int MAX_N = 1 << 20;
const ll INF = 1e9;
int size;
ll seg[MAX_N * 2], lazy[MAX_N * 2];//segは欲しい情報 lazyは区間に対する一様な処理を示すもの?
struct segtree{
    //seg:区間の最小値 lazy:区間に対して、加える値でまだ遅延しているもの
    segtree(int n){
        size = 1;
        while(size < n) size *= 2;//要素数を2のべき乗に
        for (int i = 0; i < 2 * size - 1; ++i) lazy[i] = 0;//0は遅延しているものがないことを示す
    }

    //遅延評価
    void lazy_evaluate_node(int k, int l, int r){
        if(lazy[k] != 0){//遅延がある時
            //(1)この位置を変える(遅延情報の適用方法)
            seg[k] += lazy[k];//区間[l,r)にすべて同じ値を追加することになっていて、segには最小値が入っているので、加える値を足すだけ
            if(r  - l > 1){
                //(2)この位置を変える(遅延情報の伝搬方法) 今回は数字を加える
                lazy[k * 2 + 1] += lazy[k];//左の子に伝搬
                lazy[k * 2 + 2] += lazy[k];//右の子に伝搬
            }
            lazy[k] = 0;//ノードkは伝搬完了
        }
    }

    //update(a,b,v) := [a,b)を全てvを加える
    void update(int a, int b, ll v, int k = 0, int l = 0, int r = size){
        lazy_evaluate_node(k, l, r);//辿ったノードはついでについでに伝搬しておく
        if(r <= a || b <= l) return;//[a,b)がノードkの区間[l, r)と交差しない
        if(a <= l && r <= b){//[a,bが[l,r)を完全に含んでいる
            //(5)この位置を変える(遅延情報のの更新)
            lazy[k] += v;//ノードkの区間[l,r)を全てvを加えるa
            lazy_evaluate_node(k, l, r);//一回遅延評価しとかないと都合悪い?? ([l,r)の葉の数字は全て同じ値)
        }else{
            update(a, b, v, k * 2 + 1, l, (l + r) / 2);
            update(a, b, v, k * 2 + 2, (l + r) / 2, r);
            //(3)この位置を変える (値のマージ)
            seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);//ノードkを更新 ２つの子の最小値
        }
    }

    //get(a,b) := [a,b)に対する最小値を求める
    ll get(int a, int b, int k = 0, int l = 0, int r = size){
        lazy_evaluate_node(k, l, r);//辿ったノードはついでについでに伝搬しておく
        if(r <= a || b <= l) return INF;//[a,b)がノードkの区間[l, r)と交差しない時INFを返す
        if(a <= l && r <= b) return seg[k];//[a,bが[l,r)を完全に含んでいる時そのノードの値を返す
        ll x = get(a, b, k * 2 + 1, l, (l + r) / 2);//左の子の最小値
        ll y = get(a, b, k * 2 + 2, (l + r) / 2, r);//右の子の最小値
        //(4)この位置を変える(欲しい値の戻り値) (3)と同じ感じに
        return min(x, y);
    }
};

int l[100010], r[100010], x[100010];
int s[100010], t[100010], k[100010];
vector<pair<int, int> > add[100010], del[100010];
vector<int> query[100010];
int main(void){
    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];
    int A; cin >> A;
    //a[i]のi列に対しての処理ごとにリスト化
    rep(i, A){
        cin >> l[i] >> r[i] >> x[i];
        add[l[i]].push_back(make_pair(i, x[i]));
        del[r[i]].push_back(make_pair(i, x[i]));
    }
    int B; cin >> B;
    //a[i]のi列に対しての処理ごとにリスト化
    rep(i, B){
        cin >> s[i] >> t[i] >> k[i];
        query[k[i]].push_back(i);//ai列目に対するクエリが何個目のクエリなのか
    }

    ll ans[100010];//ans[i] := i番目のクエリに関する答え
    segtree st(A + 1);
    //a1列からan列へ順番に見ていく(それぞれの列の初期値は無視して、増加現象部分のみの列としてみる)
    for (int i = 1; i <= n; ++i){
        st.update(0, 1, 0);
        for(auto u : add[i]){
            st.update(u.first + 1, A + 1, u.second);//[u,A)まで加算
        }
        for(auto u : query[i]){
            ans[u] = a[k[u] - 1] + st.get(s[u] - 1, t[u] + 1);//初項と範囲の最小値
        }
        for(auto u : del[i]){
            st.update(u.first + 1, A + 1, -u.second);//[u,A)まで減算
        }
    }
    rep(i, B){
        printf("%lld\n", ans[i]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

const int MAX_N = 1 << 18;
ll seg[MAX_N * 2], lazy[MAX_N * 2];//segは欲しい情報 lazyは区間に対する一様な処理を示すもの
struct segtree{
public:
    int SIZE;
    //seg:区間の最小値 lazy:区間に対して、加える値でまだ遅延しているもの
    segtree(int n){
        SIZE = 1;
        while(SIZE < n) SIZE *= 2;//要素数を2のべき乗に
        for (int i = 0; i < 2 * SIZE - 1; ++i) lazy[i] = 0;//0は遅延しているものがないことを示す
    }
    void lazy_evaluate(int k, int l, int r){//遅延情報の適用方法
        if(lazy[k] != 0){
            seg[k] += lazy[k];//区間[l,r)にすべて同じ値を追加することになっていて、segには最小値が入っているので、加える値を足す
            if(r  - l > 1){
                lazy[k * 2 + 1] += lazy[k];//遅延を左の子に伝搬
                lazy[k * 2 + 2] += lazy[k];//遅延を右の子に伝搬
            }
            lazy[k] = 0;//ノードkは伝搬完了
        }
    }
    void update(int a, int b, int k, int l, int r, ll x){
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            lazy[k] += x; //加える
            lazy_evaluate(k, l, r);
        }else{
            update(a, b, k * 2 + 1, l, (l + r) / 2, x);
            update(a, b, k * 2 + 2, (l + r) / 2, r, x);
            seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); //区間のmin
        }
    }  
    ll query(int a, int b, int k, int l, int r){
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return INF;//minの影響のないもの
        if(a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(x, y); //左右のminを
    }
    //update(a,b,x) := [a,b)を全てxを加える
    void update(int a, int b, int x){update(a, b, 0, 0, SIZE, x);}
    //query(a,b) := [a,b)に対する最小値を求める
    ll query(int a, int b){return query(a, b, 0, 0, SIZE);}
};

int l[100010], r[100010], x[100010];
int s[100010], t[100010], k[100010];
vector<pair<int, int> > add[100010], del[100010];
vector<int> query[100010];
int main(void){
    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];
    int A; cin >> A;
    //a[i]のi列に対しての処理ごとにリスト化
    rep(i, A){
        cin >> l[i] >> r[i] >> x[i];
        add[l[i]].push_back(make_pair(i, x[i]));
        del[r[i]].push_back(make_pair(i, x[i]));
    }
    int B; cin >> B;
    //a[i]のi列に対しての処理ごとにリスト化
    rep(i, B){
        cin >> s[i] >> t[i] >> k[i];
        query[k[i]].push_back(i);//ai列目に対するクエリが何個目のクエリなのか
    }

    ll ans[100010];//ans[i] := i番目のクエリに関する答え
    segtree st(A + 1);
    //a1列からan列へ順番に見ていく(それぞれの列の初期値は無視して、増加現象部分のみの列としてみる)
    for (int i = 1; i <= n; ++i){
        st.update(0, 1, 0);
        for(auto u : add[i]){
            st.update(u.first + 1, A + 1, u.second);//[u,A)まで加算
        }
        for(auto u : query[i]){
            ans[u] = a[k[u] - 1] + st.query(s[u] - 1, t[u] + 1);//初項と範囲の最小値
        }
        for(auto u : del[i]){
            st.update(u.first + 1, A + 1, -u.second);//[u,A)まで減算
        }
    }
    rep(i, B){
        printf("%lld\n", ans[i]);
    }
    return 0;
}