Hdu5517 Triple

Description

Input

Output

Sample Input

Sample Output

首先对于二元组\(\langle a_{1},b \rangle,\langle a_{2},b \rangle \dots\)我肯定直选\(a\)最大的与\(B\)集合中的元素配对。不妨设最大的为\(a_{1}\),若我选择了\(a_{i}\)配对，那么$$\langle a_{1},c,d \rangle \in BETTER_{C}\langle a_{i},b,c \rangle$$

所以\(C\)中有用的元素减少到了\(O(N)\)个。之后就是要找的极大的三元组的个数，这个CDQ分治或者二维树状数组都行(就是最大非升子序列长度为\(1\)的元素个数)。

#include<iostream>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

typedef long long ll;

#define lowbit(a) (a&(-a))

#define maxm (1010)

#define maxn (100010)

int T,tot,cnt,N,M,A[maxn],nA[maxn],tree[maxm][maxm]; ll ans;

struct node { int a,b; }; vector <node> B[maxn];

struct mode

{

	int a,b,c; ll num;

	friend inline bool operator <(const mode &x,const mode &y)

	{

		if (x.a != y.a) return x.a < y.a;

		else

		{

			if (x.b != y.b) return x.b < y.b;

			else return x.c < y.c;

		}

	}

	friend inline bool operator ==(const mode &x,const mode &y) { return x.a == y.a&&x.b == y.b&&x.c == y.c; }

}C[maxn],bac[maxn];

inline bool cmp(int x,int y) { return x > y; }

inline void ins(int i,int y)

{

	for (;i <= 1000;i += lowbit(i))

		for (int j = y;j <= 1000;j += lowbit(j)) ++tree[i][j];

}

inline int calc(int i,int y)

{

	int ret = 0;

	for (;i;i -= lowbit(i)) for (int j = y;j;j -= lowbit(j)) ret += tree[i][j];

	return ret;

}

inline void init()

{

	tot = cnt = ans = 0; memset(tree,0,sizeof(tree));

	for (int i = 1;i <= 100000;++i) A[i] = nA[i] = 0,B[i].clear();

}

int main()

{

	freopen("5517.in","r",stdin);

	freopen("5517.out","w",stdout);

	scanf("%d",&T);

	for (int Cas = 1;Cas <= T;++Cas)

	{

		printf("Case #%d: ",Cas);

		scanf("%d %d",&N,&M); init();

		for (int i = 1;i <= N;++i)

		{

			int a,b; scanf("%d %d",&a,&b);

			if (a > A[b]) A[b] = a,nA[b] = 1;

			else if (a == A[b]) nA[b]++;

		}

		for (int i = 1;i <= M;++i)

		{

			int a,b,c; scanf("%d %d %d",&a,&b,&c);

			B[c].push_back((node){a,b});

		}

		for (int i = 1;i <= 100000;++i)

			if (A[i]&&!B[i].empty())

				for (int j = 0,nn = B[i].size();j < nn;++j)

					bac[++tot] = (mode){A[i],B[i][j].a,B[i][j].b,nA[i]};

		sort(bac+1,bac+tot+1);

		for (int i = 1,j;i <= tot;i = j)

		{

			for (j = i+1;j <= tot&&bac[j] == bac[i];++j) bac[i].num += bac[j].num;

			C[++cnt] = bac[i];

		}

		for (int i = cnt;i;--i)

		{

			int p1 = 1000-C[i].b+1,p2 = 1000-C[i].c+1;

			if (!calc(p1,p2)) ans += C[i].num; ins(p1,p2);

		}

		cout << ans << endl;

	}

	fclose(stdin); fclose(stdout);

	return 0;

}