Hi everyone, I was studying how to solve query problems on trees using Euler Tour. I was wondering how to solve path query problems on trees. We can solve problems which can be solved by maintaining a prefix array (for e.g. sum of nodes in path from a to b), but how to solve say, node with maximum value in path from a to b. Can anyone guide me on this?
More specifically, sum(a, b) = sum(root, a) + sum(root, b) — 2*sum(root, lca(a, b)) + val(lca). I was using this to solve these problems using Euler Tour. But I cannot find maximum using this (CSES Path Queries 2).
Q1. Can we apply segment trees on Euler Tour array? Q2. How to solve problems like CSES Path Queries 2?

Hey guys, I was solving ADAUNIQ on SPOJ but couldn't find a proper understandable solution when I was stuck. I was trying to solve it using Mo's algorithm with updates but couldn't find a working code for the same. So I thought of sharing this, if it could help someone.

// first writing without coordinateCompression
// Note: We also have to coordinateCompress the update values in query

#include<bits/stdc++.h>
using namespace std;

const int N = 2*1e5;

class query {
public:
    int id, l, r, res, time;
//    int block;
};
vector<query> qv;
vector<pair<int, int> > updateQueries;

int distinct = 0; // distinct elements in current window
int cnt[N+5]; // stores the frequency


void add(int val) {
    cnt[val]++;
    if(cnt[val]==1) distinct++;
    if(cnt[val]==2) distinct--;
    // we are finding unique values in a range
    // if we find duplicate, the kind will no longer be distinct
    // not same distinct as in DQUERY
}
void rem(int val) {
    cnt[val]--;
    if(cnt[val]==0) distinct--;
    if(cnt[val]==1) distinct++;
}

void update(vector<int>& v, int i, int x, int y) {

    int idx = updateQueries[i].first;
    int val = updateQueries[i].second;

    int old = v[idx];
    v[idx] = val;
    updateQueries[i].second = old;

    if(idx>=x && idx<y) { // as our range is [x, y)
        rem(old);
        add(val);
    }
}

int main() {

    ios_base::sync_with_stdio(0); cin.tie(NULL);

    int n, num_q; cin>>n>>num_q;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

    int sz = pow(n, 2./3.)+1;

    for(int i=0; i<num_q; i++) {

        int c; cin>>c;
        if(c==1) {
            int idx, val; cin>>idx>>val;
            updateQueries.push_back(make_pair(idx, val));
        } else if(c==2) {
            query q;
            cin>>q.l; cin>>q.r;

            q.id = i; q.time = updateQueries.size();
//            q.block = (q.l)/sz;
            qv.push_back(q);

        }
    }

    // sort queries
    sort(qv.begin(), qv.end(), [&](query a, query b){

        if((a.l)/sz==(b.l)/sz){
            if((a.r)/sz==(b.r)/sz) return a.time<b.time;
            return ((a.r)/sz)<((b.r)/sz);
         }
         return (a.l)<(b.l);

    });

    int x = 0, y = 0; // maintain current window, [x, y)
    int current_time = 0;
    for(int i=0; i<qv.size(); i++) {

        // update time
        int time = qv[i].time;

        while(current_time<time) {
            update(v, current_time, x, y);
            current_time++;
        }
        while(current_time>time) {
            current_time--;
            update(v, current_time, x, y);
        }

        // add y
        while(y<=qv[i].r) {
            add(v[y]);
            y++;
        }
        // removing y
        while(y>(qv[i].r+1)) {
            y--;
            rem(v[y]);
        }
        // removing x
        while(x<qv[i].l) {
            rem(v[x]);
            x++;
        }
        // add x
        while(x>qv[i].l) {
            x--;
            add(v[x]);
        }

        qv[i].res = distinct;

    }

    sort(qv.begin(), qv.end(), [&](query a, query b){
            return a.id<b.id;
    });

    for(int i=0; i<qv.size(); i++) {
        cout<<qv[i].res<<'\n';
    }

    return 0;
}

/*
8 8
1 2 3 3 1 2 3 3
2 1 3
2 0 3
2 0 7
1 3 4
1 7 0
2 1 3
2 0 3
2 0 7
*/

Hey everyone, I was trying ADAUNIQ problem on SPOJ https://www.spoj.com/problems/ADAUNIQ/. I want to solve it using Mo's algorithm with updates, I have written the code. It gives the correct output for the default test case also but gives wrong answer on submission. I tried debugging it but couldn't find any fault. I would be extremely thankful if someone can look at my code. Please note that the question asks for "number of unique elements in a segment", so if a segment is [1, 2, 3, 3] the answer will be 2 (because 1 and 2 occur once) and not 3 (not 1, 2, 3 because 3 occurs twice).

#include<bits/stdc++.h>
using namespace std;

const int N = 2*1e5;

class query {
public:
    int id, l, r, res, time;
//    int block;
};
vector<query> qv;
vector<pair<int, int> > updateQueries;

int distinct = 0; // distinct elements in current window
int cnt[N+5]; // stores the frequency


void add(int val) {
    cnt[val]++;
    if(cnt[val]==1) distinct++;
    if(cnt[val]==2) distinct--;
    // we are finding unique values in a range
    // if we find duplicate, the kind will no longer be distinct
    // not same distinct as in DQUERY
}
void rem(int val) {
    cnt[val]--;
    if(cnt[val]==0) distinct--;
    if(cnt[val]==1) distinct++;
}

void update(vector<int>& v, int i, int x, int y) {

    int idx = updateQueries[i].first;
    int val = updateQueries[i].second;

    int old = v[idx];
    v[idx] = val;
    updateQueries[i].second = old;

    if(idx>=x && idx<=y) {
        rem(old);
        add(val);
    }
}

int main() {

    ios_base::sync_with_stdio(0); cin.tie(NULL);

    int n, num_q; cin>>n>>num_q;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

    int sz = pow(n, 2/3)+1;

    for(int i=0; i<num_q; i++) {

        int c; cin>>c;
        if(c==1) {
            int idx, val; cin>>idx>>val;
            updateQueries.push_back(make_pair(idx, val));
        } else if(c==2) {
            query q;
            cin>>q.l; cin>>q.r;

            q.id = i; q.time = updateQueries.size();
//            q.block = (q.l)/sz;
            qv.push_back(q);

        }
    }

    // sort queries
    sort(qv.begin(), qv.end(), [&](query a, query b){

        if((a.l/sz)==(b.l)/sz){
            if((a.r/sz)==(b.r/sz)) return a.time<b.time;
            return (a.r/sz)<(b.r/sz);
         }
         return (a.l/sz)<(b.l/sz);

    });

    int x = 0, y = 0; // maintain current window, [x, y)
    int current_time = 0;
    for(int i=0; i<qv.size(); i++) {

        // update time
        int time = qv[i].time;

        while(current_time<time) {
            update(v, current_time, x, y);
            current_time++;
        }
        while(current_time>time) {
            current_time--;
            update(v, current_time, x, y);
        }

        // add y
        while(y<=qv[i].r) {
            add(v[y]);
            y++;
        }
        // removing y
        while(y>(qv[i].r+1)) {
            y--;
            rem(v[y]);
        }
        // removing x
        while(x<qv[i].l) {
            rem(v[x]);
            x++;
        }
        // add x
        while(x>qv[i].l) {
            x--;
            add(v[x]);
        }

        qv[i].res = distinct;

    }

    sort(qv.begin(), qv.end(), [&](query a, query b){
            return a.id<b.id;
    });

    for(int i=0; i<qv.size(); i++) {
        cout<<qv[i].res<<'\n';
    }

    return 0;
}

Hello everyone, I was learning about square root decomposition and Mo's algorithm and was practicing a few questions. I believe I have understood the concept. So I was trying problem 221D, and I've written the code and it works too, but I am getting TLE on submitting it. I was using coordinate compression as range was 10^9, then realized that for numbers >10^5 the condition won't be met so they are of no use. I am sorting using custom comparators, also included fast input/output. Then I removed the use of sorting queries for final answer by directly using the query id and storing the answer in a new array 'ans', which I can directly print. Can anyone look at the code, and suggest why am I still getting TLE on test case 5(I am stuck for the past 1 day)? Thank you!

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
class query{
public:
    int l, r, id, block, res;
} q[2*N];

int freq[N+5];
int xx = 0;

void add(vector<int>& v, int i) {

    if(v[i]>N) return; // as 10^5 is the maximum size of array
    // x>10^5, can ever have freq[x] = x

    freq[v[i]]++;
    if(freq[v[i]]==v[i]) xx++;
}
void rem(vector<int>& v, int i) {

    if(v[i]>N) return;

    if(freq[v[i]]==v[i]) xx--;
    freq[v[i]]--;
}

// Code for coordinate compression

//vector<int> d;
//void add(vector<int>& v, int i) {
//
//    if(v[i]>=N) return;
//
//    freq[v[i]]++;
//    if(freq[v[i]]==d[v[i]]) xx++;
//}
//void rem(vector<int>& v, int i) {
//
//    if(v[i]>=N) return;
//
//    if(freq[v[i]]==d[v[i]]) xx--;
//    freq[v[i]]--;
//}
//
//void coordinateCompression(vector<int>& v) {
//    d = v;
//    sort(d.begin(), d.end());
//    d.resize(unique(d.begin(), d.end()) - d.begin());
//    for (int i = 0; i < v.size(); ++i) {
//        v[i] = lower_bound(d.begin(), d.end(), v[i]) - d.begin();
//    }
//}

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m; cin>>n>>m;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

//    coordinateCompression(v);

    int sz = sqrt(n)+1;

    int l, r;
    for(int i=0; i<m; i++) {
        cin>>l>>r;
        q[i].l = l-1; q[i].r = r-1;
        q[i].id = i;
        q[i].block = i/sz;
    }

    // sorting using custom comparator
    sort(q, q+m, [&](query a, query b){
        if(a.block==b.block) return a.r<b.r;
        return a.block<b.block;
    });

    int x = 0, y = 0;
    memset(freq, 0, sizeof(int)*(N+5));

    int ans[m];
    memset(ans, 0, sizeof(int)*m);

    for(int i=0; i<m; i++) {

        while(y<=q[i].r) {
            add(v, y);
            y++;
        }
        while(y>q[i].r+1) {
            y--;
            rem(v, y);
        }
        while(x<q[i].l) {
            rem(v, x);
            x++;
        }
        while(x>q[i].l) {
            x--;
            add(v, x);
        }

        // instead of sorting q with id, use id to create new ans array
        // in sorted manner

//        q[i].res = xx;
        ans[q[i].id] = xx;

    }

//    sort(q, q+m, [&](query a, query b){
//        return a.id<b.id;
//    });

    for(int i=0; i<m; i++) {
//        cout<<q[i].res<<'\n';
        cout<<ans[i]<<'\n';
    }


return 0;
}