约 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;
}//乌云在我们心里割下一块阴影 我聆听沉寂已久的心情