首页 > 代码库 > [BZOJ3295][Cqoi2011]动态逆序对
[BZOJ3295][Cqoi2011]动态逆序对
[BZOJ3295][Cqoi2011]动态逆序对
试题描述
对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
输入
输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。
输出
输出包含m行,依次为删除每个元素之前,逆序对的个数。
输入示例
5 4 1 5 3 4 2 5 1 4 2
输出示例
5 2 2 1
数据规模及约定
N<=100000 M<=50000
题解
树状数组套主席树不解释。内存卡卡常。。。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <stack> #include <vector> #include <queue> #include <cstring> #include <string> #include <map> #include <set> using namespace std; const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++; } int read() { int x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); } return x * f; } #define maxn 100010 #define maxnode 10100000 #define LL long long int ToT, sumv[maxnode], lc[maxnode], rc[maxnode]; void update(int& y, int x, int l, int r, int p, int v) { sumv[y = ++ToT] = sumv[x] + v; if(l == r) return ; int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x]; if(p <= mid) update(lc[y], lc[x], l, mid, p, v); else update(rc[y], rc[x], mid+1, r, p, v); return ; } int query(int o, int l, int r, int ql, int qr) { if(!o) return 0; if(ql <= l && r <= qr) return sumv[o]; int mid = l + r >> 1, ans = 0; if(ql <= mid) ans += query(lc[o], l, mid, ql, qr); if(qr > mid) ans += query(rc[o], mid+1, r, ql, qr); return ans; } int n, A[maxn], pos[maxn], Rt[maxn], rt[maxn]; void modify(int x, int v) { for(; x <= n; x += x & -x) update(Rt[x], Rt[x], 1, n, v, -1); return ; } int ask(int x, int vl, int vr) { int ans = query(rt[x], 1, n, vl, vr); for(; x; x -= x & -x) ans += query(Rt[x], 1, n, vl, vr); return ans; } int main() { // freopen("data.in", "r", stdin); // freopen("data.out", "w", stdout); n = read(); int q = read(); LL ans = 0; for(int i = 1; i <= n; i++) { A[i] = read(); pos[A[i]] = i; update(rt[i], rt[i-1], 1, n, A[i], 1); ans += query(rt[i-1], 1, n, A[i] + 1, n); } while(q--) { printf("%lld\n", ans); int p = pos[read()]; modify(p, A[p]); ans -= ask(p - 1, A[p] + 1, n) + ask(n, 1, A[p] - 1) - ask(p, 1, A[p] - 1); // printf("ToT: %d\n", ToT); } return 0; }
[BZOJ3295][Cqoi2011]动态逆序对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。