HYSBZ3295-動态逆序對

動态逆序對

Time Limit: 10 Sec   Memory Limit: 128 MB

Submit: 5029   Solved: 1686

[ Submit][ Status][ Discuss]

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

Sample Output

5

2

2

1

樣例解釋

(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

Source

解題思路：把删除變成倒着插入，給每個坐标一個權值t，表示插入時間。那麼第一個删除的t坐标當然是n，表示最後一個插入。把未被删除的結點的t坐标從左往右設為1、2、3……那麼問題就變成了求對于(t0,x0,y0)滿足t<t0,x<x0,y>y0或滿足t<t0,x>x0,y<y0的(t,x,y)的個數（x表示數字的坐标，y表示數字的值）。首先CDQ分治之前按t排序，保證t已經有序，在每次分治内部，按x排序，正着掃整個區間的時候，對于[mid+1,r]的區間就在樹狀數組上查詢大于他的y的值的數量；倒着掃，對于[mid+1,r]的區間就在樹狀數組上查詢小于他的y的值的數量。因為左邊的所有元素對于右邊的所有元素而言，是可以肯定t小的

這題也可以用樹套樹的方法解決，同樣是把删除變成倒着插入

cdq分治：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

int n, m, pos[100005], x[100005];
LL ans[100005];
struct node
{
	int t, p, v;
}a[100005];

bool cmpt(node a, node b)
{
	return a.t < b.t;
}

bool cmp(node a, node b)
{
	return a.p < b.p;
}

int lowbit(int k) { return k&-k; }
void update(int k, int val) { for (; k <= 100000; k += lowbit(k)) x[k] += val; }
int getsum(int k) { int sum = 0; for (; k; k -= lowbit(k)) sum += x[k]; return sum; }

void cdq(int l, int r)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	sort(a + l, a + mid + 1, cmp); sort(a + mid + 1, a + r + 1, cmp);
	int j = l;
	for (int i = mid + 1; i <= r; i++)
	{
		for (; j <= mid&&a[j].p < a[i].p; j++) update(a[j].v, 1);
		ans[a[i].t] += getsum(n) - getsum(a[i].v);
	}
	for (j--; j >= l; j--) update(a[j].v, -1);
	j = mid;
	for (int i = r; i >= mid + 1; i--)
	{
		for (; j >= l&&a[j].p > a[i].p; j--) update(a[j].v, 1);
		ans[a[i].t] += getsum(a[i].v);
	}
	for (j++; j <= mid; j++) update(a[j].v, -1);
}

int main()
{
	while (~scanf("%d%d", &n,&m))
	{
		memset(a, 0, sizeof a);
		memset(ans, 0, sizeof ans);
		for(int i=1;i<=n;i++) scanf("%d",&a[i].v), a[i].p = i, pos[a[i].v] = i;
		int x, tt = n;
		for(int i=1;i<=m;i++) scanf("%d",&x), a[pos[x]].t = tt--;
		for(int i=1;i<=n;i++)
			if (!a[i].t) a[i].t = tt--;
		sort(a + 1, a + 1 + n,cmpt);
		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;
}
           

樹套樹：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cctype>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

#define LL long long
#define N 100003
const int INF = 0x3f3f3f3f;
int a[N], n, q, tot, s[N], b[N], x[N], flag[N];
int L[N * 100], R[N * 100], sum[N * 100];
LL ans[N];

int lowbit(int x) { return x&(-x); }

void add(int &k, int l, int r, int p, int val)
{
	if (!k) k = ++tot;
	sum[k] += val;
	if (l == r) return;
	int mid = (l + r) / 2;
	if (p <= mid) add(L[k], l, mid, p, val);
	else add(R[k], mid + 1, r, p, val);
}

void update(int k, int p, int val)
{
	for (int i = k; i <= n; i += lowbit(i)) add(s[i], 1, n, p, val);
}

LL get(int k, int l, int r, int ll, int rr)
{
	if (ll <= l&&r <= rr) return 1LL * sum[k];
	int mid = (l + r) / 2;
	LL ans = 0;
	if (ll <= mid) ans += get(L[k], l, mid, ll, rr);
	if (rr > mid) ans += get(R[k], mid + 1, r, ll, rr);
	return ans;
}

LL query(int k, int l, int r)
{
	if (!k || l > r) return 0;
	LL ans = 0;
	for (int i = k; i >= 1; i -= lowbit(i)) ans += get(s[i], 1, n, l, r);
	return ans;
}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), x[a[i]] = i;
	for (int i = 1; i <= q; i++) scanf("%d", &b[i]), flag[x[b[i]]] = 1;
	for (int i = 1; i <= n; i++)
		if(!flag[i]) update(i, a[i], 1);
	LL sum = 0;
	for (int i = 2; i <= n; i++)
		if(!flag[i]) sum += query(i - 1, a[i] + 1, n);
	for (int i = q; i >= 1; i--)
	{
		sum += query(x[b[i]] - 1, b[i] + 1, n);
		sum += (query(n, 1, b[i] - 1) - query(x[b[i]], 1, b[i] - 1));
		update(x[b[i]], b[i], 1);
		ans[i] = sum;
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}