我这份代码的复杂度到底是多少
  • 板块P11244 吻秋
  • 楼主CNS_5t0_0r2
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/2 20:51
  • 上次更新2024/11/2 23:21:38
查看原帖
我这份代码的复杂度到底是多少
999274
CNS_5t0_0r2楼主2024/11/2 20:51
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,M = 21;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
int n,m,q;
int a[M][N];
bool vis[M];
struct node{
	int val,pri;
	int lc,rc;
	int siz;
} t[N * M];
int node_cnt,root[M];
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x,右子树所有节点权值 > x
	if(u == 0){
		L = R = 0;
		return;
	}
	if(t[u].val <= x){
		L = u;
		split(t[u].rc,x,t[u].rc,R);
	}
	else{
		R = u;
		split(t[u].lc,x,L,t[u].lc);
	}
	t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}
void split2(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x,
	if(u == 0){
		L = R = 0;
		return;
	}
	if(t[t[u].lc].siz < x){
		L = u;
		split2(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
	}
	else{
		R = u;
		split2(t[u].lc,x,L,t[u].lc);
	}
	t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}
int merge(int u,int v){
    if(!u || !v)
        return u | v;
    if(t[u].pri < t[v].pri)
        swap(u,v);
    int l,r;
    split(v,t[u].val,l,r);
    t[u].lc = merge(t[u].lc,l);
    t[u].rc = merge(t[u].rc,r);
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
    return u;
}

void insert(int x,int id){
	int u,v;
	split(root[id],x,u,v);
	t[++node_cnt] = (node){x,rand() * node_cnt ^ id,0,0,1};
	root[id] = merge(merge(u,node_cnt),v);
}
int kth(int u,int x){
	if(x == t[t[u].lc].siz + 1)
		return t[u].val;
	if(x < t[t[u].lc].siz + 1)
		return kth(t[u].lc,x);
	else
		return kth(t[u].rc,x - t[t[u].lc].siz - 1);
}

int main(){
	srand(time(0));
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read();m = read();q = read();
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			a[i][j] = read();
			insert(a[i][j],i);
		}
	}
	while(q--){
		int op = read(),x = read(),y = read();
		if(op == 1){
			int tmp = merge(root[x],root[y]);
			split2(tmp,n,root[x],root[y]);
			vis[x] = vis[y] = true;
		}
		else if(op == 2){
			if(vis[x])
				cout << kth(root[x],y) << '\n';
			else
				cout << a[x][y] << '\n';
		}
	}
	return 0;
}

9 pts,跑得比暴力还慢。

2024/11/2 20:51
加载中...