当前位置: 首页 > news >正文

[CQOI 2011]动态逆序对

Description

题库链接

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

Solution

好久以前的坑了...

解法一

考虑树套树。

删去一个数,减少的逆序对个数是当前位置之前比当前数大的个数以及在这个数的位置之后比当前数小的个数。

如果不支持修改显然是可以用主席树来维护的。

由于要支持修改,我们考虑用树状数组套线段树,树状数组维护序列下标。线段树维护数的个数。那么时间和空间复杂度都是 \(O(n\cdot log^2_2 n)\) 的。

解法二

考虑 \(cdq\)

首先删数很不好操作,我们考虑从后往前操作,让删数变成添数。

我们可以先按时间排序。添加时间早的数才会对添加时间晚的有贡献。对于 \(cdq\) 的每一次操作就是统计添数时间早于某个数的当前位置之前比当前数大的个数以及在这个数的位置之后比当前数小的个数。

Code

解法一

//It is made by Awson on 2018.2.24
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 100000;
void read(int &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, m, a, id[N+5]; LL ans;
struct Segment_tree {
    int root[N+5], ch[N*100][2], key[N*100+5], pos;
    int cpynode(int x) {++pos; ch[pos][0] = ch[x][0], ch[pos][1] = ch[x][1], key[pos] = key[x]; return pos; }
    void insert(int &o, int l, int r, int loc, int val) {
    if (o == 0) o = cpynode(o); key[o] += val;
    if (l == r) return; int mid = (l+r)>>1;
    if (loc <= mid) insert(ch[o][0], l, mid, loc, val); else insert(ch[o][1], mid+1, r, loc, val);
    }
    int query(int o, int l, int r, int a, int b) {
    if ((a <= l && r <= b) || o == 0) return key[o];
    int mid = (l+r)>>1;
    int c1 = 0, c2 = 0;
    if (a <= mid) c1 = query(ch[o][0], l, mid, a, b);
    if (b > mid) c2 = query(ch[o][1], mid+1, r, a, b);
    return c1+c2;
    }
}ST;
struct bittree {
    void add(int o, int val, int key) {for (; o <= n; o += lowbit(o)) ST.insert(ST.root[o], 1, n, val, key); }
    int query(int o, int l, int r) {
    int ans = 0;
    for (; o; o -= lowbit(o)) ans += ST.query(ST.root[o], 1, n, l, r);
    return ans;
    }
}BT;

void work() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) read(a), BT.add(i, a, 1), ans += BT.query(i-1, a, n), id[a] = i;
    for (int i = 1; i <= m; i++) {
    writeln(ans); read(a);
    ans -= BT.query(id[a]-1, a, n);
    ans -= BT.query(n, 1, a);
    ans += BT.query(id[a], 1, a);
    BT.add(id[a], a, -1);
    }
}
int main() {
    work(); return 0;
}

解法二

//It is made by Awson on 2018.2.25
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 1e5;
void read(int &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, m, match[N+5], d; LL ans[N+5];
struct tt {int x, y, t, flag; }a[N+5], b[N+5];
struct bittree {
    int c[N+5];
    void add(int o, int val) {for (; o <= n; o += lowbit(o)) c[o] += val; }
    int query(int o) {int ans = 0; for (; o; o -= lowbit(o)) ans += c[o]; return ans; }
}T;
bool comp1(const tt &a, const tt &b) {return a.t < b.t; }
bool comp2(const tt &a, const tt &b) {return a.x < b.x; }

void CDQ(int l, int r) {
    if (l == r) return; int mid = (l+r)>>1;
    for (int i = l; i <= mid; i++) b[i] = a[i], b[i].flag = 1;
    for (int i = mid+1; i <= r; i++) b[i] = a[i], b[i].flag = 0;
    sort(b+l, b+r+1, comp2);
    for (int i = l; i <= r; i++) if (b[i].flag == 1) T.add(b[i].y, 1); else ans[b[i].t] += T.query(n)-T.query(b[i].y);
    for (int i = l; i <= r; i++) if (b[i].flag == 1) T.add(b[i].y, -1);
    for (int i = r; i >= l; i--) if (b[i].flag == 1) T.add(b[i].y, 1); else ans[b[i].t] += T.query(b[i].y);
    for (int i = l; i <= r; i++) if (b[i].flag == 1) T.add(b[i].y, -1);
    CDQ(l, mid), CDQ(mid+1, r);
}
void work() {
    read(n), read(m); for (int i = 1; i <= n; i++) read(a[i].y), a[i].x = i, match[a[i].y] = i; int times = n;
    for (int i = 1; i <= m; i++) read(d), a[match[d]].t = times--;
    for (int i = 1; i <= n; i++) if (a[i].t == 0) a[i].t = times--;
    sort(a+1, a+n+1, comp1); CDQ(1, n);
    LL Ans = 0; for (int i = 1; i <= n; i++) Ans += ans[i];
    for (int i = n; i > n-m; i--) writeln(Ans), Ans -= ans[i];
}
int main() {
    work(); return 0;
}

转载于:https://www.cnblogs.com/NaVi-Awson/p/8470575.html

相关文章:

  • 当div没有设置宽度,使用width的fit-content和margin:auto实现元素的水平居中
  • 布尔变量在项目中的应用
  • docker redis
  • Codeforces932D. Tree
  • ASP.NET CORE RAZOR :将文件上传至 ASP.NET Core 中的 Razor 页面
  • No packages marked for update
  • MySQL之单表查询
  • linux 下查看一个进程执行路径
  • 字符串匹配 扩展KMP BMSunday
  • linux系统下配置Django虚拟环境的一些总结
  • pwntools 文档学习
  • Notes 20180308 : 语句
  • 软件工程阅读笔记一
  • Servlet中forward和redirect的区别(转)
  • (1)常见O(n^2)排序算法解析
  • 2019.2.20 c++ 知识梳理
  • Apache的基本使用
  • C++入门教程(10):for 语句
  • Java Agent 学习笔记
  • Linux编程学习笔记 | Linux多线程学习[2] - 线程的同步
  • MySQL的数据类型
  • Redis中的lru算法实现
  • 聊聊flink的BlobWriter
  • 如何抓住下一波零售风口?看RPA玩转零售自动化
  • 用Node EJS写一个爬虫脚本每天定时给心爱的她发一封暖心邮件
  • HanLP分词命名实体提取详解
  • kubernetes资源对象--ingress
  • #HarmonyOS:软件安装window和mac预览Hello World
  • #我与虚拟机的故事#连载20:周志明虚拟机第 3 版:到底值不值得买?
  • $GOPATH/go.mod exists but should not goland
  • ( )的作用是将计算机中的信息传送给用户,计算机应用基础 吉大15春学期《计算机应用基础》在线作业二及答案...
  • (4)事件处理——(6)给.ready()回调函数传递一个参数(Passing an argument to the .ready() callback)...
  • (6)添加vue-cookie
  • (Matalb时序预测)PSO-BP粒子群算法优化BP神经网络的多维时序回归预测
  • (二)hibernate配置管理
  • (二)换源+apt-get基础配置+搜狗拼音
  • (二)学习JVM —— 垃圾回收机制
  • (附源码)springboot掌上博客系统 毕业设计063131
  • (三)uboot源码分析
  • (新)网络工程师考点串讲与真题详解
  • (一)硬件制作--从零开始自制linux掌上电脑(F1C200S) <嵌入式项目>
  • (已解决)vue+element-ui实现个人中心,仿照原神
  • (转)Google的Objective-C编码规范
  • (最简单,详细,直接上手)uniapp/vue中英文多语言切换
  • .NET 使用 ILMerge 合并多个程序集,避免引入额外的依赖
  • .net 托管代码与非托管代码
  • @data注解_SpringBoot 使用WebSocket打造在线聊天室(基于注解)
  • @selector(..)警告提示
  • [20170705]diff比较执行结果的内容.txt
  • [20171101]rman to destination.txt
  • [C/C++] C/C++中数字与字符串之间的转换
  • [CC-FNCS]Chef and Churu
  • [HJ73 计算日期到天数转换]
  • [HTML]Web前端开发技术18(HTML5、CSS3、JavaScript )HTML5 基础与CSS3 应用——喵喵画网页
  • [IE技巧] IE 中打开Office文件的设置