How to solve segment tree problem, modification queries with a twist?

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

LogitechSellout's blog

How to solve segment tree problem, modification queries with a twist?

By LogitechSellout, history, 4 years ago, In English

This was inspired by http://www.usaco.org/index.php?page=viewproblem2&cpid=842

The problem statement is: Given an array $$$a$$$, you are given two types of queries. The first type asks you to query for a single element $$$a[i]$$$, The second type is of update type $$$(l,r,val)$$$, where all $$$a[i]$$$ such that $$$l<=i<=r$$$ are unchanged if $$$a[i]<=val$$$, and reduced to $$$val$$$ if $$$a[i]>val$$$. You can imagine that the array a is a head of hair with hair lengths $$$a[i]$$$ at position $$$i$$$, and you want to cut some given intervals to a given length

This can be easily solved offline — just sort the update queries in decreasing $$$val$$$ and it's a textbook segment tree problem (you can do this in the usaco). But how do you solve it online?

#data structures, #segment tree

-6

LogitechSellout
4 years ago
5

Comments (4)

Show archived | Write comment?

-is-this-fft-

4 years ago, # |

Fairly standard lazy propagation.

→ Reply

Everule

4 years ago, # ^ |

I'm not sure if you meant this solution, but I think a single normal segment tree is enough.

Let us look at queries on a segment tree.

When we query, we query a disjoint set of ranges, such that it covers all nodes in the range.

When we update, we update a single element all the ranges that contain it.

Now if we flip the purposes of the 2 functions, this can be done simply.

For updating, we use the query function, and update all ranges and take minimum with val.

When we query, we use the update function, and the answer is the minimum of a[i], and all the values in the ranges it is contained in.

→ Reply

LogitechSellout

4 years ago, # ^ |

I tried to do something like that but it gives WA, either my implementation is bad or simple segment tree doesn't work.

My code snippet here: https://ideone.com/PaEJsU if anyone has time to debug

→ Reply

Everule

4 years ago, # ^ |

-6

At the very least, you could try coding something even resembling my idea. Why do you need to push here? Why is there a lazy array?

Code

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
struct segment_tree {
    int n;
    vector<T> segtree;
    function<T(const T&,const T&)> join;
    T base = T();
    segment_tree(int n, function<T(const T&,const T&)> join, T base = T()) : n(n), join(join), base(base){
        segtree.resize(n << 1, base);
    }
    void build() {
        for (int i = n - 1; i > 0; --i) {
            segtree[i] = join(segtree[(i << 1)], segtree[(i << 1) | 1]);
        }
    }
    segment_tree(vector<T> seq, function<T(const T&,const T&)> join, T base = T()) : n(seq.size()), join(join), base(base){
        segtree.resize(n << 1, base);
        for (int i = 0; i < n; i++) {
            segtree[n + i] = seq[i];
        }
        //build();
    }
    void update(int l,int r, ll val){
        T ansl = base;
        T ansr = base;
        l += n;
        r += n + 1;
        while (l < r) {
            if (l & 1) {
                segtree[l] = join(segtree[l], val);
                ++l;
            }
            if (r & 1) {
                --r;
                segtree[r] = join(segtree[r], val);
            }
            l >>= 1;
            r >>= 1;
        }
    }
    T query(int pos) {
        pos+=n;
        ll ans = segtree[pos];
        pos>>=1;
        while(pos){
            ans = join(segtree[pos], ans);
            pos>>=1;
        }
        return ans;
    }
};
void solve(){
    int n;
    cin>>n;
    vector<int> seq(n);
    for(auto &x : seq) cin>>x;
    segment_tree<int> segtree(seq, [&](const int &x, const int &y){
        return x<y ? x : y;
    }, 2e9);
    int Q;
    cin>>Q;
    while(Q--){
        int type;
        cin>>type;
        if(type==0){
            int l,r,val;
            cin>>l>>r>>val;
            //--l;--r;//If one indexed
            segtree.update(l,r,val);
        }
        else{
            int pos;
            cin>>pos;
            //--pos; //If one indexed
            cout<<segtree.query(pos)<<"\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

According to me, your code is using lazy propogation, but it is not pushing on queries? I'm not sure what you have done.

→ Reply