C. 特殊区间

题目描述

给定一个数列 \(A_1,A_2,\dots,A_N\)，我们定义一个区间 \([l,r](l<r)\) 的价值为：

给定 \(Q\) 次查询，每次查询有多少个区间的价值在 \([d,u]\) 之间。

思路

显然，我们会令 \(A_a\) 最大，\(A_b\) 最小，\(A_c\oplus A_d\) 最小。由于一个序列的异或最小值为将其排序后相邻两项的异或最小值，所以我们使用两个 multiset 分别维护排序后的数列和排序后数列相邻两项异或值。由于这里有单调性，所以我们可以通过双指针求出价值 \(\ge x\) 的区间数量，使用前缀和的方式相减即可求出答案。

空间复杂度 \(O(N)\)，时间复杂度 \(O(QN\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 50001, MAXV = 1000001;

int n, q;
ll a[MAXN];
multiset<ll> s, s2;

void Insert(ll x) {
  auto it = s.lower_bound(x);
  if(it != s.begin() && it != s.end()) {
    s2.erase(s2.find((*prev(it)) ^ (*it)));
  }
  if(it != s.begin()) {
    s2.insert((*prev(it)) ^ x);
  }
  if(it != s.end()) {
    s2.insert((*it) ^ x);
  }
  s.insert(x);
}

void Erase(ll x) {
  s.erase(s.find(x));
  auto it = s.lower_bound(x);
  if(it != s.begin() && it != s.end()) {
    s2.insert((*prev(it)) ^ (*it));
  }
  if(it != s.begin()) {
    s2.erase(s2.find((*prev(it)) ^ x));
  }
  if(it != s.end()) {
    s2.erase(s2.find((*it) ^ x));
  }
}

ll Calc(ll x) {
  s.clear(), s2.clear();
  Insert(a[1]);
  ll ret = 0;
  for(int i = 1, j = 1; i <= n; Erase(a[i]), ++i) {
    for(; j <= n && (s2.empty() || *prev(s.end()) - *s.begin() - *s2.begin() < x); ) {
      if(++j <= n) {
        Insert(a[j]);
      }
    }
    ret += (n - j + 1);
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 1; i <= q; ++i) {
    ll d, u;
    cin >> d >> u;
    cout << Calc(d) - Calc(u + 1) << "\n";
  }
  return 0;
}

D. 魔法阵

题目描述

你要将 \(N\) 个魔导器围成一圈，如果魔导器 \(i\) 与 \(j\) 相邻，则会构成一个魔力值为 \(m_{i,j}\) 的魔术通路。只有任意两个魔术通路的魔力值之差 \(\le k\)，这个排列才是稳定的。现在有一些位置已经确定了，求有多少种合法的放置魔导器的方法。

思路

为了方便实现，我们先让这个圈转到第一个魔导器固定。若没有确定的魔导器，则强制定义第一个为 \(1\)，最后再让答案乘以 \(N\)。

我们考虑枚举魔力值的最小值 \(x\)。令 \(dp_{0/1,S,i}\) 表示当前是/否出现了 \(x\)，已经使用了魔导器集合 \(S\)，最后一个魔导器为 \(x\)。这里有一维状态是/否出现 \(x\) 是为了防止算重。按此状态转移即可。

空间复杂度 \(O(N2^N)\)，时间复杂度 \(O(N^3 2^N)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 14, MOD = 998244353, MAXV = (1 << 13);

int n, k, a[MAXN], pos, p[MAXN], g[MAXN][MAXN], ans, A[MAXN * MAXN], tot, dp[2][MAXV][MAXN];
bool flag;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    if(a[i]) {
      pos = i;
    }
  }
  if(pos) {
    for(int i = 1; i <= n; ++i) {
      p[(i >= pos ? i - pos + 1 : n - pos + 1 + i)] = a[i];
    }
  }else {
    flag = 1, p[1] = 1;
  }
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      cin >> g[i][j];
      if(j < i) {
        A[++tot] = g[i][j];
      }
    }
  }
  for(int i = 1; i <= tot; ++i) {
    for(bool op : {0, 1}) {
      for(int s = 1; s < (1 << n); ++s) {
        for(int j = 1; j <= n; ++j) {
          dp[op][s][j] = 0;
        }
      }
    }
    dp[0][1 << (p[1] - 1)][p[1]] = 1;
    for(int s = 1; s < (1 << n); ++s) {
      for(bool op : {0, 1}) {
        int b = __builtin_popcount(s);
        for(int j = 1; j <= n; ++j) {
          if(!dp[op][s][j]) {
            continue;
          }
          for(int x = 1; x <= n; ++x) {
            if(!((s >> (x - 1)) & 1) && g[j][x] >= A[i] && g[j][x] - A[i] <= k && (!p[b + 1] || p[b + 1] == x)) {
              dp[op | (g[j][x] == A[i])][s | (1 << (x - 1))][x] = (dp[op | (g[j][x] == A[i])][s | (1 << (x - 1))][x] + dp[op][s][j]) % MOD;
            }
          }
        }
      }
    }
    for(int j = 1; j <= n; ++j) {
      if(g[j][p[1]] >= A[i] && g[j][p[1]] - A[i] <= k) {
        ans = (ans + dp[1][(1 << n) - 1][j]) % MOD;
        if(g[j][p[1]] == A[i]) {
          ans = (ans + dp[0][(1 << n) - 1][j]) % MOD;
        }
      }
    }
  }
  cout << 1ll * (flag ? n : 1) * ans % MOD;
  return 0;
}