这个训练记录属实鸽太久了……

比赛过程

忘叻，，，

补题：E

题意

有一个长为\(n\)的未知序列\(\{a_i\}\)，现在给出\(k\)组限制，每组限制形如\((l_i,r_i,x_i)\)，表示序列中下标在\([l_i,r_i]\)内的元素按位与的结果为\(x_i\)。

对于每组限制，判定如果只考虑除了这个限制外的所有限制，是否可能构造出合法的\(\{a_i\}\)？

\(1\le n,k\le 10^6, 0\le x_i\le 10^{18}\)。

解析

既然是位运算的问题，我们就拆开考虑。那这样对于每一位，限制变成了只有如下两类：

  1. 要求一段区间\([l,r]\)内所有数都是\(1\)。
  2. 要求一段区间\([l,r]\)内存在\(0\)。

我们先钦定所有第一类限制都被满足（就相当于将若干位置直接确定为\(1\)），那么对于某个第二类限制，如果它的区间内所有点都被第一类的段给覆盖了，那么这个第二类限制就会导致不合法。这一部分直接差分标记前缀和就好了。

我们再来考虑判定的问题，下面不需要去讨论不删任何限制就能合法的情况。对于第二类限制，删掉它自己后整体合法当且仅当原来只有它自己导致了不合法，这很好判定；对于第一类限制，要求这个所有第二类限制的段都和这个第一类限制独自出现的下标集是相交的，很容易想到某种操作复杂度为\(O(\log n)\)的数据结构来干这类事，然后……然后复杂度里带着两个\(\log\)，光荣的 T 了。

因此下面我们就尽量在\(O(n)\)​​时间内完成这件事。首先要求那些位置是由某种第一类限制独自覆盖的（下面称这种位置为独立点），这个好说，前缀和就搞出来了；但确定了这一点后，怎么高效的确定这个位置是由哪个第一类限制覆盖的？这个事还是得借助前缀和，我们设一个数组\(p\)​，对于任意第一类段\([l,r]\)​，给\(p_l\)​加上这个段的编号，给\(p_{r+1}\)​减去这个段的编号。那么对于由某种第一类位置独立覆盖的下标\(i\)，\(p\)的前缀和就是覆盖这个位置的第一类限制编号了。

然后接下来是更烦人的东西：判定第一类限制的答案。我们可以注意到，同一种第一类段覆盖的独立点形成若干个连续段，而且不会出现两种同类型的独立点中间夹了不同类型的独立点的情况。那么对于这个第一类限制，删了它还不合法就是以下几种情况：

  1. 存在某个第二类段在它所有独立点的左边（或者右边）。
  2. 有某个第二类段在它两个独立点中间。

第一种情况还是很好说的。第二种也不难，记录每个位置\(i\)上以\(i\)为左端点的所有第二类段的右端点最小值\(e_i\)就能做了。

其实以上的做法不难想，但写起来细节确实挺烦。

代码

#include <bits/stdc++.h>
typedef long long ll;
const int maxb = 62;
const int maxn = 1000005;
struct seg {
  int l, r, id;
};
seg segq[maxn];
std::vector<int> lim_0[maxb], lim_1[maxb];
void proc_lim(int l, int r, int id, ll x) {
  seg pr = (seg){l, r, id};
  segq[id] = pr;
  for(int i = 0; i < maxb; i ++) {
    const int th = (x & 1);
    if(th) {
      lim_1[i].push_back(id);
    } else {
      lim_0[i].push_back(id);
    }
    x >>= 1;
  }
}

int n, k; bool ans[maxn], temp_ans[maxn];
ll sum_1[maxn], sum_id[maxn];
int sum_0[maxn], typ_1[maxn];
int cnt_il[maxn], min_ep[maxn], next[maxn];

void deal(int b) {
  memset(temp_ans, 0, sizeof(temp_ans));
  memset(sum_1, 0, sizeof(sum_1));
  memset(sum_id, 0, sizeof(sum_id));
  memset(sum_0, 0, sizeof(sum_0));
  memset(typ_1, 0, sizeof(typ_1));
  memset(min_ep, 0x3f, sizeof(min_ep));
  for(int s_id : lim_1[b]) {
    const seg &s = segq[s_id];
    sum_1[s.l] ++; sum_id[s.l] += s.id;
    sum_1[s.r + 1] --; sum_id[s.r + 1] -= s.id;
  }
  for(int i = 1; i <= n; i ++) {
    sum_1[i] += sum_1[i - 1];
    sum_id[i] += sum_id[i - 1];
    if(!sum_1[i]) sum_0[i] = 1;
    if(sum_1[i] == 1) typ_1[i] = (int)sum_id[i];
    sum_0[i] += sum_0[i - 1];
  }


  // memset(cnt_il, 0, sizeof(cnt_il));
  int il_cnt = 0, il_id = 0;
  for(int s_id : lim_0[b]) {
    const seg &s = segq[s_id];
    if(sum_0[s.r] == sum_0[s.l - 1]) {
      il_cnt ++; il_id = s.id;
      // cnt_il[s.l] ++;
      // cnt_il[s.r + 1] --;
      min_ep[s.l] = std::min(min_ep[s.l], s.r);
    }
  }
  if(!il_cnt) return;
  for(int s_id : lim_0[b]) {
    const seg &s = segq[s_id];
    if(il_cnt == 1 && il_id == s.id) temp_ans[s.id] = true;
  }

  int last_1 = 0;
  bool has_seg = false;
  for(int i = n; i >= 1; i --) {
    if(last_1 != 0 && typ_1[last_1] == typ_1[i]) {
      next[i] = last_1;
    } else {
      next[i] = n + 1;
    }
    if(typ_1[i]) {
      if(typ_1[i] != typ_1[last_1]) {
        temp_ans[typ_1[i]] = !has_seg;
      }
      last_1 = i;
    }
    if(min_ep[i] <= n) has_seg = true;
  }
  last_1 = 0; int bf_min_ep = 0x3f3f3f3f;
  for(int i = 1; i <= n; i ++) {
    if(typ_1[i] != 0) {
      if(typ_1[i] != typ_1[last_1]) {
        if(bf_min_ep < i) {
          temp_ans[typ_1[i]] = false;
        }
      }
      last_1 = i;
    } else {
      if(min_ep[i] < next[last_1]) {
        temp_ans[typ_1[last_1]] = false;
      }
    }
    bf_min_ep = std::min(bf_min_ep, min_ep[i]);
  }
  for(int i = 1; i <= k; i ++) {
    ans[i] = (ans[i] && temp_ans[i]);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for(int i = 1; i <= k; i ++) {
    int l, r; ll x;
    scanf("%d%d%lld", &l, &r, &x);
    proc_lim(l, r, i, x);
    ans[i] = true;
  }
  for(int i = 0; i < maxb; i ++) deal(i);
  for(int i = 1; i <= k; i ++) {
    if(ans[i]) {
      putchar('1');
    } else {
      putchar('0');
    }
  }
  puts("");
  return 0;
}