这里将每一个三元组 \((a_i,b_i,c_i)\) 称为一组数。
Subtask 1
暴力枚举所有的非空子集即可。
枚举方式可以采用类似状压 DP 的二进制枚举或者直接 DFS。
时间复杂度 \(O(N \times 2^N)\)。
Subtask 2
性质：此时的特征值最多由两个有效组组成，原因可见 Subtask 3。
因为 \(a_i=b_i\)，所以三元组 \((a_i,b_i,c_i)\) 实际上可以压缩为二元组 \((a_i,c_i)\)，对其进行二维偏序。
我这里采用的是排序后树状数组的写法，具体地说：
将所有二元组按照 \(a\) 排序后扫描所有二元组，可以保证对于当前二元组 \(i\) ，之前组 \(j\) 的 \(a_j\) 一定小于 \(a_i\)。
此时如果之前某二元组 \(j\) 有 \(c_j\) 比当前的 \(c_i\) 大，那么这两个二元组就可以合成一个特征值 \((a_i,c_j)\)，组 \(i\) 贡献了 \(a_i\)，组 \(j\) 贡献了 \(c_j\)。
如此，我们构造权值树状数组，每次找当前 \(c_i\) 的后缀和就是之前 \(c_j>c_i\) 的 \(j\) 的数量。
注意，我代码里面是先加入 \(c_i\) 再查找，并且查找的是 \(c_j \ge c_i\) 的 \(j\) 的数量，这是为了确保 \(j\) 能够取到 \(i\)，表示自己与自己组合，即自己单独构成一个特征值。
点击查看代码
namespace BinaryIndexTree{
struct BIT_R{
int c[N];
#define lowbit(x) ((x)&-(x))
void clear()
{
for(int i=1;i<=n;i++)
c[i]=0;
return;
}
void add(int x,int y)
{
for(;x;x-=lowbit(x))
c[x]+=y;
return;
}
int query(int x)
{
long long res=0;
for(;x<=n;x+=lowbit(x))
res+=c[x];
return res;
}
#undef lowbit
}; //反向树状数组（后缀和）
} //namespace BinaryIndexTree
namespace Subtask_2{
pair<int,int> p[N];
void Prework()
{
for(int i=1;i<=n;i++)
p[i]={a[i],c[i]}; //a[i]=b[i]
sort(p+1,p+n+1);
return;
}
BinaryIndexTree::BIT_R bit;
void Solve()
{
Prework();
long long ans=0;
for(int i=1;i<=n;i++)
{
bit.add(p[i].second,1);
ans+=bit.query(p[i].second);
}
printf("%lld\n",ans);
bit.clear();
return;
}
} //namespace Subtask_2
Subtask 3
首先，一个特征值包括三个最大值，其组成有以下三种情况：
- 一组数贡献了所有的最大值，即它的 \(a_i,b_i,c_i\) 都是最大的，此时其它的组可有可无，可以忽略。
- 某一组数贡献了两个最大值，另一组数贡献了剩下的一个最大值，此时其他组可有可无，可以忽略。
- 三个最大值分别由三组构成，剩下的组可有可无，可以忽略。
综上所述，构成一个特征值有效的三元组最多只有三个，直接 \(O(N^3)\) 枚举这三/二/一个三元组即可。
点击查看代码
namespace Subtask_3{
const int N_3=505;
bitset<N_1_3> flag[N_1_3][N_1_3];
void ClearData()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
flag[i][j]&=0;
return;
}
void Solve()
{
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
{
int x=max({a[i],a[j],a[k]});
int y=max({b[i],b[j],b[k]});
int z=max({c[i],c[j],c[k]});
if(!flag[x][y][z])
{
ans++;
flag[x][y][z]=true;
}
}
printf("%d\n",ans);
ClearData();
return;
}
}