線段樹合并都是藍題了嘛 我可能和時代脫軌了emm...

直接離散化然后合并就好啦w

生病了真難受QAQ

//Love and Freedom. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define inf 20021225 #define mxn 100010 using namespace std;struct node {int ls,rs,sum; }t[mxn*40]; int cnt,rt[mxn],ans[mxn]; struct edge {int to,lt; }e[mxn]; int val[mxn],in[mxn],ecnt; int p[mxn],dd[mxn],n;void add(int x,int y) {e[++ecnt].to=y;e[ecnt].lt=in[x];in[x]=ecnt; }void pushup(int x) {t[x].sum = t[t[x].ls].sum+t[t[x].rs].sum; }int merge(int x,int y,int l,int r) {if(!x||!y) return x+y;if(l==r){t[x].sum+=t[y].sum;return x;}int mid = (l+r)>>1;t[x].ls=merge(t[x].ls,t[y].ls,l,mid);t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r);pushup(x); return x; }void insert(int &x,int l,int r,int d) {if(!x) x=++cnt; t[x].sum++;if(l==r) return;int mid=(l+r)>>1;if(d<=mid) insert(t[x].ls,l,mid,d);else insert(t[x].rs,mid+1,r,d);pushup(x); }int query(int x,int l,int r,int d) {if(!x) return 0;if(l==r) return t[x].sum;int mid=(l+r)>>1;if(d<=mid) return query(t[x].ls,l,mid,d)+t[t[x].rs].sum;else return query(t[x].rs,mid+1,r,d); } bool cmp(int x,int y) {return val[x]<val[y]; } void dfs(int x) {for(int i=in[x];i;i=e[i].lt)dfs(e[i].to);insert(rt[x],1,n+1,p[x]);// int tmp = ;for(int i=in[x];i;i=e[i].lt)rt[x]=merge(rt[x],rt[e[i].to],1,n+1);ans[x] = query(rt[x],1,n+1,p[x]+1); } int main() {int f;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&val[i]),dd[i]=i;sort(dd+1,dd+n+1,cmp);for(int i=1;i<=n;i++) p[dd[i]]=i;for(int i=2;i<=n;i++){scanf("%d",&f);add(f,i);}dfs(1);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; }

?

轉載于:https://www.cnblogs.com/hanyuweining/p/10321877.html

總結

以上是生活随笔為你收集整理的洛谷3605 Promotion Counting的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。