wrong answer 5162nd numbers differ - expected: '18', found: '10'。应该这种错误没有别的错法吧,如果有不同的错法欢迎评论。
原因:合并两个区间时,第一个区间最后的 or 值变化处后面可能还有一些数,但是你把它们忽略了,所以维护一段区间还要维护最大值。
核心部分:
AC:
struct arr
{
int x[32], mx[32], len, m;
};
int a[N], b[N];
arr itoa(int x, int y){arr a;a.len = 1, a.mx[1] = a.m = x, a.x[1] = y;return a;}
arr operator + (arr a, const arr &b)
{
int i, m = a.m;
a.m = max(a.m,b.m);
for(i=1;i<=b.len;i++) if((a.x[a.len]|b.x[i])!=a.x[a.len])
{
a.len++;
a.x[a.len] = a.x[a.len-1] | b.x[i];
m = a.mx[a.len] = max(m,b.mx[i]);
}
return a;
}
WA:
struct arr
{
int x[32], mx[32], len;
};
int a[N], b[N];
arr itoa(int x, int y){arr a;a.len = 1, a.mx[1] = x, a.x[1] = y;return a;}
arr operator + (arr a, const arr &b)
{
int i;
for(i=1;i<=b.len;i++) if((a.x[a.len]|b.x[i])!=a.x[a.len])
{
a.len++;
a.x[a.len] = a.x[a.len-1] | b.x[i];
a.mx[a.len] = max(a.mx[a.len-1],b.mx[i]);
}
return a;
}