Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <map>
- #include <stack>
- using namespace std;
- using namespace std;
- const int maxn=350005;
- int n;
- vector<int>g[maxn];
- bool vis[maxn];
- vector<int>v;
- int st[3*maxn];
- void btree(int L,int R,int pos)
- {
- if(L==R)
- {
- st[pos]=0;
- return ;
- }
- int mid=(L+R)/2;
- btree(L,mid,2*pos);
- btree(mid+1,R,2*pos+1);
- st[pos]=st[2*pos]+st[2*pos+1];
- }
- void u(int L,int R,int idx,int pos)
- {
- if(L==R)
- {
- st[pos]=1;
- return ;
- }
- int mid=(L+R)/2;
- if(idx<=mid)
- {
- u(L,mid,idx,2*pos);
- }
- else
- {
- u(mid+1,R,idx,2*pos+1);
- }
- st[pos]=st[2*pos]+st[2*pos+1];
- }
- int query(int L,int R,int i,int j,int pos)
- {
- //L R i L R j L R
- if(i<=L && R<=j)
- {
- return st[pos];
- }
- if(j<L || R<i)
- {
- return 0;
- }
- int mid=(L+R)/2;
- return query(L,mid,i,j,2*pos)+query(mid+1,R,i,j,2*pos+1);
- }
- void topsort(int node)
- {
- vis[node]=true;
- for(auto a:g[node])
- {
- if(!vis[a])
- {
- topsort(a);
- }
- }
- v.push_back(node);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin>>n;
- memset(vis,0,sizeof vis);
- for(int i=1;i<=n;i++)
- {
- char c;
- cin>>c;
- if(c=='K')
- {
- g[i-1].push_back(i-1);
- }
- else
- {
- int num;
- cin>>num;
- g[num-1].push_back(i-1);
- }
- }
- for(int idx=0;idx<n;idx++)
- {
- if(!vis[idx])
- {
- topsort(idx);
- }
- }
- btree(0,n,1);
- vector<pair<int,int>>ans;
- for(int i=0;i<n;i++)
- {
- u(0,n, v[i], 1);
- ans.push_back({v[i],query(0,n,0,v[i],1)});
- }
- sort(ans.begin(),ans.end());
- for(int i=0;i<n;i++)
- {
- cout<<ans[i].second<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement