DODGERS - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Kasra Mazaheri

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

DIFFICULTY :

Hard

PREREQUISITES :

Graph Theory, Persistent Segment Trees

PROBLEM :

Please read it here.

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.

Your Comments are welcome !

COMPLEXITY ANALYSIS :

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

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

SOLUTION LINKS :

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;
    for (int u : Adj[v])
        if (!St[u])
            DFS(u);
}
inline int read()
{
    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);
    n = read(); m = read(); q = read(); tp = read();
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        //scanf("%d%d", &v, &u);
        v = read(); u = read();
        Adj[v].push_back(u);
        Adj[u].push_back(v);
    }
    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;
        for (int u : Adj[i])
            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])
            Z.root[i] = Z.Add(b, Z.root[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 = read(); r = read();
        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