打卡信奥刷题（3558）用C++实现信奥题 P11244 吻秋

P11244 吻秋

题目背景

English statement. You must submit your code at the Chinese version of the statement.

秋雨刚刚亲吻过大地，白云便卷起赤橙黄绿青蓝紫。

波长在可见光范围内自由落体，让蒸腾的水汽都带上了递进的旋律。

渐变色模糊的印象总被晴天匆匆带过，但往往反常的极差让我们更加记忆犹新。

所以有序，真的最优吗？

题目描述

小 C 有

m

m

m 个整数序列

a

1

…

a

m

a_1\\dots a_m

a1​…am​，每个序列的长度都为

n

n

n。

小 C 想要把自己的序列按照整数大小排序。于是小 C 有

q

q

q 次操作，每次操作：

• 要么，小 C 给出 $x,y(x\ne y)$
• 要么，小 C 给出 $i,j$

输入格式

第一行，三个整数

n

,

m

,

q

n, m, q

n,m,q。

接下来

m

m

m 行，每行

n

n

n 个整数，第

i

i

i 行

j

j

j 个整数表示

a

i

,

j

a_{i,j}

ai,j​。

接下来

q

q

q 行，每行三个整数，描述一次操作或询问。其格式为下述两种之一：

• $\text{1 x y}$
• $\text{2 i j}$

输出格式

对于每组询问，一行一个整数，表示答案。

输入输出样例 #1

输入 #1

5 3 6
1 3 2 5 6
2 7 8 2 2
3 5 3 4 8
2 1 5
1 1 2
2 2 4
1 1 3
1 2 1
2 2 3

输出 #1

6
7
2

输入输出样例 #2

输入 #2

6 5 20
5 14 13 1 15 17
7 7 19 3 8 6
16 13 13 6 14 2
12 5 4 17 12 3
19 19 4 6 3 3
2 5 3
1 4 3
2 1 1
1 2 5
2 4 6
2 2 2
1 4 2
1 2 4
2 1 1
2 3 3
2 3 3
1 4 2
1 4 1
2 3 5
1 3 4
1 4 1
1 1 4
1 5 1
2 2 4
2 4 2

输出 #2

4
5
12
3
5
13
13
16
6
14

说明/提示

数据规模与约定

本题采用捆绑测试和子任务依赖。

因为最后两个 Subtask 的极限输入数据大小分别达到 18MB、50MB 以上，C++ 选手可以选择使用下面的 快速输入输出模板：

namespace FastIO {
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? –x : x; }
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(–x); else putchar('0'); }
template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()

不保证除了 C++ 以外的语言一定能够通过，但保证对于 C++ 语言有充足的时限。

• Subtask 0（0 pts）：样例。
• Subtask 1（9 pts）：$n\le 10^4$
• Subtask 2（23 pts）：$q\le 3000$
• Subtask 3（20 pts）：$m\le 5$
• Subtask 4（28 pts）：$q\le 4\times 10^5$
• Subtask 5（20 pts）：无特殊限制。依赖于子任务 $0\sim 4$

对于所有数据，满足

1

≤

n

⋅

m

≤

2

×

10

6

1 \\leq n\\cdot m \\leq 2\\times 10^6

1≤n⋅m≤2×106，

1

≤

m

≤

20

1 \\leq m \\leq 20

1≤m≤20，

1

≤

q

≤

5

×

10

6

1 \\leq q \\leq 5\\times 10^6

1≤q≤5×106，

1

≤

a

i

,

j

≤

10

7

1 \\leq a_{i,j} \\leq 10^7

1≤ai,j​≤107；对于操作或询问，

1

≤

x

≠

y

≤

m

1 \\leq x \\neq y \\leq m

1≤x=y≤m，

1

≤

i

≤

m

1 \\leq i \\leq m

1≤i≤m，

1

≤

j

≤

n

1 \\leq j \\leq n

1≤j≤n。

C++实现

#include<bits/stdc++.h>
using namespace std;

int n,m,q;
struct node{
int a[2000010];
}ns[22];
int id[22];
bool vis[22];
int b[4000010];

int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&ns[i].a[j]);
for(int i=1;i<=m;i++) id[i]=i;
for(int i=1;i<=q;i++){
int op,xx,yy;
scanf("%d%d%d",&op,&xx,&yy);
int x=id[xx],y=id[yy];
if(op==1){
if(vis[x]==0){
sort(ns[x].a+1,ns[x].a+1+n);
vis[x]=1;
}
if(vis[y]==0){
sort(ns[y].a+1,ns[y].a+1+n);
vis[y]=1;
}
if(ns[x].a[n]<=ns[y].a[1]) continue;
if(ns[y].a[n]<=ns[x].a[1]){
swap(id[xx],id[yy]);
continue;
}
for(int i=1,j=1;i<=n||j<=n;){
if(i<=n&&(j>n||ns[x].a[i]<ns[y].a[j])) b[i+j–1]=ns[x].a[i],i++;
else b[i+j–1]=ns[y].a[j],j++;
}
for(int i=1;i<=n;i++) ns[x].a[i]=b[i];
for(int i=1;i<=n;i++) ns[y].a[i]=b[i+n];
}else{
printf("%d\\n",ns[x].a[yy]);
}
}

return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容