**Distinct Colors Solved(DFS TREE +MO)

Distinct Colors

MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

You are given a tree with N vertices rooted at 1. You consider all the N subtrees (rooted at 1,2..N such that subtree rooted at i consists of i and all nodes which contain i as an ancestor).

Each node in the graph also consists of a color. The colors can be between 1 to K.

For each subtree find the no. of distinct colours in that subtree.

Output the sum of all these N numbers.

Input

First line of input contains 2 integers N,K.

Next N-1 lines (from line 2 to line N) contain 1 integer each. (i + 1) ^th line contains the parent of i+2 and is guaranteed to be lesser than i+2. 1 is the root of the tree. 

Next line contains N integers , each from 1 to K representing the colors of each node. 

Output

Single integer corresponding to the required answer.

Constraints

1 <= N <= 10⁵

1 <= K <= 10⁵

Example

Input:
3 4
1
1
1 2 3

Output:
5

Explanation

The 3 subtrees are [1,2,3] , [2], [3] , which have 3,1,1 distinct colours respectively. So the answer is 5.

---------------------------------------------------------------EDITORIAL-----------------------------------------------------------------------------

 A SUBTREE CONTAINS ALL ITS CHILDRENS SO WE CAN MAKE IT IN 1 D ARRAY , IF WE CREATE DFS TREE THAN WE CAN FIND ALL NODES WHICH COMES UNDER A NODE , NOW FOR EACH NODE A SET OF NODES FROM L TO R (ACCORDING TO ITS DFS TIME )  COMES AND WE HAVE TO COUNT NO OF DISTINCT COLOR FROM L TO R , 

SO FOR EACH NODE AS A  ROOT NODE THERE EXISTS Li TO Ri NODES (ACCORDING TO DFS  TREE ) 

SO WE NEED TO APPLY N QUERY OF FORM Li TO Ri AND IN EACH QUERY COUNT NO OF DISTINCT COLOR IN Li TO Ri , WHICH CAN BE DONE USING MO ALGORITHM .........

-------------------------------------------------------------------------CODE----------------------------------------------------------------------

#include<iostream>
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
bool visited[200010];
list<int> arr[200010];
int a[200010];
int sttime[200010];
int endtime[200010];
int tree[200010];
int vis=0;
int color[200010];
int bck_sz=447;
int has[1000000];
long long int fans=0;
long long int  ans=0;
struct node{
int   x;
int  y;

// idx;
} brr[200010];
bool cmp(node a,node b)
{
    long long  i,j;
    i=a.x/bck_sz;
    j=b.x/bck_sz;
    if(i==j)
    {
        if(a.y<b.y)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}

void add(int n)
{
   if(has[n]==0)
   {
    has[n]++;
    ans++;
} 
else has[n]++;

}

void del(long long  n)
{
if(has[n]==1) ans--;
    if(has[n]>0)
   {
    has[n]--;
   
} 
}

void dfs(int st)
{
   list<int> ::iterator it;
   tree[vis]=color[st];  
   sttime[st]=vis;
   visited[st]=1;
   for( it=arr[st].begin();it!=arr[st].end();it++)
   {
    if(visited[*it]==0)
    {
        vis++;
visited[*it]=1;  
dfs(*it);
 
   }
   }
 //  cout<<"enfing "<<st<<" with "<<vis<<endl;
   endtime[st]=vis;
}

int main()
{
int n,k;
cin>>n>>k;
for(int i=2;i<=n;i++)
{
        cin>>a[i];
        arr[a[i]].push_back(i);
}
for(int i=1;i<=n;i++)
cin>>color[i];
dfs(1);

//for(int i=0;i<=vis;i++) cout<<tree[i]<<" ";
// cout<<endl;
// cout<<"ese"<<endl;
//for(int i=1;i<=n;i++) cout<<sttime[i]<<" "<<endtime[i]<<endl;;
//cout<<endl;
for(int i=1;i<=n;i++)
{
brr[i-1].x= sttime[i];
brr[i-1].y=endtime[i];
}
sort(brr,brr+n,cmp);
// cout<<"clrs "<<endl;
// for(int i=1;i<=n;i++) cout<<color[i]<<" ";
long long int l=0,r=-1;
for(int i=0;i<n;i++)
{
    int x=brr[i].x;
   int  y=brr[i].y;
  // x++;
  // y++;
// cout<<"range "<<x<<" "<<y<<endl;
  // cout<<x<<" query "<<y<<endl;
    while(r<y)
    {

        r++;
       // cout<<"r "<<r<<endl;
      // cout<<"adding"
        add(tree[r]);
    }
    while(l>x)
    {
        l--;
        add(tree[l]);
    }
    while(l<x)
    {
        del(tree[l]);
        l++;
    }
    while(r>y)
    {
        del(tree[r]);
        r--;
    }
  //cout<<"ans of this range "<<ans<<endl;
fans+=ans;
}
cout<<fans<<endl;
 

}

-------------------------------------------------------------this problrm can also solve by using set on each node  and merge nodes from child to calculate for each node but for ac in given time we need to do a simple observation  maximum no of copy is used for a linear tree which is very high soo  for all node for its first child just replase it with its parent and for rest child copy so in case of linear tree no of copy used =0;
----------------------------------------code---------------------------------------------------------------------------------------------------------

1. #include "bits/stdc++.h"
2. using namespace std;
3. const int N = 1e5 + 5;
4. int n , k;
5. vector < int > v[N];
6. int col[N];
7. int ans[N];
8. set < int > s[N];
9. int baap;
10. long long sum = 0;
11. void dfs(int node){
12. int idx = -1;
13. for(int x : v[node]){
14. dfs(x);
15. if(idx == -1 || s[x].size() > s[idx].size()){
16. idx = x;
17. }
18. }
19. if(idx != -1){
20. s[node].swap(s[idx]);
21. }
22. s[node].insert(col[node]);
23. for(int x : v[node]){
24. if(x != idx){
25. s[node].insert(s[x].begin() , s[x].end());
26. }
27. }
28. sum += s[node].size();
29. }
30. int main(){
31. scanf("%d %d" , &n , &k);
32. for(int i = 2 ; i <= n ; ++i){
33. scanf("%d" , &baap);
34. v[baap].emplace_back(i);
35. }
36. for(int i = 1 ; i <= n ; ++i){
37. scanf("%d" , col + i);
38. }
39. dfs(1);
40. printf("%lld\n" , sum);
41. }

KQUERY -K-query

KQUERY -K-query 

no tags 

English

Vietnamese

Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
• Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
• In the next q lines, each line contains 3 numbers i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).

Output

• For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj in a single line.

Example

Input
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 

Output
2
0
3 

 Submit solution!

---

hide comments

-----------------------------------------------------code------------------------------------------------------------------

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; int readInt () { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result*10 + (ch - '0'); } if (minus) return -result; else return result; } typedef int lli; typedef tree< pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ordered_set st; // int ans=*st.find_by_order(n); // int a=st.order_of_key(n); const int bck_sz=448; int ix=0; struct node { lli x,y,idx; }; node q[200005]; int a[30005]; int re[200005]; bool cmp(node a,node b) { lli i,j; i=a.x/bck_sz; j=b.x/bck_sz; if(i==j) { if(a.y<b.y) return 1; else return 0; } else{ if(i<j) return 1; else return 0; } } int val; void add(int n) { // cout<<"insert "<<n<<endl; st.insert({n,ix++}); } void removex(int n) { // cout<<"delete "<<n<<endl; st.erase(st.lower_bound({n,0})); } int rx[30005]; int main() { int i,j,k,n,m; n=readInt (); for(i=0;i<n;i++) a[i]=readInt (); m=readInt (); for(i=0;i<m;i++) { int x,y; x=readInt (); y=readInt (); k=readInt (); rx[i]=k; x--; y--; // cout<<x<<" "<<y<<endl; q[i].x=x; q[i].y=y; q[i].idx=i; } sort(q,q+m,cmp); int l=0,r=-1; for(i=0;i<m;i++) { int lf=q[i].x; int rf=q[i].y; int idx=q[i].idx; val=rx[idx]; // cout<<lf<<" query "<<rf<<endl; while(r<rf) { r++; // cout<<"rr "<<r<<endl; // cout<<"a[r] "<<a[r]<<endl; add(a[r]); } while(r>rf) { removex(a[r]); r--; } while(l<lf) { removex(a[l]); l++; } while(l>lf) { l--; add(a[l]); } // cout<<"query "<<lf<<" "<<rf<<endl; // int ans=*st.find_by_order(val); int ar=st.order_of_key({val+1,0}); // cout<<"find by order "<<ans<<" order by key "<<ar<<endl; /*for(auto it=st.begin();it!=st.end();it++) { // cout<<it->first<<endl; } */ if(st.size() && st.lower_bound({(val+1),0})!=st.end()) { //cout<<"order "; // cout<<ar<<endl; re[idx]=st.size()-ar; } } for(i=0;i<m;i++) printf("%d\n",re[i]); return 0; }

SUBSTRINGS COUNT

SUBSTRINGS COUNT

 Submissions

Attempted by: 497

|

Solved by: 60

|

Partially Solved by: 353

|

---

 

• Algorithms
• Binary Search
• Data Structures
• Hashing
• Medium

  Edit

Problem

Editorial

My Submissions

Analytics

 The Big Bang Challenge

Jack is the most intelligent student in the class.To boost his intelligence,his class teacher gave him a problem named"Substring Count".

Problem :
His Class teacher gave him n strings numbered from 1 to n which consists of only lowercase letters (each having length not more than 10) and then ask Q questions related to the given strings.

Each question is described by the 2 integers L,R and a string str,Now his teacher wants to know how many strings numbered from L to R contains str as a substrings.

As expected, Jack solved this problem with in a minute but he failed to solve it efficiently.Now ,its your turn to teach him.How to do it efficiently?? and save him from punishment.

INPUT
First line of input contains a single integer n denoting the number of strings given by class teacher to jack.Next n lines of input contains n strings (one per line).Next line fo input contains a single integer Q denoting the number of questions asked by his teacher.next Q lines of input contains Q question (one per line) as explained above.

OUTPUT
print the correct answer for each of the question asked by his teacher.

CONSTRAINTS
1<=n<=10000
1<=strlen(str)<=10
1<=Q<=5*10^5
1<=L,R<=n

NOTE: strings consist of only lower case characters

---

Sample Input

(Plaintext Link)

3
code
coder
coding
2
1 3 code
1 3 co

Sample Output

(Plaintext Link)

2 
3

Explanation

Q1:: code coder coding only two out of 3 strings contain cod as substring Q2:: code coder coding all the 3 strings contain co as substring

-------------------------------------CODE-----------------------------------------------------------------------------------------------------

GENERATE ALL POSSIBLE SUB STRING OF ALL STRING WHICH CAN BE DONE IN N*45(SINCE LENGTH OF EACH STRING =10 SO 45 SUBSTRINGS IN EACH STRING )

NOW WE  WHENE WE ARE  ADDING ANY INDEX , INCREASE HAS COUNT OF ALL SUBSTRING AT THAT THAT CAN BE FORMED BY STRING AT THAT INDEX (ALL SUBSTRINGS ) ,SIMILARLY FOR DELETE , 

-----------------------------------------------------CODE-----------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
//map<map<string,int> > ma;
string ss[1000000];
typedef int lli;
int result[1000005];
vector<string>v[1000005];
struct node
 {
   lli x,y,index;
   string str;
   
 } qry[1000000];

 map<string,int> has;
 long long int ans=0;

  lli bck_sz=555;
  
  lli read_int()
  {
 char r;
 bool start=false,neg=false;
  lli ret=0;
 while(true){
  r=getchar();
  if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
   continue;
  }
  if((r-'0'<0 || r-'0'>9) && r!='-' && start){
   break;
  }
  if(start)ret*=10;
  start=true;
  if(r=='-')neg=true;
  else ret+=r-'0';
 }
 if(!neg)
  return ret;
 else
  return -ret;
}

bool compare(node a,node b)
{
    lli i,j;
    i=a.x/bck_sz;
    j=b.x/bck_sz;
    if(i==j)
    {
        if(a.y<b.y)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}

int join(int index)
{
int l=v[index].size();
for(int i=0;i<l;i++)
has[v[index][i]]++;
}

int del(int index)
{
int l=v[index].size();
for(int i=0;i<l;i++)
has[v[index][i]]--;
}



int main()
 {
 int n;
 cin>>n;
 for(int i=0;i<n;i++)
  {
  string s;
  cin>>ss[i];
  int len=ss[i].length();
  map<string,int> mp;
  for(int k=0;k<len;k++)
  {
  string p;
 
  for(int j=k;j<len;j++)
   {
    p+=ss[i][j];
    if(!mp[p])
    v[i].push_back(p);
    mp[p]++;
   
}
  }
  mp.clear();
  
 
 
 }
 
 
 
 
 int q;
 cin>>q;
 for(int i=0;i<q;i++)
  {
    int a,b;
    string s;
     cin>>a>>b;
      cin>>s;
     qry[i].x=a-1;
     qry[i].y=b-1;
     qry[i].index=i;
      qry[i].str=s;
     
  }
  sort(qry,qry+q,compare);
  
 int  r=-1;
int  l=0;
for(int  i=0;i<q;i++)
 {
  int  x=qry[i].x;
               int  y=qry[i].y;
               int  index=qry[i].index;
               string s=qry[i].str;
               // cout<<" query in the range "<<x<<" "<<y<<endl;
                        
                    while(r<y)
                              {

                                  r++;
                           
                                    join(r);
                          }
                          
              while(l>x)
                {
                   l--;
                  join(l);
                  }
    while(l<x)
    {
        del(l);
        l++;
    }
    while(r>y)
    {
        del(r);
        r--;
    }
    
    result[index]=has[s];
   
 }
 
 for(lli i=0;i<q;i++)
   printf("%lld\n",result[i]);
   
}