QUEHEA : Editorial

Link to the Contest:
https://www.codechef.com/CSPK2020

QUEHEA : Editorial
Author: CodeChef Public Repository
Tester: easy3279
Editorialist : chaitanya_44
Difficulty : medium
Problem:

Wonderland is a wonderful world inhabited by N strange creatures, for simplicity all creatures are numbered from 1 to N. Every creature has exactly one best friend (it could be himself too). Note that, the friendship relationship is not bidirectional, meaning that it might be the case person x is best friend of y, but y is not best friend of x. Besides that, there is a very intricate admiration relationship among the creatures. Every creature admires himself and to all the creatures admired by his best friend.

Wonderland is divided in many guilds, each creature belonging to exactly one guild, also each guild contains at least one creature. A guild is defined as the largest set of creatures in which if we take any two creatures i, j, then there exists a creature k such that both i and j admire k. For given best friend relationship for all persons, the guilds formed will be uniquely defined.

The queen of hearts is very angry because someone stole her tarts, so she is going to perform many executions. After the executions some of the creatures will lose his best friend, and will stop admiring all the creatures admired by his best friend, in consequence the number of guilds could change.

Alice have Q queries of the form L, R, and she asks you to determine the number of guilds after the executions if the only survivors are the creatures numbered from L to R.

Input
The first line of the input contains two integers N and Q.

In the next line there are N space separated integers, the i-th integer ai represents the best friend of the i-th creature.

Then follows Q lines each one with two integers L, R representing one query.

Output
For each query, output the number of guilds after the execution.

Constraints
1 ≤ N, Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ ai ≤ N

Solution:

CPP14

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

const int N = 1e5 + 10;
int a[N];

stack s;
vectoradj[N];
int lw[N],idx[N],cmp[N],counter,SCCNum;
int min_of_cmp[N];
int max_of_cmp[N];

void tarjanSCC(int v)
{
lw[v]=idx[v]=++counter;
cmp[v]=-1;
s.push(v);
int u = a[v];
if(!idx[u]||cmp[u]==-1){

    if(!idx[u])tarjanSCC(u);
    lw[v]=min(lw[v],lw[u]);
}
if(lw[v]==idx[v]){
    int x;
    do{
        x=s.top();
        s.pop();
        cmp[x]=SCCNum;
        max_of_cmp[SCCNum] = max(x,  max_of_cmp[SCCNum]);
        min_of_cmp[SCCNum] = min(x,  min_of_cmp[SCCNum]);
    }while(x!=v);

    SCCNum++;
}

}

int cnt[N];
int taken[N];
int len;

int res ;
void add(int idx, int l, int r)
{
int added = 1;
added -= cnt[idx];
if(taken[a[idx]] && !(cmp[idx] == cmp[a[idx]] && min_of_cmp[cmp[idx]] >= l && max_of_cmp[cmp[idx]] <= r))
added–;

res += added;
cnt[a[idx]]++;
taken[idx] = 1;

}
void rem(int idx, int l, int r)
{
int added = -1;
added += cnt[idx];
if(taken[a[idx]] && !(cmp[idx] == cmp[a[idx]] && min_of_cmp[cmp[idx]] >= l && max_of_cmp[cmp[idx]] <= r))
added++;
res += added;
cnt[a[idx]]–;
taken[idx] = false;
}

struct QUERY
{
int l,r, idx;
}query[N];
bool cmpare(QUERY &a, QUERY &b)
{
return make_tuple(a.l/len, a.r) < make_tuple(b.l/len, b.r);
}
int ans[N];
int main()
{
memset(cmp,-1,sizeof cmp);

int n, q;
scanf("%d %d", &n, &q);
len = sqrt(n)+1;
for(int i=0;i<n;i++)
{
    scanf("%d", a+i);
    a[i]--;
    max_of_cmp[i] = -1;
    min_of_cmp[i] = n+10;
}
for(int i=0;i<n;i++)if(!idx[i])
{
    tarjanSCC(i);
}
a[n] = -1;
for(int i=0;i<n;i++)
{
    if(a[i] == i)
        a[i] = n;
}
for(int i=0;i<q;i++)
{
    int l, r;
    scanf("%d %d", &l, &r);
    l--, r--;
    query[i] = {l, r, i};
}
sort(query, query+q, cmpare);
add(0, 0, 0);
int l=0, r = 0;
for(int i=0;i<q;i++)
{
    int ql = query[i].l;
    int qr = query[i].r;
    while(r < qr)
    {
        r++;
        add(r, l, r);
    }
    while(l > ql)
    {
        l--;
        add(l, l, r);
    }
    while(r > qr)
    {
        rem(r, l, r);
        r--;
    }
    while(l < ql)
    {
        rem(l, l, r);
        l++;
    }
    ans[query[i].idx] = res;
}
for(int i=0;i<q;i++)
    printf("%d\n",ans[i]);

}

PYTHON3.6:
def queen(n,l,r,li=[]):
setmain=[]

for index,value in enumerate(li,1):
    if(index>=l and index<=r):
        set1=[]
        if(value<=r and value>=l):
            set1.append(min(value,index))
            set1.append(max(value,index))
            if(value==index):
                try: 
                    set1.remove(index)          
                except ValueError:
                    pass
            setmain.append(set1)               
           
        else:                                   
            for g in range(0,len(setmain)):
                try:
                    if (setmain[g][0]==index or setmain[g][1]==index ):
                        pass
                    else:
                        setmain.append([(index)])
                        break
                except IndexError:
                    pass
                
                    
for m in range(0,len(setmain)):
    for n in range(m+1,len(setmain)):
        try:    
            if(setmain[m]==setmain[n]):
                setmain.remove(setmain[n])
        
            if(setmain[m][1]==setmain[n][0]):
                setmain[m].append(setmain[n][1])
                setmain.remove(setmain[n]) 
        except IndexError:
            pass

print(len(setmain))

def main():
n,t= map(int,input().split())
li = map(int,input().split())
for i in range(0,t):
l,r=map(int,input().split())
queen(n,l,r,li)

if name==‘main’:
main()