BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 6912  Solved: 2438

[Submit][Status][Discuss]

Description

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删

除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数

Input

输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。

以下n行每行包含一个1到n之间的正整数,即初始排列。

以下m行每行一个正整数,依次为每次删除的元素。

N<=100000 M<=50000

Output

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

Sample Input

5 4 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)。

HINT

Source

这题已知有三种做法:

1、主席树+树状数组

2、树套树随便套

3、cdq分治

用cdq分治的话有一种非常巧妙的思路:先时间倒流,那么每次询问就转化成了求逆序对的个数

其实也不用。。

我们考虑一个数删除之后会对答案产生怎样的贡献

设当前删除了第$i$个元素,那么在$1 - i$中比它大的都要减去

在$(i + 1) - N$中比他小的都要减去

这样的话直接正着循环一遍再倒着循环一遍就行了。

用树状数组求逆序对

代码借鉴的candy大佬,写的非常妙

#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN = 400001, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
struct Query {
    int t, x, val, type, id;
    bool operator < (const Query &rhs) const {
        return x == rhs.x ? val < rhs.val : x < rhs.x;
    }
}Q[MAXN], Tp[MAXN];
int N, M, a[MAXN], pos[MAXN], tim;
LL ans[MAXN];

#define lb(x) (x & -x)
int T[MAXN];
void Add(int pos, int val) {for(int i = pos; i <= N; i += lb(i)) T[i] += val;}
int Sum(int pos) {int ans = 0; for(int i = pos; i >= 1; i -= lb(i)) ans += T[i]; return ans;}

void CDQ(int l, int r) {
    if(l == r) return;
    int mid = l + r >> 1;
    for(int i = l; i <= r; i++) 
        if(Q[i].t <= mid) Add(Q[i].val, Q[i].type);
        else ans[Q[i].id] += Q[i].type * (Sum(N) - Sum(Q[i].val));
    for(int i = l; i <= r; i++) if(Q[i].t <= mid) Add(Q[i].val, -Q[i].type);
    
    for(int i = r; i >= l; i--) 
        if(Q[i].t <= mid) Add(Q[i].val, Q[i].type);
        else ans[Q[i].id] += Q[i].type * (Sum(Q[i].val - 1));
    for(int i = l; i <= r; i++)if(Q[i].t <= mid) Add(Q[i].val, -Q[i].type);
    
    int p1 = l, p2 = mid + 1;
    for(int i = l; i <= r; i++)
        if(Q[i].t <= mid) Tp[p1++] = Q[i];
        else Tp[p2++] = Q[i];
    for(int i = l; i <= r; i++) Q[i] = Tp[i];
    CDQ(l, mid); CDQ(mid + 1, r);
}
int main() {
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    N = read(); M = read();
    for(int i = 1; i <= N; i++) {
        a[i] = read(); pos[a[i]] = i ;
        Q[++tim] = (Query) {tim, i, a[i], 1, 0};
    }
    for(int i = 1; i <= M; i++) {
        int x = read();
        Q[++tim] = (Query) {tim, pos[x], x, -1, i};
    }
    sort(Q + 1, Q + tim + 1);
    CDQ(1, tim);
    for(int i = 1; i <= M; i++) {
        ans[i] += ans[i - 1];
        printf("%lld\n", ans[i - 1]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Oozie分布式工作流——EL表达式

oozie支持使用EL(expression language)表达式。 基本的EL常量 KB MB GB TB PB 基本EL函数 string fir...

27780
来自专栏二进制文集

LeetCode 473 Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchstic...

12230
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

14820
来自专栏牛肉圆粉不加葱

[6] - 类和对象之进阶(二)

Scala 中的可见性非常灵活且复杂,这篇文章希望通过大量的示例来说清楚各种情况下的可见性是怎么样的。

7520
来自专栏函数式编程语言及工具

Scalaz(56)- scalaz-stream: fs2-安全运算,fs2 resource safety

    fs2在处理异常及资源使用安全方面也有比较大的改善。fs2 Stream可以有几种方式自行引发异常:直接以函数式方式用fail来引发异常、在纯代码里隐式...

21350
来自专栏代码拾遗

反射基础之Field

java.lang.reflect.Field 类的方法可以查询字段的信息。比如:名字,类型,修饰符和注解。同样也有方法可以动态访问和修改字段的值。

16410
来自专栏java、Spring、技术分享

fastjson详解

  fastjson用于将Java Bean序列化为JSON字符串,也可以从JSON字符串反序列化到JavaBean。

94510
来自专栏10km的专栏

fastjson:javabean按字段(field)序列化存储为Map并反序列化

大部分json工具对java对象整体序列化都提供了简单的调用方式,以fastjson为例: Model model = new Model(); String ...

40350
来自专栏java一日一条

Java中的语法糖

语法糖方便了程序员的开发,提高了开发效率,提升了语法的严谨也减少了编码出错误的几率。我们不仅仅在平时的编码中依赖语法糖,更要看清语法糖背后程序代码的真实结构,这...

6920
来自专栏desperate633

LeetCode 350. Intersection of Two Arrays II题目分析代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

12160

扫码关注云+社区

领取腾讯云代金券