DODGERS - Editorial

Contest : Division 1

Contest : Division 2

Practice

Setter : Kasra Mazaheri

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

Hard

PREREQUISITES :

Graph Theory, Persistent Segment Trees

Quick Explanation :

We can number each person according to the order in which they become Dodger’s friends. Then for each person x, we can find an interval [l_x,r_x] , l_x \le x \le r_x , such that person with id x will find the party fair only if no person outside his/her interval is invited to the party.

To answer a single query for given integers [l,r], we need to find the number of integers x, such that l \le x \le r , l_x \le l and r_x \ge r . We can do this in O(log(N)) time with O( N \cdot \log(N)) pre-processing before beginning with the queries, using a persistent segment tree

EXPLANATION :

Okay, so the first thing to note is that the huge description of the order in which Dodger’s becomes a friend with another person is just the description of a dfs done using the M edges given in the input, and people become friends with Dodger’s the first time they are visited during the dfs.

We should start a loop, from 1 to N, and if i is still not visited, then start a new dfs using it. We can maintain a global variable curr and an array time[], and when some person with index j is visited, we do time[j]=curr++ .

Assume, we completed the dfs. Then a friend with index x will feel unfair for a party with range [l,r], if there some index y, such that (x,y) are friends, l \le y \le r , and time[y] < time[x] .

Let’s call all people y, such that 1 \le y \le N , time[y] < time[x] and the edge (x,y) exists as enemies of x. A simple observation we can make here is that we can calculate for each person with id x, two integers l_x and r_x, that indicate :

l_x : The minimum possible value of l given in a query, such that the range [l,x] does not include any enemies of x.

r_x : The maximum possible value of r given in a query, such that the range [r,x] does not include any enemies of x.

Note that if the range [a,x] does not include any enemies of x, then the ranges [a+1,x],[a+2,x],...,[x,x] also do not include any enemies of x, and if the range [x,b] does not include any enemies of x, then the ranges [x,b-1],[x,b-2],....[x,x] also do not include any enemies of x.

If, in some query, we get some l, such that l < l_x , then we guaranteed that x can never feel fair for this party, since there exists at least one enemy of his in the range [l,x]. Similarly, if in some query we get some r such that r > r_x, then we guaranteed that x can never feel fair for this party, since there exists at least one enemy of his in the range [x,r].

We can calculate all easily all [l_x,r_x] in O(M) time, by, just going over each edge.

So, for a given query [l,r], the task now transforms to the following :

Find the number of x, such that l \le x \le r , l_x \le l and r_x \ge r . A sub task to know how to answer each query in O( \log(N)) time is to know how to use a persistent segment tree, to answer queries of the form :

Given an array A[] and Q queries (l,r,K), you need to find the number of x, such that l \le x \le r and A[x] \le K . This is quite a well known problem, and you can read about it here and here.

Now, once you know the above, we can proceed as follows :

First we need to find the number of x, such that 1 \le x \le N , l_x \le l and r_x \ge r. We can do this by building a persistent segment tree in increasing order of l_x , updating their respective r_x in the leaves, and then find in segment tree of l, the sum of the range [r,\infty].

Then, we need to subtract from this the number of x , such that 1 \le x < l and r_x \ge r . We can do this by building a segment tree in increasing order of i, and updating in the leaves it’s respective r_i . Then, we query segment tree of l-1 for the sum of the range [r,\infty]. What this query gives us is the the number of x, such that 1 \le x < l , l_x \le l and r_x \ge r . This obviously works because l_x \le x

Then we need to subtract from this, the number of x, such that r+1 \le x \le N , and r_x \le l . We can do this by building a persistent segment tree on decreasing order of i, and updating in the leaves their corresponding l_i . Then, we query segment tree of r+1 for the sum of the range [0, l]. What this query gives us is the the number of x, such that r+1 \le x \le N , l_x \le l and r_x \ge r . This obviously works because r_x \ge x

After we do this, notice that the only thing we are left with is the number of x, such that l \le x \le r , l_x \le l and r_x \ge r . And this is exactly what we wanted. Since each of these queries takes O(\log(N)) time, the time taken to answer a single query is O( \log(N)) .

Now, for any implementation or clarity issues, you can refer to the setter’s solution, its quite neat and easy to read.

That’s it, thank you.

COMPLEXITY ANALYSIS :

Time Complexity : O( (N+Q) \cdot \log (N)+M )

Space Complexity : O(N \cdot \log(N)+M)

Setter
// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006, MXS = N * 22;
int n, m, q, ts, tp, St[N], A[N], B[N];
vector < int > Adj[N], V[N];
tuple < int , int , int > QU[N];
struct PRSTree
{
int ts = 0, root[N], L[MXS], R[MXS], C[MXS];
inline void Reset()
{
for (int i = 0; i <= n + 1; i ++)
root[i] = 0;
for (int i = 0; i <= ts; i ++)
L[i] = R[i] = C[i] = 0;
ts = 0;
}
inline int Add(int i, int id)
{
int l = 0, r = n + 2, rt = ts + 1;
while (1)
{
++ ts;
L[ts] = L[id];
R[ts] = R[id];
C[ts] = C[id] + 1;
if (r - l < 2)
break;
if (i < ((l + r) >> 1))
L[ts] = ts + 1, id = L[id], r = l + r >> 1;
else
R[ts] = ts + 1, id = R[id], l = l + r >> 1;
}
return (rt);
}
inline int Get(int le, int ri, int id)
{
int l, r;
int ql = 0, qr = 0, rt = 0;
QU[qr ++] = make_tuple(id, 0, n + 2);
while (qr - ql)
{
tie(id, l, r) = QU[ql ++];
if (ri <= l || r <= le)
continue;
if (le <= l && r <= ri)
{
rt += C[id];
continue;
}
QU[qr ++] = make_tuple(L[id], l, l + r >> 1);
QU[qr ++] = make_tuple(R[id], l + r >> 1, r);
}
return (rt);
}
};
PRSTree X, Y, Z;
void DFS(int v)
{
St[v] = ++ ts;
if (!St[u])
DFS(u);
}
{
char ch = getchar();
int rt = 0;
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
rt = rt * 10 + ch - '0', ch = getchar();
return (rt);
}
inline void Solve()
{
//scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i ++)
{
int v, u;
//scanf("%d%d", &v, &u);
}
for (int i = 1; i <= n; i ++)
if (!St[i]) DFS(i);
for (int i = 1; i <= n; i ++)
{
A[i] = 0; B[i] = n + 1;
if (St[u] < St[i])
if (u < i)
A[i] = max(A[i], u);
else
B[i] = min(B[i], u);
}
for (int i = 1; i <= n; i ++)
V[A[i]].push_back(B[i]);
for (int i = 0; i <= n; i ++)
{
if (i)
Z.root[i] = Z.root[i - 1];
for (int b : V[i])
}
for (int i = 1; i <= n; i ++)
X.root[i] = X.Add(B[i], X.root[i - 1]);
for (int i = n; i; i --)
Y.root[i] = Y.Add(A[i], Y.root[i + 1]);

for (int last = 0; q; q --)
{
int l, r;
//scanf("%d%d", &l, &r);
l = (l + last - 1) % n + 1;
r = (r + last - 1) % n + 1;
if (l > r) swap(l, r);
last = Z.Get(r + 1, n + 2, Z.root[l - 1]);
last -= X.Get(r + 1, n + 2, X.root[l - 1]);
last -= Y.Get(0, l, Y.root[r + 1]);
printf("%d\n", last);
if (tp == 0) last = 0;
}
/*for (int i = 0; i <= n + 1; i ++)
Adj[i].clear(), V[i].clear(), St[i] = A[i] = B[i] = 0;
X.Reset(); Y.Reset(); Z.Reset();
n = m = q = ts = 0;*/
return ;
}
int main()
{
int TC;
scanf("%d", &TC);
for (; TC; TC --)
Solve();
return 0;
}

3 Likes

Can anyone please tell how to solve this question for offline queries

Hint : It can be done using prefix and suffix sums over a binary indexed tree. Can you think of a solution now ?

1 Like

thanks is there any other way to do it