博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ3295:[CQOI2011]动态逆序对——题解
阅读量:6808 次
发布时间:2019-06-26

本文共 2081 字,大约阅读时间需要 6 分钟。

Description

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。

Output

输出包含m行,依次为删除每个元素之前,逆序对的个数。

Sample Input

 

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5

2
2
1

——————————————————————————————

这题不开longlong成功见祖宗……

乍一看我们想不到,但是显然删除操作不好整,我们将删除变成插入,插入的时间点为t,插入的位置为p,插入的值为n。

则三元组(t,p,n)它的逆序对需要满足t0<t,p0<p,n0>n或者t0<t,p0>p,n0<n

这不就成三维偏序了吗?解完之后求一遍前缀和即是答案。

#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;const int N=100001;inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct del{ int t; int p; int n;}q[N],tmp[N];ll m,n,ans[N],pos[N],tree[N];inline int lowbit(int t){ return t&(-t);}void add(int x,int y){ //将a[x]+y for(int i=x;i<=n;i+=lowbit(i))tree[i]+=y; return;}ll query(int x){ //1-x区间和 ll res=0; for(int i=x;i>0;i-=lowbit(i))res+=tree[i]; return res;}void cdq(int l,int r){ if(l>=r)return; int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); for(int i=l,j=l,p=mid+1;i<=r;i++){ if(j<=mid&&(p>r||q[j].n>q[p].n))tmp[i]=q[j++]; else tmp[i]=q[p++]; } for(int i=l;i<=r;i++){ q[i]=tmp[i]; if(q[i].t<=mid)add(q[i].p,1); else ans[q[i].t]+=query(q[i].p); } for(int i=l;i<=r;i++)if(q[i].t<=mid)add(q[i].p,-1); for(int i=r;i>=l;i--){ if(q[i].t<=mid)add(q[i].p,1); else ans[q[i].t]+=query(n)-query(q[i].p); } for(int i=l;i<=r;i++)if(q[i].t<=mid)add(q[i].p,-1); return;}bool vis[N];int main(){ n=read(); m=read(); for(int i=1;i<=n;i++)pos[read()]=i; for(int i=n;i>=n-m+1;i--){ q[i].t=i; q[i].n=read(); q[i].p=pos[q[i].n]; vis[q[i].n]=1; } int cnt=n-m; for(int i=1;i<=n;i++){ if(!vis[i]){ q[cnt].t=cnt; q[cnt].n=i; q[cnt--].p=pos[i]; } } cdq(1,n); for(int i=1;i<=n;i++)ans[i]+=ans[i-1]; for(int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]); return 0;}

转载于:https://www.cnblogs.com/luyouqi233/p/8044201.html

你可能感兴趣的文章
判断当前进程是否以管理员权限启动的
查看>>
Javascript交互式金融股票基金图表JavaScript Stock Chart
查看>>
bootstrap-徽章-链接
查看>>
SQL-26 (二次分组)汇总各个部门当前员工的title类型的分配数目,结果给出部门编号dept_no、dept_name、其当前员工所有的title以及该类型title对应的数目count...
查看>>
SQL-55 分页查询employees表,每5行一页,返回第2页的数据
查看>>
DB2 心态
查看>>
Android实现仿IOS带清空功能的文本输入框
查看>>
轻松玩转windows7之一:利用无线玩转虚拟网络
查看>>
:layout_gravity gravity
查看>>
POJ 2478:Farey Sequence
查看>>
linux 心得
查看>>
线上应用故障排查之一:高CPU占用
查看>>
编写差异更新脚本
查看>>
CentOS 6.4下Squid代理服务器的安装与配置
查看>>
CentOS 6.5安装YouCompleteMe使用vim C/C++语法自动补全
查看>>
利用php利用root权限执行shell脚本必须进行以下几个步骤
查看>>
Storm原理及单机安装指南
查看>>
Linux一些有用的操作
查看>>
IAT 注入ImportInject(dll)
查看>>
[C++]面向对象部分——类
查看>>