装备合成¶
题意¶
给定 k 个装备，每个装备有 n 个属性。
维护 q 组操作：
- 新建一个装备，其每项属性为 x 和 y 装备对应属性的最小值
- 新建一个装备，其每项属性为 x 和 y 装备对应属性的最大值
- 回答 x 装备的 y 属性
解析¶
这道题和今年冬令营抄了同一道题 Magic Breeding，而且这道题几乎完全照抄。
虽然 a_{i,j} 值域很大，但答案只有可能是 k 个 a_{i,j} 中的一个。枚举 k 个初始装备分别作为基准，设 0 表示小于基准的这一属性，1 表示大于等于基准的这一属性，就可以将每种装备表示为一个 01 串。取最大值就是按位或，最小值就是按位与，这些都可以用 std::bitset 实现，时间复杂度为 O(\frac{nq}{\omega})。
当然还有更优秀的复杂度为 O(2^kq) 的做法。枚举当前属性的基准值，用 S 压缩所有装备对应属性相对基准值的大小关系。由于 S 只有 2^k 种取值，维护每个 S 的结果即可。
实现¶
#include <bits/stdc++.h>
template <typename Tp>
void read(Tp &res){
static char ch; ch = getchar(), res = 0;
while(!std::isdigit(ch)) ch = getchar();
while(std::isdigit(ch)) res = res * 10 + ch - 48, ch = getchar();
}
typedef unsigned long long int ull;
const int maxk = 14, maxn = 1e5 + 19;
struct bitset{
std::vector<ull> mk;
void set(int pos, bool val){
mk[pos >> 6] |= (1ull << (pos & 63));
if(!val)
mk[pos >> 6] ^= (1ull << (pos & 63));
}
bool access(int pos){
return mk[pos >> 6] & (1ull << (pos & 63));
}
bitset &operator&=(const bitset &b){
int sz = b.mk.size();
for(int i = 0; i < sz; ++i)
mk[i] &= b.mk[i];
return *this;
}
bitset &operator|=(const bitset &b){
int sz = b.mk.size();
for(int i = 0; i < sz; ++i)
mk[i] |= b.mk[i];
return *this;
}
};
int n, k, q, a[maxk][maxn];
bool vist[maxn];
int tmp[maxn], tot, id[maxn];
int op[maxn], x[maxn], y[maxn], ans[maxn];
bitset t[maxn];
int main(){
read(n), read(k), read(q);
for(int i = 1; i <= k; ++i)
for(int j = 1; j <= n; ++j)
read(a[i][j]);
for(int i = 1; i <= q; ++i){
read(op[i]), read(x[i]), read(y[i]);
if(op[i] == 3)
vist[y[i]] = true;
}
for(int i = 1; i <= n; ++i)
if(vist[i])
tmp[++tot] = i, id[i] = tot;
for(int i = 1; i <= k; ++i)
t[i].mk.resize(tot / 64 + 1);
for(int i = 1; i <= k; ++i){
int m = k;
for(int j = 1; j <= k; ++j){
for(int p = 1; p <= tot; ++p)
t[j].set(p, a[j][tmp[p]] >= a[i][tmp[p]]);
}
for(int j = 1; j <= q; ++j){
if(op[j] == 1){
t[++m] = t[x[j]];
t[m] |= t[y[j]];
}
else if(op[j] == 2){
t[++m] = t[x[j]];
t[m] &= t[y[j]];
}
else{
if(t[x[j]].access(id[y[j]]))
ans[j] = std::max(ans[j], a[i][y[j]]);
}
}
}
for(int i = 1; i <= q; ++i)
if(op[i] == 3)
std::printf("%d\n", ans[i]);
return 0;
}