之前一道求逆序的线段树模板
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct node
{
int l,r;
node * pl, * pr;
int count;
}mem[200];
int mem_pos;
int anti, n, ans[200], num[200];
node * root;
![](/Images/OutliningIndicators/None.gif)
node * new_node()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
node * pt = &mem[mem_pos ++];
memset(pt,0,sizeof(node));
return pt;
}
![](/Images/OutliningIndicators/None.gif)
node * make_tree(int il, int ir,bool flag)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
node * root = new_node();
root ->l = il;
root ->r = ir;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(flag)
{
root ->count = ir - il+1;
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(il != ir)
{
int mid = (il+ir)/2;
root ->pl = make_tree(il, mid,flag);
root ->pr = make_tree(mid+1, ir,flag);
}
return root;
}
![](/Images/OutliningIndicators/None.gif)
int find(node * root, int num)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
root ->count --;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(root ->l == root ->r)
{
return root ->l;
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(root ->pl ->count > num)
{//left
return find(root ->pl, num);
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{//right
return find(root ->pr, num - root ->pl ->count);
}
}
![](/Images/OutliningIndicators/None.gif)
void update(node * root, int num)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
root ->count ++;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(root ->l == num && root ->r == num)
{
return ;
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(root ->pl ->r >= num)
{//left
anti += root ->pr ->count;
update(root ->pl, num);
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{//right
update(root ->pr, num);
}
}
![](/Images/OutliningIndicators/None.gif)
void cal_P()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1;i<=n;i++)
{
anti = 0;
update(root, num[i]);
ans[ num[i] ] = anti;
}
}
![](/Images/OutliningIndicators/None.gif)
void cal_I()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1;i<=n;i++)
{
ans[ find(root, num[i]) ] = i;
}
}
![](/Images/OutliningIndicators/None.gif)
原文地址:https://www.cnblogs.com/SQL/p/912730.html