Help Required CSES Distinct Colors

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello guys,

I was trying to solve Distinct Colors: link.

I did a naive solution which obviously led to TLE.

TLE

vector<VII> adj(2e5);
map<int, VII> col;
VII sub(2e5, 0);
VII ind(2e5, 0);
VII v(2e5);
int t = 1;
int dfs(int u,int p)
{
    for(auto it:adj[u])
    if(it!=p)
        sub[u] += dfs(it, u);
    
 
    ind[u] = t++;
    col[v[u]].pb(ind[u]);
    sub[u]++;
    return sub[u];
}
int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n;++i)
        cin >> v[i];
 
    for (int i = 0; i < n - 1;++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
 
    dfs(1, -1);
    for (int i = 1; i <= n;++i)
    {
        int l = ind[i] - sub[i] + 1;
        int r = ind[i];
        int ans = 0;
        for(auto c:col)
        {
            auto lll = lower_bound(all(c.second), l);
            auto rr = upper_bound(all(c.second), r);
            if(rr-lll>=1)
                ans++;
        }
        cout << ans << ' ';
    }
    return 0;
}

I saw various solutions that use BIT. But I cant assimilate why BIT works here, what BIT represents here (for e.g. in case range sum query BIT keeps track of cummulative frequency.)

It would be great if someone tells some trick how to use BIT for various other purposes too.

Thanks!

Комментарии (11)

Показать архивные | Написать комментарий?

LanceTheDragonTrainer

4 года назад, # |

It's simple. Simply transform your tree into an array by doing a pre-order traversal. Then, notice that a subtree corresponds to a subarray. Now, you just need to solve the problem of finding the number of distinct elements in a subarray (which is actually SPOJ DQUERY).

→ Ответить

retr0coderxyz

4 года назад, # ^ |

← Rev. 2 →

Thanks buddy, I have done till subarray part. epitome of this question lies around finding distinct numbers within range ( which I have used map and binary search to check here). So I need help in that part.

There are several ways to solve the problem for the array version.

The most straightforward is to use Mo's algo.

Since you asked for fenwick tree solution specifically, I shall tell you something — it is not so straightforward (you need a clever trick).

Segment tree with a vector in each node provides you with a much more straightforward solution.

Can you elaborate on the segment tree part, Thanks — noob here :(

Hint: (Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity.

Actually, you can also solve this without flattening the tree. But that's a bit advanced for now...

tihsrah_1177

LanceTheDragonTrainer Can you please explain how we can solve this without flattening the tree

CoderAnshu

using dsu on trees (sack) ,You can take help from here : https://mirror.codeforces.com/blog/entry/44351

nishuz

You can solve with small to large merging.

Code

LanceTheDragonTrainer gave some valuable insights, but still its not enough for me to pick up. I honestly don't understand "(Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity." works or what to do after that. It will be great if anybody could explain me in a well detailed manner out of your busy time, I would be really grateful.

Thank you!

Everule

Notice that each distinct color will have only one index where the value of next_element is larger than your right end.

Блог пользователя retr0coderxyz