题解
9 分钟 读完 (大约 1282 个字)

口胡 Luogu3157 [CQOI2011 动态逆序对]

传送门

题目大意

给定一个$1$到$n\le10^5$的排列。

有$m$次删除操作，每次删去一个数，问删去前序列的逆序对是多少。

解析

K-D Tree

想练习一下K-D Tree，结果做法不太对，被卡常了。

小问题，我口胡一下K-D Tree的正解。

一个数产生的贡献是：
$$
\sum_{k<i} [a_k>a_i]+\sum_{i<k}[a_i>a_k]
$$
考虑把每个数$a_i$记作二维平面上的一个点$(i,a_i)$，那么一个数产生的贡献就变成了它左上角和右下角的点数之和。

这个就可以K-D Tree了。

主席树

再上一个树状数组，随便做。

Code

咕咕咕

K-D Tree($80pts$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// luogu-judger-enable-o2
#pragma GCC optimize ("O3")
#define DREP(i, s, e) for(int i = s; i >= e ;i--)
#define  REP(i, s, e) for(int i = s; i <= e ;i++)

#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 100000 + 10, maxm = 50000 + 10, inf = 1e9;
template <typename T> inline T read()
{
	T ans(0), p(1);
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-') p = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		ans = ans * 10 + c - 48;
		c = getchar();
	}
	return ans * p;
}

int n, m, a[maxn], t[maxn], del[maxn], id[maxn], notin[maxn];

int cnt[maxn << 1], Min[maxn << 1], Max[maxn << 1], lp[maxn << 1], rp[maxn << 1];
#define mid (l + r >> 1)
#define ls p << 1
#define rs p << 1 | 1
#define lson ls, l, mid - 1
#define rson rs, mid + 1, r
inline bool cmp1(int a, int b) {return a < b;}
inline bool cmp2(int a, int b) {return id[a] < id[b];}
inline int Cmp1(const void *a, const void *b) {return (*(int*)a) - (*(int*)b);}
inline int Cmp2(const void *a, const void *b) {return id[(*(int*)a)] - id[(*(int*)b)];}
int pos[maxn];
#define pushup(p, l, r)\
{\
	cnt[p] = (!notin[t[mid]]) + cnt[ls] + cnt[rs];\
	Min[p] = min(notin[t[mid]] ? inf : t[mid], 	min(Min[ls], Min[rs]));\
	Max[p] = max(notin[t[mid]] ? -inf : t[mid],	max(Max[ls], Max[rs]));\
}
void build(int p, int l, int r, bool flag = 0)
{
	if (l > r) return;
	qsort(t + l, r - l + 1, 4, flag ? Cmp1 : Cmp2);
	pos[t[mid]] = mid;
	lp[p] = rp[p] = id[t[mid]];
	build(lson, flag ^ 1);
	build(rson, flag ^ 1);
	cnt[p] = !notin[t[mid]];
	Min[p] = notin[t[mid]] ? inf : t[mid];
	Max[p] = notin[t[mid]] ? -inf : t[mid];
	if (l < r)
	{
		pushup(p, l, r);
		chkmin(lp[p], min(lp[ls], lp[rs]));
		chkmax(rp[p], max(rp[ls], rp[rs]));
	}
}
int queryA(int p, int l, int r, int L, int R, int val)
{
	if (l > r || L > rp[p] || R < lp[p] || Max[p] < val || !cnt[p]) return 0;
	bool flag(!notin[t[mid]] && L <= id[t[mid]] && id[t[mid]] <= R && t[mid] > val);
	if (L <= lp[p] && rp[p] <= R && Min[p] > val) return cnt[p];
	else return queryA(lson, L, R, val) + queryA(rson, L, R, val) + flag;
}
int queryB(int p, int l, int r, int L, int R, int val)
{
	if (l > r || L > rp[p] || R < lp[p] || Min[p] > val || !cnt[p]) return 0;
	bool flag(!notin[t[mid]] && L <= id[t[mid]] && id[t[mid]] <= R && t[mid] < val);
	if (L <= lp[p] && rp[p] <= R && Max[p] < val) return cnt[p];
	else return queryB(lson, L, R, val) + queryB(rson, L, R, val) + flag;
}
void insert(int p, int l, int r, int pos)
{
	cnt[p]++;
	chkmin(Min[p], t[pos]);
	chkmax(Max[p], t[pos]);
	if (mid == pos) return;
	else
		if (pos < mid) insert(lson, pos);
		else insert(rson, pos);
}
long long ans[maxm];

int main()
{
#ifdef CraZYali
	freopen("3157-new.in", "r", stdin);
	freopen("3157-new.out", "w", stdout);
#endif
	cin >> n >> m;
	REP(i, 0, 200000) Max[i] = rp[i] = -inf, Min[i] = lp[i] = inf;

	REP(i, 1, n) id[a[i] = read<int>()] = i;
	REP(i, 1, m) notin[del[i] = read<int>()] = 1;
	copy(a + 1, a + 1 + n, t + 1);
	build(1, 1, n);
	REP(i, 1, n) if (!notin[a[i]]) ans[m+1] += queryB(1, 1, n, i+1, n, a[i]);
	DREP(i, m, 1)
	{
		ans[i] = ans[i+1] + queryA(1, 1, n, 1, id[del[i]] - 1, del[i]) + queryB(1, 1, n, id[del[i]] + 1, n, del[i]);
		notin[del[i]] = 0;
		insert(1, 1, n, pos[del[i]]);
	}
	REP(i, 1, m) printf("%lld\n", ans[i]);
	return 0;
}

主席树(AC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#define  REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)

#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 100000 + 10;

template <typename T> T read()
{
	T ans = 0, p = 1;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-') p = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		ans = ans * 10 + c - 48;
		c = getchar();
	}
	return ans * p;
}

struct node *null;
const int maxnode = 28000000;

int rt[maxnode], ls[maxnode], rs[maxnode], sum[maxnode], cur, LL[30], RR[30];

#define mid (l + r >> 1)
#define lson ls[p], l, mid
#define rson rs[p], mid + 1, r

void update(int &p, int l, int r, int pos, int num)
{
	if (!p) p = ++cur;
	sum[p] += num;
	if (l == r) return;
	else if (pos <= mid)	update(lson, pos, num);
	else					update(rson, pos, num);
}

int n, m, a[maxn], pos[maxn];
long long ans;

int query(int l, int r, int val, bool mode)
{
	int lsz(0), rsz(0), s(0);
	for (int i = l-1; i > 0; i -= i & -i) LL[++lsz] = rt[i];
	for (int i = r	; i > 0; i -= i & -i) RR[++rsz] = rt[i];
	l = 1, r = n;
	while (l < r)
		if (val > mid)
		{
			if (mode)
			{
				REP(i, 1, lsz) s -= sum[ls[LL[i]]];
				REP(i, 1, rsz) s += sum[ls[RR[i]]];
			}
			REP(i, 1, lsz) LL[i] = rs[LL[i]];
			REP(i, 1, rsz) RR[i] = rs[RR[i]];
			l = mid + 1;
		}
		else
		{
			if (!mode)
			{
				REP(i, 1, lsz) s -= sum[rs[LL[i]]];
				REP(i, 1, rsz) s += sum[rs[RR[i]]];
			}
			REP(i, 1, lsz) LL[i] = ls[LL[i]];
			REP(i, 1, rsz) RR[i] = ls[RR[i]];
			r = mid ;
		}
	return s;
}

int main()
{
#ifdef CraZYali
	freopen("3157.in", "r", stdin);
	freopen("3157.out", "w", stdout);
#endif
	cin >> n >> m;
	REP(i, 1, n)
	{
		pos[a[i] = read<int>()] = i;
		ans += 1ll * query(1, i-1, a[i], 0);
		for (int j = i; j <= n; j += j & -j) update(rt[j], 1, n, a[i], 1);
	}
	while (m --> 0)
	{
		printf("%lld\n", ans);
		int x = read<int>(), p = pos[x];
		ans -= query(1, p - 1, x, 0);
		ans -= query(p + 1, n, x, 1);
		for (int i = p; i <= n; i += i & -i) update(rt[i], 1, n, x, -1);
	}
	return 0;
}

CDQ

咕咕咕。

1
2
3
4
5
6
7
8
#include <...>
using namespace std;
void input(){...}
void output(){...}
#define mid (l+r>>1)
void work(int l,int r){...}
inline void CDQ(int l, int r) {CDQ(l,mid);CDQ(mid+1,r);work(l,r);}
int main(){return input(),CDQ(1,n),output(),0;}

后记

其实这个题好像还可以CDQ。

本来就是一个类似二维数点的东西，那CDQ不是随便做？

有时间再写吧。

# K-D Tree, 卡常, 坑

喜欢这篇文章？打赏一下作者吧

LOJ2057 [TJOI2016 & HEOI2016 游戏]
胡闹 方差

评论

链接

分类

标签云

AC自动机 FFT、NTT Hash K-D Tree Kruskal重构树 SAM WO YE BU HUI excrt lct 主席树 二分图 交互 倍增 卡常 可并堆 可持久化 坑 多项式 套路 字符串 容斥 左偏树 带修莫队 平衡树 技巧 插头dp 数论 斜率优化 树上莫队 树套树 毒瘤计数 生成函数 网络流 胡闹系列 莫比乌斯反演 计算几何 高级数据结构 黑科技

最新文章

归档

标签

AC自动机 1
FFT、NTT 6
Hash 3
K-D Tree 1
Kruskal重构树 1
SAM 4
WO YE BU HUI 7
excrt 1
lct 2
主席树 4
二分图 2
交互 1
倍增 2
卡常 2
可并堆 1
可持久化 1
坑 2
多项式 1
套路 2
字符串 10
容斥 2
左偏树 1
带修莫队 2
平衡树 2
技巧 5
插头dp 1
数论 5
斜率优化 2
树上莫队 2
树套树 5
毒瘤计数 2
生成函数 1
网络流 4
胡闹系列 18
莫比乌斯反演 3
计算几何 3
高级数据结构 11
黑科技 2
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×