https://codeforces.com/gym/104427

A

不是很难，显然的事情，如果终止状态两个相邻的块颜色相同，那么开始的时候他们也是这个颜色。

而其余块的颜色显然是随意的，因为联通块的边界都已经被定死了，中间的不一样大不了操作一下就行了。

时间复杂度：$O(nm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<cstring>
#define N 2100
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
char st[N][N];bool v[N][N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    fep(i,1,n){
        scanf("%s",st[i]+1);
        fep(j,1,m-1){
            if(st[i][j]!=st[i][j+1])v[i][j]=v[i][j+1]=1;
        }
    }
    fep(i,2,n){
        fep(j,1,m){
            if(st[i][j]!=st[i-1][j])v[i][j]=v[i-1][j]=1;
        }
    }
    LL ans=1;
    fep(i,1,n){
        fep(j,1,m){
            if(!v[i][j])ans=ans*2%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

B

我们不妨考虑没有双向边的图 G , 和只有双向边的图 G’ 。

显然如果 G’ 为空，那么所有点入度都不为 $0$ 为充要条件。

否则考虑 G’ 中的一个联通块，如果联通块中有一个点在 $G$ 中入度不为 $0$ ，或者是这个联通块的边数≥点数那么这个联通块显然有解，否则无解，然后实现一下即可。

时间复杂度：$O((n+m)\log n)$ 。

最优复杂度：$O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#define N 210000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL mod=1e9+7;
set<PII> fuck;
int fa[N],s1[N],s2[N],in[N];
PII a[N];int n,m,nn;
int findfa(int x){
    if(fa[x]==x)return x;
    else return fa[x]=findfa(fa[x]);
}
void mer(int x,int y){
    x=findfa(x);y=findfa(y);
    if(x==y)return ;
    fa[x]=y;s1[y]+=s1[x];s2[y]+=s2[x];
}
int main(){
    scanf("%d%d",&n,&m);
    fep(i,1,m){
        int x,y;scanf("%d%d",&x,&y);
        fuck.insert(make_pair(x,y));in[y]++;
        if(fuck.find(make_pair(y,x))!=fuck.end()){
            a[++nn]=make_pair(x,y);in[x]--;in[y]--;
        }
    }
    fep(i,1,n)fa[i]=i,s1[i]=1,s2[i]=in[i];
    fep(i,1,nn){
        int x=a[i].first,y=a[i].second;
        mer(x,y);s2[findfa(x)]++;
    }
    fep(i,1,n){
        if(fa[i]==i && s2[i]<s1[i]){printf("NO\n");return 0;}
    }
    printf("YES\n");
    return 0;
}

C

不会

D

一个很显然的事情，最终的图一定是一堆非叶节点挂着叶子节点的森林。

因为有一个非常显然的事情：

右边的方案肯定比左边的方案要优秀。

那么做法就很简单了，其实就是每个子树在处理完自己之后，需要挑选一个叶子节点送上去。

然后对于一个子树的根节点 $x$ ，其的所有儿子送上权值后，除了被挑选的权值，其余权值都需要乘以自己。

显然，对于一个子树的一个叶子节点，我们需要维护两个信息：这个叶子节点的权值，和这个子树除了这个叶子节点外的最小权值，分别记为 $A,B$ ，不难发现，当根节点面对儿子子树送上来的 $(A,B)$ 时，如果不打算送上去，其产生的贡献为：$A*val_x+B$ ，不难发现，对于儿子子树而言，其需要存储叶子节点个数的 $(A,B)$ ，同时父节点的 $val$ 对于其而言可以说是未知的，而这个统计贡献的方式又是一次函数，所以又是喜闻乐见的维护凸包时间。

那么这个时候每个节点需要干的事情就一个：维护出我自己的凸包。

对于非叶子节点，其每个儿子的凸包的 $B$ 都需要加上其他儿子的贡献，即凸包的上下移动。

而合并凸包可以正常的按秩合并，也可以直接李超线段树合并，时间复杂度都是 $log^2$ 的。

李超线段树的优势是好写，劣势也是有的，因为其的空间比较大，而且是值域线段树，一个 $log$ 是值域的，而且只能处理凸包上下移动，如果是左右移动就寄了，而且如果习惯了写凸包合并实际上也不会比李超线段树难写很多。

时间复杂度：$O(n\log^2{n})$

E

队友做的题目，赛后我自己来看一眼。

感觉确实还行，但是情况讨论比较逆天。

简单来说，这道题目有一个性质：

就是我们假设我们需要的修改的最左边的位置为 $l$ ，那么显然需要修改的最右边的位置为 $r$ 。

那么对于任意一个最优解，我们用一个最小的区间 $[a,b]$ 包住我们所有修改过的位置，则 $a=l$ 和 $b=r$ 至少有其一可以成立。

因此。我们先忽略走路的代价，然后预处理出 $[l,i]$ 和 $[i,r]$ 的最小修改代价。

然后就是处理每个区间对于 $i$ 的贡献了，这就非常的简单了。

例如 $[l,i]$ 对于 $j(j\ge l)$ 的贡献分为两种，先走到 $l$ ，再走到 $i$ ，这可以在从小到大遍历时处理，也可以先走 $i$ 再走 $l$ ，这可以从大到小遍历时枚举。

然后只要能够讨论出所有情况，这道题目就做完了。

时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<cstring>
#include<algorithm>
//#define DEBUG
#define N 1100000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
const LL inf=(LL)1e15;
char st[N];
LL C,a[N],f1[N],f2[N];
LL ans[N];
int n;
void change(LL *f,int l,int r,LL sum){f[l]+=sum;f[r+1]-=sum;}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&C);
        scanf("%s",st+1);
        int l=0,mid=0;
        fep(i,1,n){
            scanf("%lld",&a[i]);
            f1[i]=f2[i]=0;
        }
        fep(i,1,n/2){
            if(st[i]!=st[n-i+1]){l=i;break;}
        }
        feq(i,n/2,1){
            if(st[i]!=st[n-i+1]){mid=i;break;}
        }
        if(!l){
            fep(i,1,n)printf("0 ");
            printf("\n");
            continue;
        }
        #ifdef DEBUG
        printf("%s\n",st+1);
        printf("%d\n",l);
        #endif
        
        change(f1,1,mid-1,inf);change(f2,n-mid+2,n,inf);
        for(int i=l;i+i<=n;i++){
            if(st[i]==st[n-i+1])continue;
            if(a[i]<=a[n-i+1]){
                change(f1,i,n,a[i]);
                change(f2,i+1,n-i+1,a[n-i+1]);
                change(f2,1,i,a[i]);
            }
            else{
                change(f2,1,n-i+1,a[n-i+1]);
                change(f1,i,n-i,a[i]);
                change(f1,n-i+1,n,a[n-i+1]);
            }
        }
        fep(i,1,n)f1[i]+=f1[i-1],f2[i]+=f2[i-1];
        #ifdef DEBUG
        fep(i,1,n)printf("%lld %lld\n",f1[i],f2[i]);
        #endif
        int r=n-l+1;
        // fep(i,l,n-l+1)f1[i]+=(i-l)*C,f2[i]=(r-i)*C;
        LL now1=inf,now2=inf,now3=inf;
        fep(i,1,n){
            now1=min(now1,min(f1[i]-C*l,f2[i]+C*(r-i)-C*i));
            now2=min(now2,f2[i]+C*(r-i)+C*r);
            now3=min(now3,f2[i]-i*C);
            if(i>r)now2=inf;
            ans[i]=min(now1+C*i,now2-C*i);
            if(i>=r)ans[i]=min(ans[i],now3+i*C);
        }
        #ifdef DEBUG
        fep(i,1,n)printf("%lld ",ans[i]);
        printf("\n");
        #endif
        now1=inf;now2=inf;now3=inf;
        feq(i,n,1){
            now1=min(now1,f1[i]+(i-l)*C-l*C);
            now2=min(now2,min(f2[i]+r*C,f1[i]+C*(i-l)+C*i));
            now3=min(now3,f1[i]+i*C);
            if(i<l)now1=inf;
            ans[i]=min(ans[i],min(now1+i*C,now2-i*C));
            if(i<=l)ans[i]=min(ans[i],now3-i*C);
        }
        fep(i,1,n)printf("%lld ",ans[i]);
        printf("\n");
    }
    return 0;
}

F

本场最逆天的大贪心题，但实际上只要你建了个好模，能够从一个合适的角度思考，这道题目其实也不是很难。

当然，这道题目其实也有一个方法可以快速的做出来，就是你先想一个最简单的贪心，然后尝试构造数据卡掉这个贪心，然后研究一下错误的原因，想办法解决，大概率就能在较短的时间做出来这道题目。

例如：

一个比较简单的贪心，我们认为肯定是存在一个分界线，这个分界线往上都是漂亮的，往下都是不漂亮的。

这样存在数据：

1 1 1 2 3 3 3 4 4 4

这个数据应该选择 $1,2$ 作为每一段的分界点。

分析一下选两个 $1$ 和 $1,2$ 的区别在于段数的变化，

一个有四段，一个只有三段，因此，这也就引出了另外一个队伍的做法：

从小到大，根据当前已经选择的分界点和段数，判断是否还需要新增分界点，如果需要，就从最短的段中扔出一个数字作为分界点，显然的事情是这样一定存在一个方案使得我们选择的数字都是漂亮的，而且这也一定是最优方案，因为每次选择分界点都是迫不得已且已经尽可能的让段数减少了。

不过这是别的队的做法，我的做法是反过来的。

我的做法是从大到小，根据现在的分界点和段数，适当的让段数延长或者新增一个段，是反过来的。

至于上面两个做法的严谨证明，可以自行证明。

不过对于我的做法，我可以简单的阐释一下证明过程：

首先发现一个检验模型，即一个段视为 $1$ ，一个分界点视为 $-1$ ，从大到小求和，且每当和 $<1$ 时就重置为 $1$ ，这样只要求完后和为 $1$ ，那么就至少存在一个方案使得漂亮数的数量大于等于目前我们所选的漂亮数。

然后根据这个模型，我们可以证明一定存在一个最优方案使得 $sum$ 只能在最后一步才能出现重置的情况，所以我们不妨加上这个限制求最优方案。

因此，做法便为每次发现可能需要重置时，调整方案使得其不会重置，且这个过程采用贪心使其最优化。

用到的思想为：如果对于一个方案集：$S$ ，其中 $S’\subseteq S$ ，且存在最优方案使得 $x\in S’$ ，则可以把在 $S$ 上求最优方案改成在 $S’$ 上求最优方案。

贪心的证明还是那个老方法：

在算法进行的过程中，当需要我们新增段数时，我们新增了段数，显然会导致方案无效，当需要我们新增或者延长时，触发连招：

假如存在一个满足之前条件的最优方案不放在这里，那么一定存在一个满足之前条件的最优方案放在这里。显然，因为我们加入了满足之前条件这个限制，所以不会导致循环论证。

准确来说，只要你找到一个最优方案满足当前的限制条件又不会破坏之前的限制条件，就不会循环论证，而上面的调整显然调整的是一个新的漂亮数的位置，并不会影响到之前已经固定下来的漂亮数的位置，所以自然也就不会循环论证了。

说起循环论证，我一开始在做这道题目的时候方向错了，就出现了一个非常有意思的事情：

我发现了三个性质，用调整都可以证明存在一个最优方案满足这个条件，但是最尴尬的事情是我无法证明他们可以被同时满足。

即可能存在以下情况：一个最优方案，我调整了一下，满足性质 $1$ ，又调整了一下，满足了性质 $2$ ，结果不满足性质 $1$ 了，循环往复，这样就陷入了循环论证当中。

不过还好后来转换了想题思路，没过多久就想出来了，也算没坑队友太久。

时间复杂度：$O(n\log{n})$

这道题目非常有意思，刚拿起此题，都会凭借直觉想出一个简单的贪心，然后发现WA了，但是能说直觉做题法错了吗？其实也没错，因为只要你做了足够多的贪心题，你就会在想出这个贪心做法的时候感觉这个做法总会有一点点问题，问题应该是出在数字允许相同这个条件上，然后自己尝试卡一下，就会发现一个 hack 数据，在发现错误原因后，就能慢慢想出正确做法了，所以虽然一开始是错的，但是直觉做题法还是能帮助我们逐步想出正解的。

也不排除有逆天直接就想到了正确的做法，如果你直接想出了做法，请忽略上面的话。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 310000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
priority_queue<int> fuck;
int n,a[N],ans;
inline bool cmp(int x,int y){return x>y;}
int now;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        while(!fuck.empty())fuck.pop();
        ans=now=0;
        scanf("%d",&n);
        fep(i,1,n)scanf("%d",&a[i]);
        sort(a+1,a+n+1,cmp);
        int res=0;
        fep(i,1,n){
            if(a[i]!=a[i-1]){
                int x=i;while(x<n && a[x+1]==a[x])x++;
                fuck.push(x-i+1);
            }
            res--;
            if(!now){
                if(res<0 || (!res && i!=n)){
                    now=fuck.top();fuck.pop();res+=2;
                    ans++;now--;
                }
            }
            else if(now && !res)now--,res++,ans++;
            // printf("%d %d %d\n",now,res,ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}

G

非常的简单，首先让全局都变成 $2$ ，这样就变成了单点修改，然后根据需要放 $3$ 就行了。

时间复杂度：$O(nm)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
#define N 2100
using namespace std;
char st[N][N],ans[N][N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    printf("1\n");
    fep(i,1,n){
        scanf("%s",st[i]+1);
        fep(j,1,m){
            ans[i][j]='2';
            int nex=4-(i==1)-(j==1)-(i==n)-(j==m);
            if((nex&1)^(st[i][j]=='B'))ans[i][j]='3';
        }
        printf("%s\n",ans[i]+1);
    }
    return 0;
}

H

不会

I

显然，割点就走不过去了。

然后我们写了一棵圆方树，然后调了一万年，艹！

当然，实际上这道题目存在更加优秀的做法，就是直接在 $DFS$ 树上跑。

我们实际上想要知道一个点在圆方树上是在这个割点的哪个子树里面，更准确的说，是想要知道原图上某个点不经过某个割点不能走到的区域的大小。

不难发现，例如当 $x$ 是割点时，此时有三种情况。（$siz[x]$ 表示 $x$ 的子树大小，$siz’[x]$ 表示 $x$ 子树中满足 $y$ 是 $x$ 儿子且 $low[y]\geq dfn[x]$ 的 $y$ 的子树大小之和）

  1. $y$ 的祖先是 $x$ ，那么此时 $siz’[x]$ 就是不能走到的区域大小。
  2. 设 $z$ 为 $y$ 的祖先且为 $x$ 的儿子。
    1. 假设 $low[z]\ge dfn[x]$ ，则 $n-siz[z]-1$ 就是无法走到的区域大小。
    2. 假设 $low[z]<dfn[x]$ ，则 $siz’[x]$ 就是无法走到的区域大小。

然后就可以不用建出圆方树了，也就可以不用调一万年了，悲。

不过非圆方树的做法是口胡的，还没验证，有时间验证一下。

时空复杂度：$O(m+(n+q)\log{n})$。

事实上预处理一下，可以在 $O(n+m+q)$ 的时空内解决这道题目。

J

队友做的，但是我也参与讨论了。

  1. 某个颜色的被删除点对肯定是包含和被包含关系的，且如果剩下来一个数字，那一定是中间那个。
    即如果某个颜色存在点对 $(a_1,b_1),(a_2,b_2)$ ，那么一定存在关系：$a_1>a_2,b_1<b_2$ 或者反过来。
    证明方式就是如果存在违规点对，把早出现的点对变成大区间，晚出现的变成小区间，可以证明一定不劣。
    可以发现，经过这样的调整，区间长度的平方和一定减小，所以这样的调整一定会结束。
    至于只会剩下中间那个，类似证明即可。
  2. 一定存在一个最优方案使得删除顺序为长度长的优先。
    类似上面的，每次交换相邻两个点对然后证明不劣就行了。

排个序然后用树状数组维护一下就行了。

时间复杂度：$O(n\log{n})$ 。

同时也可以发现，这个做法很符合正常人的直觉：删大区间对剩下区间的影响最小，所以优先删最大的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 310000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL mod=1e9+7;
int bst[N],n;
int lowbit(int x){return x&-x;}
void change(int x,int k){
    while(x<=n)bst[x]+=k,x+=lowbit(x);
}
int findans(int x){
    int ans=0;
    while(x)ans+=bst[x],x-=lowbit(x);
    return ans;
}
vector<int> a[N];
PII b[N];int top;
inline bool cmp(PII x,PII y){return (x.second-x.first)>(y.second-y.first);}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        top=0;
        scanf("%d",&n);
        fep(i,1,n){
            int x;scanf("%d",&x);
            a[x].push_back(i);
        }
        fep(i,1,n){
            int siz=a[i].size();
            for(int j=1;j+j<=siz;j++)b[++top]=make_pair(a[i][j-1],a[i][siz-j]);
            a[i].clear();
        }
        sort(b+1,b+top+1,cmp);
        LL ans=0;
        fep(i,1,top){
            ans+=b[i].second-b[i].first-findans(b[i].second)+findans(b[i].first);
            change(b[i].first,1);change(b[i].second,1);
        }
        printf("%lld\n",ans);
        memset(bst+1,0,(n<<2));
    }
    return 0;
}

K

感觉其实还没 $F$ 难。

重点是要发现一个性质，当我连接 $i,j$ 且 $|j-i|=2$ 时，相当于直接删除了中间的数字，然后根据这个构造上界即可。

考虑从小到大遍历一个最优方案。

首先，对于 $|j-i|=1$ 的边，能连就连。(后面默认这一部分边都已经连上了)

对于 $|j-i|>1$ 的边，显然我们每次连都会导致中间的点不能再用了（因为我们从小到大遍历边的），保持遍历边的顺序不变，假如我们直接把中间点给删了，就会发现对于任意时刻的序列，对于能连的 $|j-i|=1$ 的边也都是连上的，也就是在新序列中，下一条边的 $|j-i|$ 仍然 $>1$ 。

所以我们就不难发现一个上界：$(n-1)+(n-2)=2n-3$ 。

现在我们先把 $|j-i|=1$ 的点连了，同时需要注意：序列最左边和最右边是一直不会被删除的，他们之间的连边对全局不会有影响，能连就连，不能连就算了（和 $|j-i|=1$ 的边是一个性质的）。

所以，如果序列左右两边的颜色如果相同，那么至少剩下 $3$ 个数字，不同 ，至少剩下两个数字。

然后就是讨论：

  1. $m≥3$ ，考虑每次连边删去中间的点。
    1. 那么无论任何时候，都存在一个点可以被删除（即连接其相邻的两个点）。
    2. 如果有一个颜色被删除到只剩一个，那么显然其可以向剩余所有点连边，最后会剩下三个数字。
    3. 如果序列两边两个数字不同，连边。
  2. $m=2$ ，不妨变成 $01$ 序列，定义联通块为相同颜色的区间，最大联通块是以某个位置能延申出去的最长连通块，连通块个数是最大连通块个数。
    1. 如果我们只删除一个数字，那么连通块个数不变。
    2. 连边只会导致：连通块长度减小，连通块个数减少，不会导致连通块长度增加。
    3. 因此，只删一个数字的操作次数上限为：连通块长度-1 的和。
    4. 显然，接下来只进行删除两个数字的操作是最优秀的，也显然可以办到，最终结果为 $010/101/01/10$ ，都是最优的终止状态，因此这样子操作下来就是边数的上限。

然后照着做就完了，时间复杂度：$O(n)$ 。

上面的是别的队的做法，我原来答辩到爆炸的做法在这

$m\ge 3$ 的情况，我是这么做的：

  1. 首先把每个连通块消到只剩 $1$ 个数字。
  2. 然后乱删，直到只剩下三个颜色且其中一个颜色只剩下一个数字。
  3. 然后尝试删除出现次数最多的颜色，失败，且如果出现次数第二多的颜色出现了至少两次，则删除且一定能成功，反之退出，或者直到只剩两个颜色时退出。

显然，此时终止状态不多，以 $0,1,2$ 表示（$0$ 出现次数最多，$1$ 次多，$2$ 最少，只出现了一次）：

长度为 $4$ 的：$0120$

长度为 $3$ 的：$012,021,020$

长度为 $2$ 的：$12$

然后再特判一下，就做完了。

MD，这个做法本来就答辩，打代码加思考细节就只有半个小时时间，笑死，根本写不完，然后这道题目赛时就没做出来了，不过也是我的问题，毕竟这个做法本来也是我想的，要是我能想出别的队的那个做法，估计是有可能能写出来的，毕竟他们那个做法比我的做法好写太多了。

而且我这个做法的细节处理也是有点冗杂的，实际上第 $3$ 步能改成：

1
然后尝试删除出现次数最多的颜色，失败，则删除出现次数第二多的颜色，再失败，则删除出现次数第三多的，直到只剩两个颜色时退出。

这个修改只不过是把处理终止状态的步骤和第 $3$ 步尝试删除的部分融合了，观察一下上面所剩下的终止状态就可以发现这个修改是显然正确的。

由于是赛后补的题目，所以采用的是别的队伍的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<vector>
#define N 210000
#define NN 410000
// #define DEBUG
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef pair<int,int> PII;
PII sta[NN];int top;
int n,col[N],cc[N];
struct node{
    int l,r;
}li[N];bool v[N];
void del_f(int x){li[li[x].r].l=li[x].l;li[li[x].l].r=li[x].r;}
vector<int> fuck;
bool check(int x){return !v[x] && li[x].l && li[x].r<=n && col[li[x].l]!=col[li[x].r];}
void del(int x){
    int lef=li[x].l,rig=li[x].r;
    v[x]=1;del_f(x);sta[++top]=make_pair(lef,rig);
    if(check(lef))fuck.push_back(lef);
    if(check(rig))fuck.push_back(rig);
    cc[col[x]]--;
}
void init(){
    fep(i,1,n)li[i].l=i-1,li[i].r=i+1;
    li[n+1].l=n;li[0].r=1;
}
int m;
int main(){
    #ifdef DEBUG
        freopen("std.in","r",stdin);
    #endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();top=0;
        fep(i,1,n){
            scanf("%d",&col[i]);cc[col[i]]++;
            if(i!=1 && col[i]!=col[i-1])sta[++top]=make_pair(i-1,i);
        }
        fep(i,1,n){
            if(check(i))fuck.push_back(i);
        }
        int pre=0;
        fep(i,2,n){
            if(col[i]!=col[i-1])!pre?pre=i-1:0;
            else if(pre)del(i-1);            
        }
        // #ifdef DEBUG
        // printf("%d\n",top);
        // fflush(stdout);
        // #endif
        feq(i,pre,2)del(i);
        // #ifdef DEBUG
        // printf("%d\n",top);
        // fflush(stdout);
        // #endif
        if(m==2){
            int x=li[0].r,type=1;
            while(x!=n+1){
                if(li[x].l!=li[0].r && !type)sta[++top]=make_pair(li[0].r,x);
                x=li[x].r;type^=1;
                // printf("%d\n",x);
            }
        }
        else{
            int x=0;
            while(1){
                x=fuck[fuck.size()-1];fuck.pop_back();
                if(!check(x))continue;
                if(cc[col[x]]==1)break;
                del(x);
            }
            // printf("OK\n");
            int now=li[0].r;
            while(now!=n+1){
                if(now!=x && li[now].l!=x && li[now].r!=x)sta[++top]=make_pair(now,x);
                now=li[now].r;
            }
            if(col[1]!=col[n])sta[++top]=make_pair(1,n);
        }
        printf("%d\n",top);
        fep(i,1,top)printf("%d %d\n",sta[i].first,sta[i].second);
        memset(cc+1,0,m<<2);
        // memset(col,0,sizeof(col));
        // memset(li,0,sizeof(li));
        memset(v+1,0,n);
        // memset(v,0,sizeof(v));
        // memset(sta,0,sizeof(sta));
        fuck.clear();
    }
    return 0;
}

坑

  1. 亲手写一些代码，例如：口胡或者知道做法但是没有写的题目。
  2. 把没有做的题目自己做一遍。
  3. 自己去看一遍官方题解并且补充一下官方题解的做法。
  4. 去把合并凸包的两种方式都写一遍并且写一篇博客。
  5. 补充一下线段树合并时间复杂度的证明：常规证明，和从按秩合并的角度理解的证明（刘家宁提供的角度）。