小红书0327

1. 水一水
2. k排序，每次可以从数组中选择k个排序完放数组后面，问排序整个数组需要几次这样操作？

排序完看看多少位置不一样，73%

#include<iostream>
#include<algorithm>
using namespace std;
int a[100010], b[100010];


// 5 4 3 2 1,  something
int main() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t, n, k;
  cin >> t;
  while(t--) {
    int cnt = 0;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i], b[i] = a[i];
    sort(b, b + n);
    for (int i = 0; i < n; ++i)
      if (a[i] != b[i])
        ++cnt;
    if (cnt == n) cnt -= 1;
    cout << (cnt + k - 1) / k << endl;
    
  }
}

3.对一个数组进行m次区间操作（与 或 设置 为一个值）,问最后操作完数组变成什么.

每一轮求一个bit位的值,遍历数组同时用堆维护最后一个修改操作，复杂度20 * nlogm。 100%

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int a[100010], l[100010], r[100010], x[100010];
char op[100010];
vector<int> ops_at_there[100010];


struct ops {
  int time, left, right, bit;
};
bool operator < (const ops &a, const ops &b) {
    return a.time < b.time;
}


int main() {
  cin.tie(0);
  cout.tie(0);
  int n;  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int m;  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> l[i];
    ops_at_there[l[i]].push_back(i);
  }
  for (int i = 1; i <= m; ++i) cin >> r[i];
  for (int i = 1; i <= m; ++i) cin >> op[i];
  for (int i = 1; i <= m; ++i) cin >> x[i];
  for (int bit_idx = 0; bit_idx < 20; bit_idx++) {
    // 确定bit i的值
    priority_queue<ops> pq;
    for (int i = 1; i <= n; ++i) {
      for (int op_idx : ops_at_there[i]) {
        char tp = op[op_idx];
        int bit = (x[op_idx] >> bit_idx) & 1;
        if (tp == '=' || (tp == '|' && bit==1) || (tp == '&' && bit==0)) {
          pq.push({op_idx, l[op_idx], r[op_idx], bit});
        }
      }
      while (!pq.empty() && pq.top().right < i) {
        pq.pop();
      }
      if (!pq.empty()) {
        const auto st = pq.top();
        if (st.bit) {
          a[i] = a[i] | (1 << bit_idx);
        } else {
          a[i] = a[i] & (~(1 << bit_idx));
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << a[i];
    if (i < n) cout << ' ';
  }
}