感谢线段树进阶,给了我重新做人的机会。---------------某不知名OIer,Keen_z
Description
题目描述
在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味;小猴在枝头悠来荡去,好不自在;各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果;鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ还是太naive,一天,SHY带着自己心爱的图找到LJJ,对LJJ说:“既然你已经见识过动态树,动态仙人掌了,那么今天就来见识一下动态图吧” LJJ:“要支持什么操作?” SHY:“ 1.新建一个节点,权值为x。 2.连接两个节点。 3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。 4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。 5.询问一个节点a所属于的联通块内的第k小的权值是多少。 6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。 7.询问a所在联通快内节点的数量 8.若两个节点a,b直接相连,将这条边断开。 9.若节点a存在,将这个点删去。 ” LJJ:“我可以离线吗?” SHY:“可以,每次操作是不加密的,” LJJ:“我可以暴力吗?” SHY:“自重” LJJ很郁闷,你能帮帮他吗
输入格式
第一行有一个正整数m,表示操作个数。 接下来m行,每行先给出1个正整数c。 若c=1,之后一个正整数x,表示新建一个权值为x的节点,并且节点编号为n+1(当前有n个节点)。 若c=2,之后两个正整数a,b,表示在a,b之间连接一条边。 若c=3,之后两个正整数a,x,表示a联通快内原本权值小于x的节点全部变成x。 若c=4,之后两个正整数a,x,表示a联通快内原本权值大于x的节点全部变成x。 若c=5,之后两个正整数a,k,表示询问a所属于的联通块内的第k小的权值是多少。 若c=6,之后两个正整数a,b,表示询问a所属联通快内所有节点权值之积与b所属联通快内所有节点权值之积的大小, 若a所属联通快内所有节点权值之积大于b所属联通快内所有节点权值之积,输出1,否则为0。 若c=7,之后一个正整数a,表示询问a所在联通块大小 若c=8,之后两个正整数a,b,表示断开a,b所连接的边。 若c=9,之后一个正整数a,表示断开a点的所有连边 具体输出格式见样例
HINT
对100%的数据 0<=m<=400000,c<=7,所有出现的数均<=1000000000,所有出现的点保证存在 【HINT】请认真阅读题面
Solution
给了8,9两个阴间删点删边操作之后告诉你c<=7。。
一个很喵的转化,可以将连乘转化为对数之和。
将每个联通块都看作一个线段树,在其中维护权值为i的点的个数与元素对数的和。连边时将两点所在的线段树合并。
过程中要用一波并察集操作,来及时更新合并后线段树的根。
主要还是看代码吧,应该挺好理解的(挺不好调的
附去掉9 1后的样例输入,输出应为5。
code:
1 #include<bits/stdc++.h> 2 #define debug cout<<"lbwnb"<<endl 3 using namespace std; 4 const int NN=4e5+5; 5 int hal,id,c[NN],rt[NN],m,dat[NN][3],has[NN],cnt,fa[NN],s; 6 double logg[NN]; 7 inline signed read(){ 8 int x=0,f=1; 9 char ch=getchar(); 10 while(ch<'0'||ch>'9') 11 { 12 if(ch=='-') f=-1; 13 ch=getchar(); 14 } 15 while(ch<='9'&&ch>='0') 16 { 17 x=(x<<1)+(x<<3)+(ch^48); 18 ch=getchar(); 19 } 20 return x*f; 21 } 22 void write(int x){ 23 if(x<0) putchar('-'), x=-x; 24 if(x>9) write(x/10); 25 putchar(x%10+'0'); 26 } 27 int get(int x){ 28 return fa[x]==x?x:fa[x]=get(fa[x]); 29 } 30 inline int cag(int x){ 31 return lower_bound(has+1,has+1+hal,x)-has; 32 } 33 struct node{ 34 int seg,ls[NN*20],rs[NN*20],caf[NN*20],siz[NN*20]; 35 double sum[NN*20]; 36 void pushup(int x){ 37 sum[x]=sum[ls[x]]+sum[rs[x]]; 38 siz[x]=siz[ls[x]]+siz[rs[x]]; 39 } 40 void insert(int &x,int l,int r,int pos,int w){ 41 if(!x) x=++seg; 42 if(l==r){ 43 sum[x]+=logg[pos]*w; 44 siz[x]+=w; 45 return; 46 } 47 int mid=(l+r)>>1; 48 if(pos<=mid) insert(ls[x],l,mid,pos,w); 49 else insert(rs[x],mid+1,r,pos,w); 50 pushup(x); 51 } 52 int query(int x,int l,int r,int pos){ 53 if(l==r) return l; 54 int mid=(l+r)>>1; 55 if(siz[ls[x]]>=pos) return query(ls[x],l,mid,pos); 56 else return query(rs[x],mid+1,r,pos-siz[ls[x]]); 57 } 58 void marge(int &x,int y,int l,int r){ 59 if(!x||!y){ 60 x=x+y; 61 return; 62 } 63 if(l==r){ 64 siz[x]+=siz[y]; 65 sum[x]+=sum[y]; 66 return; 67 } 68 int mid=(l+r)>>1; 69 marge(ls[x],ls[y],l,mid); 70 marge(rs[x],rs[y],mid+1,r); 71 pushup(x); 72 } 73 void delet(int x,int l,int r,int opl,int opr){ 74 if(!siz[x]) return; 75 if(l==r){ 76 s+=siz[x]; 77 sum[x]=siz[x]=0; 78 return; 79 } 80 int mid=(l+r)>>1; 81 if(opl<=mid) delet(ls[x],l,mid,opl,opr); 82 if(opr>mid) delet(rs[x],mid+1,r,opl,opr); 83 pushup(x); 84 } 85 }segt; 86 int main(){ 87 m=read(); 88 for(int i=1;i<=m;i++){ 89 c[i]=read(); dat[i][1]=read(); 90 if(c[i]!=1&&c[i]!=7) dat[i][2]=read(); 91 if(c[i]==1) has[++cnt]=dat[i][1], dat[i][2]=++id; 92 if(c[i]==3||c[i]==4) has[++cnt]=dat[i][2]; 93 } 94 sort(has+1,has+cnt+1); 95 hal=unique(has+1,has+cnt+1)-(has+1); 96 for(int i=1;i<=m;i++) 97 switch(c[i]){ 98 case 1:{ 99 int x=cag(dat[i][1]); 100 logg[x]=log(dat[i][1]); 101 segt.insert(rt[dat[i][2]],1,hal,x,1); 102 fa[dat[i][2]]=dat[i][2]; 103 break; 104 } 105 case 2:{ 106 int rx=get(dat[i][1]),ry=get(dat[i][2]); 107 if(rx!=ry){ 108 fa[ry]=rx; 109 segt.marge(rt[rx],rt[ry],1,hal); 110 } 111 break; 112 } 113 case 3:{ 114 int x=cag(dat[i][2]),ro=get(dat[i][1]); 115 s=0; logg[x]=log(dat[i][2]); 116 segt.delet(rt[ro],1,hal,1,max(1,x-1)); 117 if(s) segt.insert(rt[ro],1,hal,x,s); 118 break; 119 } 120 case 4:{ 121 int x=cag(dat[i][2]),ro=get(dat[i][1]); 122 s=0; logg[x]=log(dat[i][2]); 123 segt.delet(rt[ro],1,hal,min(hal,x+1),hal); 124 if(s) segt.insert(rt[ro],1,hal,x,s); 125 break; 126 } 127 case 5:{ 128 int ro=get(dat[i][1]); 129 int ans=segt.query(rt[ro],1,hal,dat[i][2]); 130 write(has[ans]); putchar('\n'); 131 break; 132 } 133 case 6:{ 134 int r1=get(dat[i][1]),r2=get(dat[i][2]); 135 if(segt.sum[rt[r1]]>segt.sum[rt[r2]]) puts("1"); 136 else puts("0"); 137 break; 138 } 139 case 7:{ 140 int ro=get(dat[i][1]); 141 write(segt.siz[rt[ro]]); putchar('\n'); 142 break; 143 } 144 } 145 } 146 /* 147 11 148 1 2 149 1 3 150 1 4 151 1 5 152 1 6 153 2 1 2 154 2 2 3 155 2 3 4 156 2 4 5 157 3 2 5 158 5 3 4 159 */code