
求助的内容如题。
几个猜想:
#0 不是样例 不可能的qwq
代码本身有问题,但是在本地运行的体现不出来 更玄学了
原谅我的大脑在遇到这种情况之后宕机的表现,所以有无大佬能够解释一下这个现象qwq?
顺便贴上我的代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){/*if(ch=='-')x=-1;*/ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return x*s;
}
inline void print(int x){
if(!x)return;
print(x/10),putchar(x%10^'0');
}
inline int my_max(int x,int y){
return x>y?x:y;
}
inline int my_min(int x,int y){
return x<y?x:y;
}
const int N=2e6+5;
const int M=20+5;
int n,m,q;
const int maxn=0,minn=1e7+5;
struct arrtmp{
int lin[N],maxx,minx,swapid,sorted;
}arr[M];
int type,id1,id2;int newarr[2*N+5]={};
void mymerge(int x1,int x2){//合并重组两个数组的元素,规定arr[x1].lin[n]<=arr[x2].lin[n]
int head1=1,head2=1;
while(head1<=n){
if(arr[x1].lin[head1]<=arr[x2].lin[head2])newarr[head1+head2-1]=arr[x1].lin[head1++];
else newarr[head1+head2-1]=arr[x2].lin[head2++];
}
for(int i=1;i<=n;i++){
arr[x1].lin[i]=newarr[i];
if(i<head2)arr[x2].lin[i]=newarr[i+n];
}
}
int main(){
//freopen("ans.txt","w",stdout);
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++){
arr[i].maxx=maxn,arr[i].minx=minn,arr[i].swapid=i,arr[i].sorted=0;
for(int j=1;j<=n;j++)
arr[i].lin[j]=read(),arr[i].minx=my_min(arr[i].minx,arr[i].lin[j]),arr[i].maxx=my_max(arr[i].maxx,arr[i].lin[j]);
}
while(q--){
type=read(),id1=read(),id2=read();
if(type==2){
int c=id1;
while(c!=arr[id1].swapid)id1=arr[id1].swapid;
//找爸爸,复杂度O(m),应该O(qm)不会超时的吧
print(arr[id1].lin[id2]),putchar('\n');
}
else{
int c=id1,d=id2,o0=id1,o9=id2;
while(c!=arr[id1].swapid)id1=arr[id1].swapid;
while(d!=arr[id2].swapid)id2=arr[id2].swapid;
// id1=arr[id1].swapid;id2=arr[id2].swapid;
// cout<<"id1="<<id1<<" id2="<<id2<<" ";
// id1=arr[id1].swapid;id2=arr[id2].swapid;
// for(int i=1;i<=m;i++)
// cout<<arr[i].swapid<<'-';cout<<" ";
if(!arr[id1].sorted)sort(arr[id1].lin+1,arr[id1].lin+n+1),arr[id1].sorted=1;
if(!arr[id2].sorted)sort(arr[id2].lin+1,arr[id2].lin+n+1),arr[id2].sorted=1;
// if(id1>id2)swap(id1,id2);
if(arr[id1].maxx<=arr[id2].minx){
// cout<<"type=1 "<<endl;
}else if(arr[id1].minx>=arr[id2].maxx){
// cout<<"type=2 "<<endl;
swap(arr[id1].swapid,arr[id2].swapid);
}else{
// cout<<"type=3 "<<endl;
if(arr[id1].lin[n]>arr[id2].lin[n]){
mymerge(id2,id1);swap(arr[id1].swapid,arr[id2].swapid);//前面的约束规定
}
else mymerge(id1,id2);
}
/*
这一段貌似没有应对类似于
1 3 3 3 3 3
2 2 2 3 3 3
的数据,即最大值一样且多个的情况,代码里面没有体现出来
*/
arr[id1].minx=arr[id1].lin[1],arr[id1].maxx=arr[id1].lin[n];
arr[id2].minx=arr[id2].lin[1],arr[id2].maxx=arr[id2].lin[n];
// printf("T%d:\n",q);
// for(int i=1;i<=m;i++){
// cout<<arr[i].swapid<<'-';
// for(int j=1;j<=n;j++)
// printf("%d ",arr[i].lin[j]);
// printf("min=%d max=%d",arr[i].minx,arr[i].maxx);putchar('\n');
// }putchar('\n');
}
}
// fclose(stdout);
return 0;
}
(能帮帮看一下也不错啦) 大佬轻喷