三元组[01 Trie计数]

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

有两种方法都可以拿到满分

\(Solution\ 1\)

考虑枚举\(y\)

建两个\(01Trie\),要支持删除操作

一颗\(Trie\)维护\(y\)左边的信息

一颗\(Trie\)维护\(y\)右边的信息

在枚举\(y\)的时候左边的添加,右边的删除,可做到\(log\)维护,建树是\(nlog\)

暴力的想法是两个\(Trie\)一起跑,枚举在哪一位开始不一样,前面的情况也都枚举,这样的情况最坏是\(2\)的指数级别,可以拿到\(50\)分

考虑优化这个过程

因为每次只会删去一条链,所以考虑这条链被删去所带来的影响

用\(f[i][0/1]\)表示到第\(i\)位开始不一样的答案

每次删除时只少了一条链,所以把这条链的情况减去

增加时加上新的情况即可

\(Solution\ 2\)

这种方法相对来说代码量要少很多

考虑枚举\(z\)

用一颗\(Tire\)表示前面的信息

仍然考虑枚举在哪一位开始不一样\((d)\)

记\(s[i][0/1]\)表示前面所有在第\(i\)位为\(0/1\)的串的总数

记\(sum[i]\)表示\(Tire\)上\(i\)号节点有多少个不合法的\((x,y)\)对\((y<x)\)

记\(cnt[i]\)表示\(Tire\)上经过\(i\)的个数

由于枚举的是\(z\),我们对\(y\)的要求只有枚举到\(d\)时,其在\(d\)是\(0\)还是\(1\)

假设枚举到的\(z\)的值在\(d\)位是\(c\)

答案就是cnt[原本串中和\(z\)的\(d\)前面的位相同]\(\times s[d][!c]-\)不合法的\((x,y)\)对数

具体可看代码

\(\mathcal{Code}\)

\(Solution\ 2\)

因为这种好实现些,所以就写的这种

/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年09月23日 星期一 19时48分07秒

*******************************/

#include <cstdio>

#include <fstream>

#include <cstring>

#define ll long long

#define reset(x) memset(x,0,sizeof(x))

using namespace std;

const int maxn = 3000006;

const int lim = 29;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	flag|=ch=='-';

		while(ch>='0'&&ch<='9')	res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	res=~res+1;

		return *this;

	}

}cin;

//}}}

int T,n,v,tot;

int ch[maxn][2],s[lim+1][2];

ll sum[maxn],cnt[maxn];

void insert (int rt,int v,int d)

{

	if (d<0)	return;

	int c=(v>>d)&1;

	if (!ch[rt][c])	ch[rt][c]=++tot;

	rt=ch[rt][c];

	++cnt[rt],sum[rt]+=++s[d][c];

	insert(rt,v,d-1);

}

ll query (int rt,int v,int d)

{

	if (d<0)	return 0;

	int c=(v>>d)&1,p=ch[rt][c^1];

	return cnt[p]*s[d][c^1]-sum[p]+query(ch[rt][c],v,d-1);

}

int main()

{

	cin>>T;

	while (T--){

		cin>>n;

		ll ans=tot=0;

		reset(sum),reset(s),reset(ch),reset(cnt);

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

			cin>>v;

			insert(0,v,lim);

			ans+=query(0,v,lim);

		}

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

	}

	return 0;

}

如有哪里讲得不是很明白或是有错误，欢迎指正

如您喜欢的话不妨点个赞收藏一下吧

巴特西

三元组[01 Trie计数]

最新文章

热门文章