WA #13 TLE#17#18#19#20
查看原帖
WA #13 TLE#17#18#19#20
713303
shining_array楼主2025/7/3 11:56

约 6KB,码风不好。

#include<bits/stdc++.h>
#define int long long	//其实这里并不需要开 long long  
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-48);
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');	
}//write12 都是 write 的复名操作  
const int N=5e5+10;	//一般的 N 的大小 但是值域要准备 两倍的量  
int idx=0;	//这里表示的是线段树的节点数目  
struct node{
	int l,r;	//节点的区间  
	int lson,rson;
	int sum;	//代表目前留下的值  
}tree[N*42];  
int rot[N*3];	//树根 类似于主席树的基本操作 
int n,q;
int nxt[N*3],lst[N*3];	//注意 nxt 和 lst 的操作方案有些不同  
int lst2[N*3];	//必须定义的内容 不然会内爆  后面已经有东西叫做 lst1 了  
//重新定义 nxt 和 lst 必须代表位置而非值 
int sum[N*3];
int sum_in[N*3],idx1=0;

//所有东西开上 3 倍空间 
void insert(int id,int place){
	int lst1=lst[id];	//直接移到末尾 
	nxt[lst1]=place;
	lst[id]=place;	//插入一个值  
	lst2[place]=lst1;	//上一个元素  
} 	//之后的函数起名为 link 
int del(int id){
	//删除 id 序列最后一个数 
	int lst1=lst[id]; 
	int lst1_1=lst2[lst1];	//这里代表倒数第二个位置 
	lst[id]=lst1_1;	//处理头节点 
	nxt[lst1_1]=0;
	lst2[lst1]=0; 
	return sum_in[lst1];
}	//改成 int 返回 lst1 更方便  
void dfs_insert(int u){
	cout<<'#'<<u<<' '<<lst[u]<<endl;
	int u1=u; 
	while(u!=0){
		cout<<u<<' ';
		u=nxt[u];
	}
	cout<<endl;
	u=u1;
	while(u!=0){
		cout<<lst2[u]<<' ';
		u=nxt[u];
	}
	cout<<endl;
	u=u1;
	while(u!=0){
		cout<<sum_in[u]<<' ';
		u=nxt[u];
	} 
	cout<<endl;
	return;
} //这里要注意一个误区:需要把整个位置搞定  
int L=1,R=1e6;	//两边的值域 大概率开不满  
void pushup(int id){
	tree[id].sum=tree[tree[id].lson].sum+tree[tree[id].rson].sum;
}
void modify(int id,int x,int y,int l,int r){	//这里是 l,r 的函数 空间应该不会有 deque 的大 
//	cout<<'#'<<id<<' '<<x<<' '<<y<<' '<<l<<' '<<r<<endl;
	// x 代表位置 y 代表具体操作 
	tree[id].l=l,tree[id].r=r;	//其实这个操作不一定有 
	if(l==r){
		tree[id].sum+=y;	//代表这里加上了一个数 y  
		return;
	} 
	int mid=l+r>>1;
	if(x<=mid){
		//往左边走 
		if(!tree[id].lson)	tree[id].lson=++idx;	//根节点不连续几乎没有影响 
		modify(tree[id].lson,x,y,l,mid); 
	} 
	else{
		if(!tree[id].rson)	tree[id].rson=++idx;
		modify(tree[id].rson,x,y,mid+1,r); 
	}
	pushup(id);
}
int idx3,q1[N];	//第三种操作需要的二分参数  
int tot=0; 
int node1[N];	//保护所在的节点 线段树  
void binary(int l,int r,int k){
	//二分求解的过程 
	int mid=l+r>>1;
//	cout<<'^'<<k<<endl; 
	//下面直接在线段树节点上查询即可 不需在线段树上重新跑 
	//还需要动态搞所在节点位置 
	while(l<r){
//		cout<<'&'<<l<<' '<<mid<<' '<<r<<' '<<k<<endl;
		int left=0;	//左节点的情况  
		//这里可能全程都搞错了  
		for(int i=1;i<=idx3;i++){
			int l3=tree[node1[i]].lson;	//代表它的左节点 这里不需要节点回收 
			left+=tree[l3].sum; 
		}
//		cout<<'#'<<left<<endl;
		if(left>=k){
			//代表往左边走 
			for(int i=1;i<=idx3;i++){
				int l3=tree[node1[i]].lson;
				node1[i]=l3;
			} 
			r=mid;
		}
		else{
			k-=left;	//这个细节不能忽略  
			for(int i=1;i<=idx3;i++){
				int r3=tree[node1[i]].rson;
				node1[i]=r3;
			}//这里不需要动态建节点??  
			l=mid+1; 
		}
		mid=l+r>>1;
//		cout<<'*'<<l<<' '<<mid<<' '<<r<<' '<<k<<endl;
	} 
	int include13=0;
	for(int i=1;i<=idx3;i++){
		include13+=tree[node1[i]].sum;	//就是目前的数值  
	}
	tot--;
	if(include13*2>tot){
		write2(mid);	//其实到这里并未结束  
	} 
	else	puts("-1");
}
int merge(int x,int y){
	//x y 是目前要合并的两个节点 
	if(!x||!y)	return x+y;	//一种比较巧妙的写法 
	tree[x].sum+=tree[y].sum;
	tree[x].lson=merge(tree[x].lson,tree[y].lson);
	tree[x].rson=merge(tree[x].rson,tree[y].rson);
	return x;	//代表最后返回的根 全程都没有懒标记  
}
void link(int x,int y){
	int lstx=lst[x];	//表尾 
	int y_0=nxt[y];		//第二个表头 
	int lsty=lst[y];	//第二个表尾 
	nxt[lstx]=y_0;
	lst2[y_0]=lstx;
	lst[x]=lsty; 
}
int qlst;
signed main(){
//	freopen("major.in","r",stdin);
//	freopen("major.out","w",stdout);
	n=read(),q=read(),qlst=q;
	for(int i=1;i<=n+q;i++){
		lst[i]=i;
	} 
	idx1=n+q;
	for(int i=1;i<=n;i++){
		rot[i]=++idx;	//代表目前位置的根 
		sum[i]=read();
		for(int j=1;j<=sum[i];j++){
//			int sum1=read();
			sum_in[++idx1]=read();
			insert(i,idx1);	//在第 i 个位置添加一个值  
			modify(rot[i],sum_in[idx1],1,L,R);	//直接把值插进去  
		} 
	} 
//	cout<<"谭总的世界-056"<<endl;
//	for(int i=1;i<=n+q;i++){
//		dfs_insert(i);
//	} 
//	for(int i=1;i<=idx1;i++){
//		cout<<sum_in[i]<<' ';
//	}
//	cout<<endl<<endl;
	while(q--){
		int op=read();
		switch(op){
			case 1:{
				int x=read(),y=read();	//在 x 的末尾增加 y 
				sum[x]++; 
				sum_in[++idx1]=y;	//将两个值赋到相等  
				insert(x,idx1); 
				modify(rot[x],sum_in[idx1],1,L,R);
				break;
			}
			case 2:{
				int x=read();
				sum[x]--;
				int ret=del(x);
//				cout<<'!'<<ret<<endl;
				modify(rot[x],ret,-1,L,R);
				break;
			}
			case 3:{
				idx3=read();
				tot=0;
				for(int i=1;i<=idx3;i++){
					q1[i]=read();
					tot+=sum[q1[i]];	//代表这里的 tot 值已经 
					node1[i]=rot[q1[i]];	//代表一开始在的位置  
				} 
				tot++; 
//				cout<<'*'<<tot<<endl;	//最后一轮为 8 其实没有任何问题 因为加了一个 1  
				binary(L,R,(tot>>1));	//tot 
				break;
			}
			//5.19KB 完成了没有操作 4 的情况!  
			case 4:{
				int x=read(),y=read(),z=read();
				rot[z]=merge(rot[x],rot[y]);//还要处理链表的情况  
				link(x,y);	//先把 x y 合并 再处理 z  
				link(z,x);
				sum[z]=sum[x]+sum[y];
				break;
			}
			//整体上即为线段树合并 + 链表合并 的全过程  
		}
	}
//	cout<<"谭总的世界-035"<<endl;
//	for(int i=1;i<=n+qlst;i++){
//		dfs_insert(i);
//	} 
//	for(int i=1;i<=idx1;i++){
//		cout<<sum_in[i]<<' ';
//	}
//	cout<<endl;
	return 0;
}//乌云在我们心里割下一块阴影 我聆听沉寂已久的心情  
2025/7/3 11:56
加载中...