QOJ 可以评测我们先考虑两个简单的 Subtask。Subtask 1k 1 k1k1。一个自然的想法是直接传这个数 1 11如果数是n nn就传1 11。也就是传( x m o d n ) 1 (x \bmod n)1(xmodn)1。Subtask 2对两个数分别执行上面的 1 11操作即可。但是两数如果在环上相邻就炸了此时我们把每个数 2 22即可。正解上面的做法启发我们把[ 1 , n ] [1,n][1,n]的值域视作首尾相连的环即n nn的后继为1 11。前两个 Subtask 的做法启发我们想到如下策略初始时R ∅ R\varnothingR∅给T TT中所有数打标记从小到大遍历T TT从T TT中每个数x xx开始找到它往后第一个未标记的数y yy标记y yy并将y yy加入R RR对于解密依然从小到大遍历只需要把以上过程中的“往后”换成“往前”即可。手玩样例发现这个策略非常对。但是直接暴力做是O ( n 2 ) O(n^2)O(n2)的。不难发现所有未标记的数最多形成k 1 k1k1个连续段。开一个set维护这些连续段即可。时间复杂度O ( ∑ k log ⁡ k ) O(\sum k\log k)O(∑klogk)。#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#defineebemplace_back#definevivectorint#definepiipairint,intusingnamespacestd;constexprintINF2e9;setpiis;constviEncode(intn,intk,vi v){vi res;s.clear();sort(v.begin(),v.end());if(v[0]1)s.emplace(1,v[0]-1);if(v[k-1]n)s.emplace(v[k-1]1,n);rep(i,0,k-1)if(v[i]1v[i1])s.emplace(v[i]1,v[i1]-1);rep(i,0,k){autoits.upper_bound({v[i],INF});if(its.end())its.begin();intlit-first,rit-second;res.eb(l);s.erase(it);if(l1r)s.emplace(l1,r);}sort(res.begin(),res.end());returnres;}constviDecode(intn,intk,vi v){vi res;s.clear();sort(v.begin(),v.end());if(v[0]1)s.emplace(1,v[0]-1);if(v[k-1]n)s.emplace(v[k-1]1,n);rep(i,0,k-1)if(v[i]1v[i1])s.emplace(v[i]1,v[i1]-1);rep(i,0,k){autoits.upper_bound({v[i],INF});if(its.begin())its.end();itprev(it);intlit-first,rit-second;res.eb(r);s.erase(it);if(lr-1)s.emplace(l,r-1);}sort(res.begin(),res.end());returnres;}