题目大意:给定一个序列。每次选择一个位置,把这个位置之后全部小于等于这个数的数抽出来,排序,再插回去,求每次操作后的逆序对数

首先我们每一次操作 对于这个位置前面的数 因为排序的数与前面的数位置关系不变 所以这些数的逆序对不会变化

对于这个位置后面比这个数大的数 因为改变位置的数都比这些数小 所以这些数的逆序对不会变化

说究竟就是排序的数的逆序对数改变了 以这些数開始的逆序对没有了

于是就好办了 我们用树状数组统计出以每一个数開始的逆序对数 然后以原数的大小为keyword建立线段树 维护区间最小值

对于每一个询问p,我们取出[p,n]中的最小值a[x]。将a[x]清为正无穷。把以a[x]开头的逆序对减掉,继续找,直到a[p]为正无穷为止

每一个数仅仅会被找到1次 所以均摊复杂度O(nlogn)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 500500
#define ls tree[p].lson
#define rs tree[p].rson
using namespace std;
struct abcd{
int lson,rson;
int *num;
}tree[M<<1];int tree_tot;
int n,m,tot,a[M];
pair<int,int>b[M];
int c[M],f[M];
long long ans;
int* _min(int *x,int *y)
{
return *x>=*y?y:x;
}
void Build_Tree(int p,int x,int y)
{
int mid=x+y>>1;
if(x==y)
{
tree[p].num=a+mid;
return ;
}
ls=++tree_tot;rs=++tree_tot;
Build_Tree(ls,x,mid);
Build_Tree(rs,mid+1,y);
tree[p].num=_min(tree[ls].num,tree[rs].num);
}
int* Get_Ans(int p,int x,int y,int l,int r)
{
int mid=x+y>>1;
if(x==l&&y==r)
return tree[p].num;
if(r<=mid)
return Get_Ans(ls,x,mid,l,r);
if(l>mid)
return Get_Ans(rs,mid+1,y,l,r);
return _min( Get_Ans(ls,x,mid,l,mid) , Get_Ans(rs,mid+1,y,mid+1,r) );
}
inline void Modify(int p,int x,int y,int pos)
{
int mid=x+y>>1;
if(x==y)
return ;
if(pos<=mid)
Modify(ls,x,mid,pos);
else
Modify(rs,mid+1,y,pos);
tree[p].num=_min(tree[ls].num,tree[rs].num);
}
inline void Update(int x)
{
for(;x<=tot;x+=x&-x)
c[x]++;
}
inline int Get_Ans(int x)
{
int re=0;
for(;x;x-=x&-x)
re+=c[x];
return re;
}
int main()
{
int i,p;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&b[i].first),b[i].second=i;
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
{
if(i==1||b[i].first!=b[i-1].first)
++tot;
a[b[i].second]=tot;
}
for(i=n;i;i--)
Update(a[i]),ans+=f[i]=Get_Ans(a[i]-1);
Build_Tree(0,1,n);
printf("%lld\n",ans);
for(i=1;i<=m;i++)
{
int *temp;
scanf("%d",&p);
if(a[p]!=0x3f3f3f3f)
do{
temp=Get_Ans(0,1,n,p,n);
ans-=f[temp-a];
*temp=0x3f3f3f3f;
Modify(0,1,n,temp-a);
}while(temp!=a+p);
printf("%lld\n",ans);
}
}

最新文章

  1. Android编码规范05
  2. connect to https://dl-ssl.google.com refused
  3. 初识Groovy
  4. jquery页面刷新reload
  5. ansible playbook最佳实践
  6. Dozer应用——类之间值的映射
  7. Oracle中错误代码ORA-02292 违反了完整性约束条件解决
  8. Properties集合
  9. vs2012 asp调试设置 清单目录
  10. OpenID Connect:OAuth 2.0协议之上的简单身份层
  11. IaaS,PaaS,SaaS 的区别(转)
  12. Unity3D外包 团队更新一下UE4和Unity3D案例
  13. Build a Machine Learning Portfolio(构建机器学习投资组合)
  14. PAT (Advanced Level) Practise 1003 解题报告
  15. 解决 windows下安装Anaconda后python pip不可用的情况
  16. Spring MVC开启注解
  17. 小明A+B
  18. (二)zookeeper安装
  19. C++ 第一课:预处理命令
  20. &lt;OFFER05&gt; 05_ReplaceSpaces

热门文章

  1. C#中class的访问级别
  2. AppDomain与进程、线程、Assembly之间关系
  3. OOS升级服务
  4. 对Gearman中client,worker,jobserver的理解
  5. scala 安装
  6. hadoop 异常处理实例(一)hadoop内存配置项
  7. C API向MySQL插入批量数据的快速方法——关于mysql_autocommit
  8. ExecutorService介绍
  9. C++必备知识
  10. Android网络框架Volley(体验篇)