# 星星灰暗着。

### 题解 P3605 【[USACO17JAN]Promotion Counting晋升者计数】

posted on 2018-06-13 22:01:04 | under 题解 |

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<tr1/unordered_map>
#define neko 100010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
typedef int arr[neko];
int L[neko*20],R[neko*20],Sum[neko*20],rt[neko*20];
int t,cnt,n;
std::tr1::unordered_map<int,int>mp;
struct OK
{int val,id;}a[neko];
bool cmp(OK x,OK y)
{return x.val<y.val;}
bool cmp2(OK x,OK y)
{return x.id<y.id;}
struct node
{
int v,nex;
}e[neko<<1];
{
e[++t].v=y;
}
namespace Pst_Tree
{
#define mid ((l+r)>>1)
#define lson L[root],l,mid
#define rson R[root],mid+1,r
void pushup(int root)
{Sum[root]=Sum[L[root]]+Sum[R[root]];}
void update(int &root,int l,int r,int x)
{
if(!root)root=++cnt;
if(l==r){++Sum[root];return;}
if(x<=mid)update(lson,x);
else update(rson,x);
pushup(root);
}
int query(int root,int l,int r,int tagl,int tagr)
{
if(l>=tagl&&r<=tagr)return Sum[root];
int tmp=0;
if(tagl<=mid)tmp+=query(lson,tagl,tagr);
if(tagr>mid)tmp+=query(rson,tagl,tagr);
return tmp;
}
int merge(int x,int y)
{
if((!x)||(!y))return x+y;
L[x]=merge(L[x],L[y]);
R[x]=merge(R[x],R[y]);
pushup(x);
return x;
}
}
using namespace Pst_Tree;
void dfs(int u,int fa)
{
travel(i,u,v)if(v!=fa)dfs(v,u),rt[u]=merge(rt[u],rt[v]);
ans[u]=query(rt[u],1,n,mp[a[u].val]+1,n);
}
int main()
{
using namespace std;
int x;
scanf("%d",&n);
f(i,1,n)scanf("%d",&a[i].val),a[i].id=i;
sort(a+1,a+n+1,cmp);
f(i,1,n)if(!mp[a[i].val])mp[a[i].val]=i;
sort(a+1,a+n+1,cmp2);
}