求代码复杂度
  • 板块P11244 吻秋
  • 楼主zyn0309
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/3 09:55
  • 上次更新2024/11/3 12:45:28
查看原帖
求代码复杂度
864310
zyn0309楼主2024/11/3 09:55
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,q,a[N],aa[2*N],id[25];
bool b[25];
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
signed main(){
	cin>>n>>m>>q;
	for(int i=1;i<=m;++i){
	  for(int j=1;j<=n;++j){
	  	cin>>a[(i-1)*n+j];
	  }
	  id[i]=i;
	}
	int opt,x,y;
	for(int i=1;i<=q;++i){
	  cin>>opt>>x>>y;
	  if(opt==2){
	  	cout<<a[(id[x]-1)*n+y]<<endl;
	  }
	  else{
	  	if(b[id[x]]&&b[id[y]]){
	  	  if(a[id[x]*n]<=a[(id[y]-1)*n+1])continue;
	  	  if(a[(id[x]-1)*n+1]>=a[id[y]*n]){
	  	  	swap(id[x],id[y]);
	  	  	continue;
		  }
		}
		if(!b[id[x]])sort(a+1+(id[x]-1)*n,a+1+id[x]*n);
		if(!b[id[y]])sort(a+1+(id[y]-1)*n,a+1+id[y]*n);
		int s1=1,s2=1;
		for(int j=1;j<=2*n;++j){
		  if(s1>n){
		    aa[j]=a[(id[y]-1)*n+s2];
		    ++s2;
		  }
		  else if(s2>n){
		    aa[j]=a[(id[x]-1)*n+s1];
		    ++s1;
		  }
		  else if(a[(id[y]-1)*n+s2]<a[(id[x]-1)*n+s1]){
		    aa[j]=a[(id[y]-1)*n+s2];
		    ++s2;
		  }
		  else{
		    aa[j]=a[(id[x]-1)*n+s1];
		    ++s1;
		  }
		}
		for(int j=1;j<=n;++j){
	  	  a[(id[x]-1)*n+j]=aa[j];
	  	  a[(id[y]-1)*n+j]=aa[j+n];
		}
		b[id[x]]=b[id[y]]=1;
	  }
	}
	return 0;
}
2024/11/3 09:55
加载中...