Bitset（[HZOI 2015]偏序++）

时间：2024-12-18 10:03:01

Bitset简介

下面介绍C++ STL 中一个非常有用的东西：

Bitset

类似于二进制状压，它可以把信息转化成一个01串存储起来

定义方法：

首先要#include<bitset>或#include<bits/stdc++.h>

然后定义一个长度为len的bitset S

bitset<len>S;

一些操作

Bitset（[HZOI 2015]偏序++）

bitset还支持&，^，|三个运算

b._Find_first() 找到第一个1的位置

b._Find_next(x)找到x后面为1的第一个位置

复杂度

时间：我感觉很慢，但学长说是O(玄学)，而且开了氧气优化后跑的飞快

空间：自己测一下就好

[HZOI 2015]偏序++

题面戳我

这是一道有趣的k+1维偏序，加上下标最多有7维

树套树套树套......套树？显然写不出

几层CDQ套在一起？O(n log^k n)，TLE飞了

kd-tree可以卡过

这道题可以考虑用bitset做

对于每一个k+1维的组合，如果求出每一维小于它的集合，答案就是每一维的交集，就是二进制按位与

用bitset可以做到

可以这样bitset <40000> S[8][40000]

然后就AC了

？？？等等，你当bitset不要空间的吗？显然不行

所以我们考虑分块，只记录下每块块顶的，快内的暴力算，时间O(\(n\sqrt n\))

可以吊打kd-tree

代码

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

# define Copy(a, b) memcpy(a, b, sizeof(a))

# define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

using namespace std;

typedef long long ll;

const int _(5e4 + 10);

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, bl[_], pre[_], suf[_], blo, k, b[8][_], bblo;

pair <int, int> a[8][_];

bitset <_> S[8][250];

IL int Find(RG int v, RG int x){

	RG int l = 1, r = n, ans = 0;

	while(l <= r){

		RG int mid = (l + r) >> 1;

		if(a[x][mid].first <= v) l = mid + 1, ans = mid;

		else r = mid - 1;

	}

	return ans;

}

IL bitset <_> Getbst(RG int x, RG int y){

	bitset <_> ans; ans.reset();

	RG int pos = Find(y, x);

	if(!pos) return ans;

	ans = S[x][bl[pos] - 1];

	for(RG int i = pre[pos]; i <= pos; ++i) ans.set(a[x][i].second);

	return ans;

}

IL ll Calc(){

	bitset <_> ans; RG ll ret = 0;

	for(RG int i = 1; i <= n; ++i){

		ans.set();

		for(RG int j = 1; j <= k; ++j) ans &= Getbst(j, b[j][i]);

		ret += ans.count() - 1;

	}

	return ret;

}

int main(RG int argc, RG char* argv[]){

	File("partial_order_plus");

	n = Read(); k = Read() + 1; bblo = sqrt(n);

	for(RG int i = 1; i <= n; ++i) a[1][i] = make_pair(b[1][i] = i, i);

	for(RG int j = 2; j <= k; ++j)

		for(RG int i = 1; i <= n; ++i)

			a[j][i] = make_pair(b[j][i] = Read(), i);

	for(RG int i = 1; i <= n; ++i){

		bl[i] = (i - 1) / bblo + 1;

		pre[i] = (bl[i] - 1) * bblo + 1;

		suf[i] = min(n, bl[i] * bblo);

	}

	blo = bl[n];

	for(RG int i = 2; i <= k; ++i) sort(a[i] + 1, a[i] + n + 1);

	for(RG int j = 1; j <= k; ++j)

		for(RG int i = 1; i <= blo; ++i){

			S[j][i] = S[j][i - 1]; RG int d = (i - 1) * bblo + 1;

			for(RG int l = pre[d]; l <= suf[d]; ++l) S[j][i].set(a[j][l].second);

		}

	printf("%lld\n", Calc());

    return 0;

}

相关文章