bzoj3295 [Cqoi2011]动态逆序对 cdq+树状数组
2024-09-03 16:05:24
【bzoj3295】[Cqoi2011]动态逆序对
2014年6月17日4,7954
Description
对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。
Output
输出包含m行,依次为删除每个元素之前,逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=100000 M<=50000
题解:
这道动态逆序对问题和普通逆序对问题有什么区别,发现动态逆序对的每个值还有一个时间影响
普通逆序对只有两个元素是二维偏序问题,一维是位置,一维是键值。
而这里就是三维偏序问题,我们应该怎么来安排可以最方便呢?
我是这样安排的,a,b,c分别表示时间,位置,键值,分别排序+cdq+树状数组,这样来搞
在对于键值中,有点技巧,应为位置可能在前或者在后面,所以两次树状数组维护才行。
最后用前缀和的思想。
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio> #define N 100007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,tr[N];
long long ans[N];
struct Node
{
int a,b,c,ans;
}a[N]; bool cmp1(Node x,Node y)
{
if (x.a==y.a&&x.b==y.b) return x.c>y.c;
if (x.a==y.a) return x.b<y.b;
return x.a<y.a;
}
bool cmp2(Node x,Node y)
{
return x.b<y.b;
}
bool cmp3(Node x,Node y)
{
return x.b>y.b;
}
int lowbit(int x){return x&(-x);}
void update(int x,int num)
{
for (int i=x;i<=n;i+=lowbit(i))
tr[i]+=num;
}
int query(int x)
{
int res=;
for (int i=x;i>=;i-=lowbit(i))
res+=tr[i];
return res;
}
void cdq(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>;
cdq(l,mid);
cdq(mid+,r);
sort(a+l,a+mid+,cmp2);
sort(a+mid+,a+r+,cmp2);
int i=l,j=mid+;
while(j<=r)
{
while(i<=mid&&a[i].b<a[j].b)
update(a[i].c,),i++;
a[j].ans+=query(n)-query(a[j].c),j++;
}
for (int j=l;j<i;j++)
update(a[j].c,-); sort(a+l,a+mid+,cmp3);
sort(a+mid+,a+r+,cmp3);
i=l,j=mid+;
while(j<=r)
{
while(i<=mid&&a[i].b>a[j].b)
update(a[i].c,),i++;
a[j].ans+=query(a[j].c),j++;
}
for (int j=l;j<i;j++)
update(a[j].c,-);
}
int main()
{
n=read(),m=read();
for (int i=;i<=n;i++){int x=read();a[x].b=i;}
for (int i=;i<=m;i++){int x=read();a[x].a=m-i+;}//倒着表示什么时候插入
for (int i=;i<=n;i++)a[i].c=i;
sort(a+,a+n+,cmp1);
cdq(,n);
for (int i=;i<=n;i++)
ans[a[i].a]+=a[i].ans;
for (int i=;i<=m;i++)
ans[i]+=ans[i-];
for (int i=m;i>=;i--)
printf("%lld\n",ans[i]);
}
最新文章
- C++指针和动态内存分配
- PHP_Bibel阅读笔记(二)——脸黑的一天(?一年)
- java应用死循环排查方法或查找程序消耗资源的线程方法(面试)
- (Beta)Let&#39;s-Beta阶段展示博客
- [LeetCod] Single Number
- POJ 2763 Housewife Wind (树链剖分 有修改单边权)
- Arduino 入门程序示例之一片 LED(2015-06-11)
- 【剑指offer】数字数组中只出现一次(2)
- Claris and XOR(模拟)
- rowid去重(删除表的重复记录)
- LeetCode 599. Minimum Index Sum of Two Lists (从两个lists里找到相同的并且位置总和最靠前的)
- C算法实现:将字符串中的数字返回为整型数
- 设计模式九: 观察者模式(Observer Pattern)
- JavaScript之Number、String、Array常用属性与方法手册
- Java中的IO流总结
- POJ2676 Sudoku 舞蹈链 DLX
- IDEA创建SpringBoot项目
- 一个神奇的???whatever~~
- go web framework gin 启动流程分析
- 【日常开发】使用多种工具实现 sql查询没有结果的name
热门文章
- HDFS执行getDatanodeReport时权限不足的解决办法
- Android偏好设置(2)为应用定义一个偏好设置xml
- MAT使用入门
- 转】SparkSQL中的内置函数
- .net 字符串和JSON格式的互换
- 直接插入排序法原理及其js实现
- Android习惯--Activity启动方法
- Request.Form(";id";)与Request.QueryString(";id";)的区别
- struts2通过配置文件进行数据校验无效
- Go语言 之md5加密