LOJ #3161. 「NOI2019」I 君的探险

测试点 \(1\) 至 \(5\)：

暴力，每次改变点 \(i\) 的状态，查看 \(i + 1...n\) 哪些点状态改变了，改变了说明有边。

注意 modify 只有 \(n - 1\) 次机会，请别碰 \(n - 1\) 号结点！！

可获得 \(20\ \rm pts\)。

测试点 \(6\) 至 \(9\)：

数据保证 \(n\) 个点形成 \(n/2\) 个匹配，询问次数上界 \(n \log n\) 和 \(q \log n\)。

考虑整体二分，solve(l, r, ql, qr) 表示询问 \([ql,qr]\) 中答案在 \([l,r]\) 里，取中点 mid，每次修改 \(l...mid\)，对于询问 \(x\)，如果 \(x\in[l,mid]\) 和 \(x\) 状态改变这两个条件满足了恰好一个，说明 \(x\) 的连边在 \([l,mid]\) 中，递归到左边，其他递归到右边。

有个小问题是状态无法及时更新。即我们在修改 \([l,mid]\) 时，可能把 \([r + 1, n]\) 中的一些点状态改变了，而无法更新这个状态。没有关系，对于边 \((x,y),x<y\)，我们分治到 \(x\) 时就统计答案。

结合前面的算法可获得 \(36\ \rm pts\)。

（好像我这个做法比较烦人，但 modify 次数为上界的一半）

测试点 \(10\) 至 \(11\)

数据保证形成树且父亲结点编号比儿子小，询问次数上界 \(n \log n\) 和 \(q \log n\)。

还是整体二分，考虑询问 \(x\)，若 \(x\leq mid\) 直接分到右边，否则我们把 \([l,mid]\) modify 一次，看 \(x\) 是否为 \(1\)，是则分到左边，否则分到右边。然后再把 \([l,mid]\) modify 回来。一开始脑抽了，没发现这样写只调用了区间长度次 modify，还以为有个二倍常数过不去。

结合前面的算法可获得 \(44\ \rm pts\)。

测试点 \(12\) 至 \(14\)

数据保证形成链，询问次数限制 \(10^7\)（相当于不 TLE 就行）。

考虑按二进制位做，对于第 \(k\) 位，把该位为 \(1\) 的结点 modify。询问完再改回去。

对于该位为 \(1\) 的结点：

• 若查询的状态为 \(1\)，说明两端该位 xor 为 \(0\)。
• 若查询的状态为 \(0\)，说明两端该位 xor 为 \(1\)。

该位为 \(0\) 的结点同理。这样我们就得到一个点所连两个点的 xor。

暴力询问与 \(0\) 相连的点，然后直接递推就能得到答案了。

结合前面的算法可获得 \(56\ \rm pts\)。

测试点 \(15\) 至 \(17\)

数据保证是树，询问次数 \(10^7\)，允许 \(2m\) 次 check。

套有上面的二进制位方法可以求出每个点相邻点编号 xor 和，为了方便标号从 \(1\) 开始，\(u\) 的相邻结点异或和记做 \(p[u]\)。

我们维护一个队列 \(Q\)，初始时加入 \(1,2,3,...,n\)。

每次取出队列的 front，记做 \(u\)，通过 modify + query + modify 检查 \(u\) 和 \(p[u]\) 之间是否有边，若有边就 report，然后把 \(p[p[u]]\) 异或上 \(u\)，让 \(p[u]\) 加入队列，再令 \(p[u] = 0\)，也就是把这条边断了，一直做到队列为空。

由于某个叶子都会往上删，直到把所在连通块删完，做法正确。复杂度也是有保证的，初始 \(n\) 个点，每断一条边才会做 push 操作，也就是我们最多取 front \(n+m\) 次。

注意要判重边，因为可能有 \(u,v\) 互相删的情况。

另外我感觉使用 check 做也是 ok 的，没有仔细想。

结合前面的算法可获得 \(68\ \rm pts\)。

测试点 \(18\) 到 \(25\)（正解）

好，现在非常高兴地告诉你前面的东西和正解没关系

类似测试点 \(6\) 到 \(9\) 做整体二分，先通过 random_shuffle 随机打乱结点编号，然后每个点仿照之前的方法“找父亲”，但要注意询问点的状态要消除了已 report 的点的影响。

我们每一轮把 check = 0 的结点加入询问， random_shuffle 后做上面所述的整体二分。

证明毫无头绪，网上也没什么资料。

结合前面的算法可获得 \(100\ \rm pts\)。

代码

实现了上述所有 subtask。

#include "explore.h"
#include <bits/stdc++.h>
#define pb push_back
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;

const int N = 2e5 + 10;

namespace task1 {

int st[N];
void main(int n) {
   rep(i, 0, n - 2) {
      modify(i);
      st[i] ^= 1;
      rep(j, i + 1, n - 1) {
         if(query(j) ^ st[j]) {
            st[j] ^= 1;
            report(i, j);
         }
      }
   }
}

}

namespace task2 {

int st[N], q[N], t1[N], t2[N];
bool use[N];
void solve(int l, int r, int ql, int qr) {
   if(ql > qr || l > r) return ;
   if(l == r) {
      rep(i, ql, qr) if(!use[min(q[i], l)]) {
         use[min(q[i], l)] = 1;
         report(q[i] - 1, l - 1);
         break ;
      }
      return ;
   }
   int mid = (l + r) >> 1;
   rep(i, l, mid) modify(i - 1);
   int T1 = 0, T2 = 0;
   rep(i, ql, qr) {
      bool diff = 0;
      if(st[q[i]] ^ query(q[i] - 1)) {
         st[q[i]] ^= 1; diff = 1;
      }
      if(diff ^ (l <= q[i] && q[i] <= mid)) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n) {
   rep(i, 1, n) q[i] = i;
   solve(1, n, 1, n);
}

}

namespace task3 {

int st[N], q[N], t1[N], t2[N];
void solve(int l, int r, int ql, int qr) {
   if(ql > qr || l > r) return ;
   if(l == r) {
      rep(i, ql, qr) {
         report(l - 1, q[i] - 1);
      }
      return ;
   }
   int mid = (l + r) >> 1, T1 = 0, T2 = 0;
   rep(i, l, mid) modify(i - 1);
   rep(i, ql, qr) {
      if(q[i] <= mid || query(q[i] - 1)) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, l, mid) modify(i - 1);
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n) {
   report(0, 1);
   rep(i, 3, n) q[i] = i;
   solve(1, n, 3, n);
}

}

namespace task4 {

int p[N];
void get(int u, int la) {
   if(!(la ^ p[u])) return ;
   report(u, la ^ p[u]);
   get(la ^ p[u], u);
}
void main(int n) {
   for(int i = 0; (1 << i) < n; i ++) {
      rep(u, 0, n - 1) if(u >> i & 1) modify(u);
      rep(u, 0, n - 1) if((u >> i & 1) ^ query(u)) p[u] |= 1 << i;
      rep(u, 0, n - 1) if(u >> i & 1) modify(u);
   }
   modify(0);
   int u = -1, v = -1;
   rep(i, 1, n - 1) if(query(i)) u == -1 ? u = i : v = i;
   report(0, u); get(u, 0);
   if(~ v) {
      report(0, v); get(v, 0);
   }
}

}

namespace task5 {

int p[N];
map< pair<int, int>, bool > Map;
bool ins(int x, int y) {
   pair<int, int> p(min(x, y), max(x, y));
   if(Map[p]) return 0;
   return Map[p] = 1;
}
void main(int n) {
   for(int i = 0; (1 << i) <= n; i ++) {
      rep(u, 1, n) if(u >> i & 1) modify(u - 1);
      rep(u, 1, n) if((u >> i & 1) ^ query(u - 1)) p[u] |= 1 << i;
      rep(u, 1, n) if(u >> i & 1) modify(u - 1);
   }
   queue<int> q;
   rep(i, 1, n) q.push(i);
   while(q.size()) {
      int u = q.front(); q.pop();
      if(p[u] >= 1 && p[u] <= n && p[u] != u) {
         modify(p[u] - 1); int t = query(u - 1); modify(p[u] - 1);
         if(t && ins(u, p[u])) {
            report(u - 1, p[u] - 1);
            p[p[u]] ^= u;
            q.push(p[u]);
            p[u] = 0;
         }
      }
   }
}

}

namespace task6 {

int id[N], q[N], cnt, t1[N], t2[N];
bool use[N], st[N];
vector<int> g[N];
int calc(int u) {
   bool tg = query(id[u] - 1);
   for(int j = 0; j < (int) g[id[u]].size(); j ++) tg ^= st[g[id[u]][j]];
   return tg;
}
void solve(int l, int r, int ql, int qr) {
   if(ql > qr) return ;
   if(l == r) {
      rep(i, ql, qr) if(l != q[i]) {
         report(id[l] - 1, id[q[i]] - 1);
         g[id[l]].pb(id[q[i]]);
         g[id[q[i]]].pb(id[l]);
         cnt --;
      }
      return ;
   }
   int mid = (l + r) >> 1;
   rep(i, l, mid) if(!use[id[i]]) modify(id[i] - 1), st[id[i]] = 1;
   int T1 = 0, T2 = 0;
   rep(i, ql, qr) {
      if(q[i] <= mid || calc(q[i])) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, l, mid) if(!use[id[i]]) modify(id[i] - 1), st[id[i]] = 0;
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n, int m) {
   srand(202021);
   cnt = m;
   rep(i, 1, n) id[i] = i;
   while(cnt) {
      random_shuffle(id + 1, id + n + 1);
      int qm = 0;
      rep(i, 1, n) if(!use[id[i]]) q[++ qm] = i;
      solve(1, n, 1, qm);
      if(cnt) rep(i, 1, n) if(!use[i] && check(i - 1)) use[i] = 1;
   }
}

}

void explore(int n, int m) {
   if(n <= 500) task1::main(n);
   else if(n % 10 == 8) task2::main(n);
   else if(n % 10 == 7) task3::main(n);
   else if(n % 10 == 6) task4::main(n);
   else if(n % 10 == 5) task5::main(n);
   else task6::main(n, m);
}