### broly_1033's blog

By broly_1033, history, 16 months ago,

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?

• 0

By broly_1033, history, 16 months ago,

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

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);
}
}

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);
}

while(y<=qv[i].r) {
y++;
}
// removing y
while(y>(qv[i].r+1)) {
y--;
rem(v[y]);
}
// removing x
while(x<qv[i].l) {
rem(v[x]);
x++;
}
while(x>qv[i].l) {
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
*/


• -8

By broly_1033, history, 16 months ago,

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

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);
}
}

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);
}

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


• 0

By broly_1033, history, 17 months ago,

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) {
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--;
}

// 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;
}

• +1