题目
点这里看题目。
分析
我们用三元组 \((l,r,x)\) 表示令 \(a_l,a_{l+1},\dots,a_r\) 与起来为 \(x\) 的一条限制。
考虑给定一堆限制的时候，如何检查它们合不合法。
显然可以拆位考虑。枚举二进制的第 \(k\) 位，那么现在每个位置都只能是 0 或者 1。此时条件 \((l,r,x)\) 会变成一下两种之一：
- 如果 \(x\) 在第 \(k\) 位上为 1，此时这个条件要求 \(a_{l},a_{l+1},\dots,a_r\) 在第 \(k\) 位上与起来为 1，所以每个数必须都是 1；
- 如果 \(x\) 在第 \(k\) 位上位 0，此时这个条件要求 \(a_l,a_{l+1},\dots,a_r\) 在第 \(k\) 位上与起来为 0，所以其中至少有一个 0；
我们可以将所有的 1 限制先全部施加到序列上，再检查所有的 2 限制。既然可以检查了，我们就有了一个 \(O(n^2\log_2(\max x))\) 的算法。
但是，虽然外层枚举的内容可以被化为若干个限制的区间，但是区间之间并没有良好的递推关系（因为这个检查方式是强制离线的）。注意到问题的要求是“不考虑某一条限制，其余限制能否同时成立”，因此，这导出了另一个方向：我们可以根据每一位上的检查情况，推断不考虑哪些限制可以保证剩余成立。
仍然枚举第 \(k\) 位，仍然先施加所有 1 限制。现在考虑 2 限制的冲突情况，假如有 \(c\) 条 2 限制出现了冲突：
- 如果 \(c=0\)，那么当前位上任意删除一条限制都 OK；
- 如果 \(c=1\)，那么我们删除冲突的那一条就 OK，但是删除其它的就不行；
- 如果 \(c>1\)，怎么删除都不行；
考虑完 2 限制的删除方式，我们接着考虑 1 限制的。2 限制的要求是“给定区间内有至少一个 0”，为了让某一冲突的限制的区间中出现 0，我们考虑区间中仅仅被覆盖了 1 次的位置，其中一个位置为 \(i\)。如果删除 \(i\) 所对应的区间，那么就可以让这条冲突的限制变得合法。
那么对于一个 2 限制而言，我们需要做的是枚举其中所有仅被覆盖 1 次的位置，这些位置的 \(g\) 所对应的 1 限制就是删除后使得该 2 限制合法的所有 1 限制，我们不妨称为该 2 限制的“合法化 1 限制”。将所有的冲突的 2 限制的“合法化 1 限制”取交，我们得到的就是所有删除后可行的 1 限制。
由于如下性质：对于仅仅被覆盖 1 次的位置 \(i\)，设覆盖它的区间为 \(g_i\)。考虑三个仅被覆盖 1 次的位置 \(i<j<k\)，如果有 \(g_i=g_k\)，那么一定会有 \(g_i=g_j=g_k\)（这容易使用反证法说明）；所以我们可以对于可能的“合法化 1 限制”重标号，使得 \(g\) 是单调的。那么每个冲突的 2 限制的“合法 1 限制”在重标号后，下标将会变成一段连续的区间，而区间取交是相当容易的。同时，由于 \(g\) 的单调性，寻找某个冲突的 2 限制的“合法 1 限制”区间也比较简单。
精细实现后可以得到一个 \(O(n\log_2(\max a))\) 的算法。
小结：
- 一定要灵活转换思路，明知外层枚举的算法难以优化，就应该主动求变，舍弃掉这样的做法；
- 思路不能僵化：对于“只忽略一条限制”的问题，不仅可以枚举，也可以推断。
- 注意一下本题中利用标号的连续性质，将集合取交转化成区间取交的方法；
- 注意一下实现细节：求 \(g\) 也可以使用差分。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int MAXN = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( ! ( ‘0‘ <= s && s <= ‘9‘ ) ) { f = 1; if( s == ‘-‘ ) f = -1; s = getchar(); }
while( ‘0‘ <= s && s <= ‘9‘ ) { x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( ‘-‘ ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + ‘0‘ );
}
int vio[MAXN], tot;
int pos[MAXN], seq[MAXN], ID;
LL f[MAXN], g[MAXN];
int nxt[MAXN], pre[MAXN];
int ans[MAXN];
int qL[MAXN], qR[MAXN]; LL qX[MAXN];
int N, K;
int main()
{
read( N ), read( K );
rep( i, 1, K ) read( qL[i] ), read( qR[i] ), read( qX[i] );
nxt[N + 1] = N + 1, pre[0] = 0;
for( int k = 0 ; k < 60 ; k ++ )
{
rep( i, 1, N ) f[i] = g[i] = 0;
rep( i, 1, K )
if( qX[i] >> k & 1 )
{
f[qL[i]] ++, f[qR[i] + 1] --;
g[qL[i]] += i, g[qR[i] + 1] -= i;
}
rep( i, 1, N ) f[i] += f[i - 1], g[i] += g[i - 1];
per( i, N, 1 ) nxt[i] = f[i] ? nxt[i + 1] : i;
ID = tot = 0;
rep( i, 1, K )
if( ! ( qX[i] >> k & 1 ) )
if( nxt[qL[i]] > qR[i] )
vio[++ tot] = i;
if( tot == 0 )
{
rep( i, 1, K ) ans[i] ++;
continue;
}
if( tot == 1 ) ans[vio[1]] ++;
rep( i, 1, N )
if( f[i] == 1 && ! pos[g[i]] )
seq[pos[g[i]] = ++ ID] = g[i];
rep( i, 1, N ) pre[i] = f[i] == 1 ? i : pre[i - 1];
per( i, N, 1 ) nxt[i] = f[i] == 1 ? i : nxt[i + 1];
int l = 0, r = ID;
rep( i, 1, tot )
{
int u = vio[i];
if( nxt[qL[u]] <= qR[u] )
l = std :: max( l, pos[g[nxt[qL[u]]]] );
else
l = ID + 1;
if( pre[qR[u]] >= qL[u] )
r = std :: min( r, pos[g[pre[qR[u]]]] );
else
r = 0;
}
rep( i, l, r ) ans[seq[i]] ++;
rep( i, 1, K ) pos[i] = 0;
}
rep( i, 1, K ) putchar( ( ans[i] == 60 ) + ‘0‘ );
puts( "" );
return 0;
}