BZOJ 4399 魔法少女LJJ

题目大意

给你一个图。每次插入一个点，连接两个点，查询某个联通块内第X小，查询两个联通块内元素权值乘积关系。

这道题可以用动态开点权值线段树解决问题。比较大小因为每个点权值都是$10^9$范围的所以暴力乘起来肯定爆longlong，这时候请出我们的伙伴log()，使用log()执行判断大小的工作就可以了。

（本题又名“膜法少女Lijinnn”

细节很多，是真的多，比操作多到不知道哪里去了。 大数据结构题。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 1000000000
int T,mode,inx,iny,root[400010],fa[400010],siz[7600190],n,tot,ls[7600190],rs[7600190];
bool laz[7600190];
double sum[7600190];
void pushdown(int pos)
{
	if(laz[pos])
	{
		laz[pos]=0;
		siz[ls[pos]]=siz[rs[pos]]=sum[ls[pos]]=sum[rs[pos]]=0;
		laz[ls[pos]]=laz[rs[pos]]=1;
	}
}
int unifind(int tx){return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
void add(int &pos,int l,int r,double val,int cg,int tx)
{
	if(!pos) pos=++tot;
	siz[pos]+=cg,sum[pos]+=cg*val;
	if(l==r) return;
	pushdown(pos);
	int mid=(l+r)>>1;
	if(tx<=mid) add(ls[pos],l,mid,val,cg,tx);
	else add(rs[pos],mid+1,r,val,cg,tx);
}
int merge(int tx,int ty)
{
	if(!tx) return ty;
	if(!ty) return tx;
	siz[ty]+=siz[tx],sum[ty]+=sum[tx];
	pushdown(tx),pushdown(ty);
	ls[ty]=merge(ls[tx],ls[ty]),rs[ty]=merge(rs[tx],rs[ty]);
	return ty;
}
int lookfor(int pos,int l,int r,int tx)
{
	if(l==r) return l;
	pushdown(pos);
	int mid=(l+r)>>1;
	if(tx<=siz[ls[pos]]) return lookfor(ls[pos],l,mid,tx);
	else return lookfor(rs[pos],mid+1,r,tx-siz[ls[pos]]);
}
void del(int pos,int l,int r,int x,int y)
{
	if(!pos) return;
	if(x<=l&&r<=y)
	{
		siz[pos]=0,sum[pos]=0,laz[pos]=1;
		return;
	}
	pushdown(pos);
	int mid=(l+r)>>1;
	if(x<=mid) del(ls[pos],l,mid,x,y);
	if(y>mid) del(rs[pos],mid+1,r,x,y);
	sum[pos]=sum[ls[pos]]+sum[rs[pos]],siz[pos]=siz[ls[pos]]+siz[rs[pos]];
	return;
}
int getord(int pos,int l,int r,int x,int y)
{
	if(!pos) return 0;
	if(x<=l&&r<=y) return siz[pos];
	pushdown(pos);
	int mid=(l+r)>>1,tmp=0;
	if(x<=mid) tmp+=getord(ls[pos],l,mid,x,y);
	if(y>mid) tmp+=getord(rs[pos],mid+1,r,x,y);
	return tmp;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&mode);
		switch(mode)
		{
			case 1:scanf("%d",&inx);add(root[++n],1,maxN,log(inx),1,inx);fa[n]=n;break;
			case 2:
			{
				scanf("%d%d",&inx,&iny);
				inx=unifind(inx),iny=unifind(iny);
				if(inx!=iny) fa[inx]=iny,root[inx]=merge(root[inx],root[iny]);
				break;
			}
			case 3:
			{
				scanf("%d%d",&inx,&iny);
				inx=unifind(inx);
				int tmp=getord(root[inx],1,maxN,1,iny);
				del(root[inx],1,maxN,1,iny),add(root[inx],1,maxN,log(iny),tmp,iny);
				break;
			}
			case 4:
			{
				scanf("%d%d",&inx,&iny);
				inx=unifind(inx);
				int tmp=getord(root[inx],1,maxN,iny,maxN);
				del(root[inx],1,maxN,iny,maxN),add(root[inx],1,maxN,log(iny),tmp,iny);
				break;
			}
			case 5:
			{
				scanf("%d%d",&inx,&iny);
				printf("%d\n",lookfor(root[unifind(inx)],1,maxN,iny));
				break;
			}
			case 6:
			{
				scanf("%d%d",&inx,&iny);
				double tx=sum[root[unifind(inx)]],ty=sum[root[unifind(iny)]];
				printf("%d\n",tx>ty);
				break;
			}
			case 7:
			{
				scanf("%d",&inx);
				printf("%d\n",siz[root[unifind(inx)]]);
				break;
			}
		}
	}
	return 0;
}