Toph - Birthday Present Tutorial
Problem Description here
এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত Intra CoU Programming Contest 2020 এর জন্য সেট করা। এই প্রব্লেম সলভ করতে যা যা জানা দরকার তা হলোঃ
Sparse Table, Segment Tree, DFS, Binary Search
প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে n সাইজের একটি ট্রি দেয়া থাকবে যার প্রতি নোডে কিছু ফুল আছে। এখন, তোমাকে q টা কুয়েরী এন্সার করতে হবে। কুয়েরী আবার দুই ধরণের হতে পারে।
১) u v x
v থেকে u এর দিকে সর্বনিম্ন কয়টা নোড ভিজিট করে কমপক্ষে x সংখ্যক ফুল কালেক্ট করা যায় তা বের করতে হবে যেখানে u হচ্ছে v এর এন্সেস্টর(পূর্বসুরী) ।
২) u y
u নোডের ফুল সংখ্যা আপডেট করতে হবে। y পজিটিভ হলে যোগ হবে, নেগেটিভ হলে বিয়োগ।
হিন্টসঃ
১) স্পার্স টেবিল ডাটা স্ট্রাকচার শিখে থাকলে এখন তুমি একটি ট্রি এর প্রতিটি নোডের জন্য এর kth প্যারেন্ট বের করতে পারবে নিশ্চয়ই! এর জন্য তোমার log(n) কমপ্লেক্সিটি লাগবে।
২) প্রব্লেমে একটা ব্যাপার লক্ষ্য করেছো কি? u সবসময় v এর এন্সেস্টর! কেন?
DFS ব্যাবহার করে একটি ট্রি এর প্রতিটি নোডের স্টার্ট টাইম আর ফিনিশিং টাইম নিশ্চয়ই বের করতে পারো। এখন একটি 2n সাইজের অ্যারে নাও। প্রতিটি নোডের স্টার্ট টাইম যতো অ্যারের ততো তম ইনডেক্সে +x রাখো, ফিনিশিং টাইম যতো অ্যারের ততো তম ইনডেক্সে -x রাখো। এখানে, x হচ্ছে ঐ নোডের ফুল সংখ্যা। এখন এই অ্যারের উপর সেগমেন্ট ট্রি বিল্ড কর।
মজার ব্যাপার লক্ষ্য করেছো কী? তা হলো, সেগমেন্ট ট্রি এর একটি কুয়েরীর মাধ্যমে log(n) কমপ্লেক্সিটি তে আমি এখন বের করতে পারবো u থেকে v তে কয়টি ফুল আছে। কীভাবে? আমাদের বিল্ড করা 2n সাইজের অ্যারের start[u] ইনডেক্স থেকে start[v] ইনডেক্স পর্যন্ত যোগফল কত তা আমি সেগমেন্ট ট্রি তে রেঞ্জ কুয়েরী করে বের করতে পারি!
বিঃদ্রঃ u এবং v এর মধ্যে এন্সেস্টর ডিসেন্ডেন্ট সম্পর্ক না থাকলে সেগমেন্ট ট্রি এর এই ট্রিক্স কাজ করবে না!
৩) এখন, প্রতিটি নোড ট্রি এর কোন লেভেলে আছে সেটাও অলরেডি DFS রান করে আমার প্রিক্যালকুলেট করা আছে যেখান থেকে আমি বলতে পারবো u , v এর কত তম প্যারেন্ট। ধরি, u হচ্ছে v এর kth প্যারেন্ট। এখন, আমি একটি বাইনারী সার্চ করে দেখবো 0th to kth এর মধ্যে কমপক্ষে v এর কততম প্যারেন্ট কে সিলেক্ট করলে v থেকে তার ঐ প্যারেন্ট পর্যন্ত কমপক্ষে x সংখ্যক ফুল থাকে?
৪) আপডেট অপারেশন নিয়ে কিছু বলা লাগবে কি? প্রতিটি নোডের ফুল সংখ্যা আপডেট করার জন্য ঐ নোডের স্টার্টিং এবং ফিনিশিং দুই ইনডেক্সের ভ্যালু ই আপডেট করা লাগবে!
আশা করি, প্রব্লেমটি নিজে নিজেই সলভ করতে পারবে। তাও, না পারলে নিচের কোড দেখতে পারো।
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define sz 400005 | |
| #define ll long long | |
| #define Input freopen("in.txt","r",stdin) | |
| #define Output freopen("out.txt","w",stdout) | |
| ll curr_tim=0,level[sz],parent[sz],st[sz],ed[sz],cost[sz],sptable[sz][35],tree[4*sz],ara[sz]; | |
| vector<ll>graph[sz]; | |
| void DFS(ll u,ll par,ll lev) | |
| { | |
| st[u] = ++curr_tim; | |
| level[u] = lev; | |
| parent[u] = par; | |
| for(auto v:graph[u]){ | |
| if(v != par) | |
| DFS(v , u , lev+1); | |
| } | |
| ed[u] = ++curr_tim; | |
| } | |
| void sparseTable(ll n) | |
| { | |
| for(ll i=1 ; i<=n ; i++) | |
| sptable[i][0] = parent[i]; | |
| for(ll j=1 ; (1<<j)<=n ; j++){ | |
| for(ll i=1 ; i<=n ; i++){ | |
| if(sptable[i][j-1] == -1) | |
| sptable[i][j] = sptable[i][j-1]; | |
| else | |
| sptable[i][j] = sptable[sptable[i][j-1]][j-1]; | |
| } | |
| } | |
| } | |
| ll kthParent(ll u,ll kth) | |
| { | |
| for(ll j=25 ; j>=0 ; j--){ | |
| if(kth >= (1<<j)){ | |
| u = sptable[u][j]; | |
| kth -= (1<<j); | |
| } | |
| } | |
| return u; | |
| } | |
| void Init(ll node,ll b,ll e) | |
| { | |
| if(b == e){ | |
| tree[node] = ara[b]; | |
| return; | |
| } | |
| ll mid = (b+e)>>1; | |
| Init(node<<1 , b , mid); | |
| Init(1+(node<<1) , mid+1 , e); | |
| tree[node] = tree[node<<1] + tree[1+(node<<1)]; | |
| } | |
| void Update(ll node,ll b,ll e,ll pos,ll val) | |
| { | |
| if(pos<b || pos>e) | |
| return; | |
| if(b==pos && e==pos){ | |
| tree[node] += val; | |
| return; | |
| } | |
| ll mid = (b+e)>>1; | |
| Update(node<<1 , b , mid , pos , val); | |
| Update(1+(node<<1) , mid+1 , e , pos , val); | |
| tree[node] = tree[node<<1] + tree[1+(node<<1)]; | |
| } | |
| ll Query(ll node,ll b,ll e,ll i,ll j) | |
| { | |
| if(j<b || i>e) | |
| return 0LL; | |
| if(b>=i && e<=j) | |
| return tree[node]; | |
| ll mid = (b+e)>>1; | |
| ll p1 = Query(node<<1 , b , mid , i , j); | |
| ll p2 = Query(1+(node<<1) , mid+1 , e , i , j); | |
| return p1+p2; | |
| } | |
| ll BS(ll u,ll v,ll x,ll n) | |
| { | |
| ll lo=0,hi=level[v]-level[u],mid,res=-1; | |
| while(lo <= hi){ | |
| mid = (lo+hi)>>1; | |
| ll node = kthParent(v , mid); | |
| if(Query(1 , 1 , 2*n , st[node] , st[v]) >= x){ | |
| res = mid+1; | |
| hi = mid-1; | |
| } | |
| else | |
| lo = mid+1; | |
| } | |
| return res; | |
| } | |
| int main() | |
| { | |
| // Input; | |
| // Output; | |
| ll i,j,k,n,q,u,v,x,qtype,ans; | |
| cin>>n>>q; | |
| for(i=1 ; i<n ; i++){ | |
| cin>>u>>v; | |
| graph[u].push_back(v); | |
| graph[v].push_back(u); | |
| } | |
| DFS(1 , -1 , 1); | |
| sparseTable(n); | |
| for(i=1 ; i<=n ; i++){ | |
| cin>>cost[i]; | |
| ara[st[i]] = cost[i]; | |
| ara[ed[i]] = -cost[i]; | |
| } | |
| Init(1 , 1 , 2*n); | |
| for(i=1 ; i<=q ; i++){ | |
| cin>>qtype; | |
| if(qtype == 1){ | |
| cin>>u>>v>>x; | |
| if(level[u] > level[v]) | |
| swap(u , v); | |
| ans = BS(u , v , x , n); | |
| cout<<ans<<endl; | |
| } | |
| else{ | |
| cin>>u>>x; | |
| Update(1 , 1 , 2*n , st[u] , x); | |
| Update(1 , 1 , 2*n , ed[u] , -x); | |
| } | |
| } | |
| return 0; | |
| } |
Comments
Post a Comment