😭😭😭

😭😭😭

😭😭😭

😭😭😭

😭😭😭

😭😭😭

$😭😭😭$

$\large 😭😭😭$

$\Large 😭😭😭$

$\LARGE 😭😭😭$

$\huge 😭😭😭$

$\Huge 😭😭😭$

得了 $\large 200pts$，挂了 $\Huge 230pts😭$

A

$100/100$，AC

我们可以先用前缀和求出每张传单的范围。询问时，我们用二分即可找到每个人对应的传单。

B

$100/100$，AC

我们可以预处理出以 $i$ 开头和结尾的最长上升子段的长度。那么我们就可以枚举每个下标，判断若将其替换可以得到的最长长度即可。

C

$0/100$，$\Huge CE😭$

不是为什么 int pos = min(lower_bound(a + i, a + n + 1, a[i] * j) - a - 1, n); 不开long long会CE啊？

啊，原来是 lower_bound(a + i, a + n + 1, a[i] * j) - a - 1 不是 int，不可以直接取 min，我

由于取模运算过于复杂，考虑用其他运算代替来思考。

由于我们的目标是 $\max (a_i \bmod a_j) (1 \le i, j \le n, a_j \le a_i)$，我们可以将 $a_i \bmod a_j$ 转化成求 $a_i - k \cdot a_j (k \cdot a_j \le a_i \le (k + 1) \cdot a_j)$。

由于有 $a_j \le a_i$ 的限制条件，我们可以先将 $a$ 排一遍序，这样可以方便处理。再根据上面的处理，我们可以枚举 $j$，再根据 $k$ 将 $j$ 之后的数分段。这样每一段最优的一定就是最后的一个数。

由上面的处理，我们可以得到一个较为暴力的做法。但是，经过仔细观察，我们可以发现这个时间复杂度是正确的！

对于一个数 $x$，他的一个段的长度是 $x$，因此该做法的时间复杂度是 $\mathcal O(\sum \lceil \frac{a_n}{a_i} \rceil \cdot \log n)$。可是，当 $a_i = 1(1 \le i \le n - 1)$ 且 $a_n = 10^6$ 时怎么办呢？

我们发现，当出现重复的数时，后出现的数的贡献一定不优于先出现的数。这是因为先出现的数比后出现的数多了他们之间的数的选择方法。因此，我们可以降低一部分时间复杂度。

那么，这时卡到最大时间复杂度的构造方法是 $a_i = i(1 \le i \le n - 1)， a_n = 10^6$。经过严密的计(测)算(试)，我们可以发现这样的方法会卡到 $2500ms$。

由于 $a_n$ 很大，前面的数会再 $n - 1$ 至 $10^6$ 这一个真空的区域浪费很长的时间遍历，产生了浪费。

由于 $a_i \le 10^6$，我们可以对值域作前缀和，对一段二分时，若这段为空，我们就可以跳过这一段，这样我们就可以节约出一个二分的时间。

总时间复杂度为 $\mathcal O(能过)$。

代码如下：

const int kMaxN = 2e5 + 5, kMaxM = 4e6 + 5;

int n, ans, a[kMaxN], sum[kMaxM];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[a[i]]++;
    }
    for(int i = 1; i <= 2e6; i++) {
        sum[i] += sum[i - 1];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        if(a[i] == a[i - 1]) {
            continue;
        }
        for(int j = 2; j <= (a[n] / a[i]) + 1; j++) {
            if(sum[a[i] * j] - sum[a[i] * (j - 1)] == 0) {
                continue;
            }
            int pos = min(lower_bound(a + i, a + n + 1, a[i] * j) - a - 1ll, n);
            ans = max(ans, a[pos] % a[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

累计挂分：$100pts/230pts$

D

$0/100$， $\huge TLE + WA😭$

怎么会有一个正常的生物会做到 lowerbound 不排序啊

怎么会有人忘记判断右边第二格和左边第二格的情况啊

这是一个悲伤的故事：

    ios::sync_with_stdio(0), cin.tie(0);
    cin >> m;
    for(int i = 1; i <= m; i++) {
        vis[i] = 1;
        cin >> x[i] >> y[i];
        num[y[i]].emplace_back(x[i]);
        idx[y[i]].emplace_back(i);
    }
    for(int i = 1; i <= m; i++) {
        int tmp = /*竟然真的有一个生物会不排序直接lower_bound*/lower_bound(num[y[i] + 1].begin(), num[y[i] + 1].end(), x[i] - 1) - num[y[i] + 1].begin();
        for(int j = 0; tmp < num[y[i] + 1].size() && num[y[i] + 1][tmp] <= x[i] + 1/*真的有人会只判断左右两边的东西，而不考虑右边和左边的第二格*/; tmp++, j++) {
            fa[idx[y[i] + 1][tmp]].push_back(i);
            son[i][j] = idx[y[i] + 1][tmp];
            cnt[idx[y[i] + 1][tmp]]++;
        }
    }

$\Huge 😭😭😭😭😭$

我们可以玩一玩方块，发现能取的只有上面没有任何方块"压着"的方块和自己上面的方块都有至少两个其他方块托着的方块。

因此我们只用将这些方块放在一个 set 里面，若这一回合蜗蜗取，那么就取 set 的 end，否则取 begin。

每次删除是更新其他方块的状态，把能拿走的放进 set 若更新后不能拿走就拿出 set。

模拟即可。

const int kMaxN = 2e5 + 5, kMod = 1e9 + 9; 

int m, x[kMaxN], y[kMaxN];
map<Pii, int> vis;
set<int> s;
LL ans;

int Cover(int p, int cnt = 0) {
  for(int d = -1; d <= 1; d++) {
    cnt += !!(vis[mkp(x[p] + d, y[p] - 1)]);
  }
  return cnt;
}

bool Check(int p, bool f1 = 1, bool f2 = 1) {
  for(int d = -1; d <= 1; d++) {
    int nx = x[p] + d;
    if(vis[mkp(nx, y[p] + 1)]) {
      f1 = 0;
    }
    if(Cover(vis[mkp(nx, y[p] + 1)]) == 1) {
      f2 = 0;
    }
  }
  return f1 || f2;
}

void Del(int p) {
  s.erase(p);
  vis[mkp(x[p], y[p])] = 0;
  for(int d = -2; d <= 2; d++) {   //由于删的方块和上面一层的方块都可以延长一格，因此-2 -- 2 
    if(!vis[mkp(x[p] + d, y[p])]) {
      continue;
    } 
    if(!Check(vis[mkp(x[p] + d, y[p])])) {
      s.erase(vis[mkp(x[p] + d, y[p])]);
    } else {
      s.insert(vis[mkp(x[p] + d, y[p])]);
    }
  }
  for(int d = -1; d <= 1; d++) {
    if(vis[mkp(x[p] + d, y[p] - 1)] && Check(vis[mkp(x[p] + d, y[p] - 1)])) {
      s.insert(vis[mkp(x[p] + d, y[p] - 1)]);
    }
  } 
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> m;
  for(int i = 1; i <= m; i++) {
    cin >> x[i] >> y[i];
    vis[mkp(x[i], y[i])] = i;
  } 
  for(int i = 1; i <= m; i++) {
    if(Check(i)) {
      s.insert(i);
    }
  }
  for(int i = 1, pos; i <= m; i++) {
    if(i & 1) {
      auto tmp = s.end();
      tmp--;
      pos = *tmp;
    } else {
      pos = *s.begin();
    }
    ans = (ans * m + pos - 1) % kMod;
    Del(pos); 
  }
  cout << ans << endl;
  return 0;
}

累计挂分：$200pts/230pts$

E

为什么我的 30 分暴力也挂了呀

$\LARGE😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭$

考虑DP。

设 $f_{i, 0}$ 表示满足 $i \subseteq j$ 的 $\max a_j$； $g_{i, 0}$ 表示满足 $i \subseteq j$ 的 $\max b_j$。$f_{i, 1}$ 与 $g_{i, 1}$ 则表示最小值。

由此，若我们求出了这些DP值，那么我们就可以得出 $c_k$ 相较于 $c_{k + 1}$ 新增的最大值了。我们可以直接将上述的四个变量分别组合，相乘，取最大值即可。

但是，$k \subseteq i，k \subseteq j$ 不代表 i & j == k 啊！很有道理，但是我们求的是 i & j >= k 的数，而 $k$ 一定是 $i, j$ 的子集，因此 i & j 一定 >= k。

代码如下:

const int kMaxN = 2e5 + 5, kMod = 998244353; 

int t, n, a[kMaxN], b[kMaxN];
LL f[kMaxN][2], g[kMaxN][2]; 

LL Get_ans() {
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    f[i][0] = f[i][1] = a[i];
  }
  for(int i = 0; i < n; i++)  {
    cin >> b[i];
    g[i][0] = g[i][1] = b[i];
  }
  for(int i = n - 1; i >= 0; i--) {
    for(int j = 0; (1ll << j) < n; j++) {
      if(!(i & (1ll << j)) && (i ^ (1ll << j)) < n) {
        f[i][0] = max(f[i][0], f[i ^ (1ll << j)][0]);
        f[i][1] = min(f[i][1], f[i ^ (1ll << j)][1]);
        g[i][0] = max(g[i][0], g[i ^ (1ll << j)][0]);
        g[i][1] = min(g[i][1], g[i ^ (1ll << j)][1]); 
      } 
    } 
  }
  LL maxi = -2e18, ans = 0;
  for(int i = n - 1; i >= 0; i--) {
    maxi = max({maxi, f[i][0] * g[i][0], f[i][1] * g[i][1], f[i][1] * g[i][0], f[i][0] * g[i][1]});
    (ans += maxi % kMod + kMod) %= kMod;
  }
  return ans;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  for(cin >> t; t--; ) {
    cout << Get_ans() << '\n'; 
  } 
  return 0;
}

累计挂分： $230pts/230pts$