【BZOJ4399】魔法少女LJJ

  注意c<=7，然后一切都好说。

  刚开始每个点开一棵权值线段树，事先将所有的权值离散化。关于一个联通图内所有点的乘积，只要取点权的log，就能拿来直接加了，而且判断大小也很方便。

  然后用线段树的合并做。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=400010,maxv=4600000;

struct Segment_Tree
{
	int size[maxv];
	double mul[maxv];
	double tag_zero[maxv];
	int ls[maxv],rs[maxv];
	int root[maxv];
	int n,IDs;

	#define mid ((l+r)>>1)

	void Update(int x) {size[x]=size[ls[x]]+size[rs[x]];mul[x]=mul[ls[x]]+mul[rs[x]];}

	void Mark_Zero(int x) {mul[x]=0;size[x]=0;tag_zero[x]=1;}
	void Push_Down(int x)
	{
		if (tag_zero[x])
		{
			Mark_Zero(ls[x]);
			Mark_Zero(rs[x]);
			tag_zero[x]=0;
		}
	}

	void Build(int l,int r,int &x,int a,double b)
	{
		mul[x=++IDs]=b;
		size[x]=1;
		if (l==r) return;
		if (a<=mid) Build(l,mid,ls[x],a,b);
		else Build(mid+1,r,rs[x],a,b);
	}

	void Merge(int l,int r,int &x,int y)
	{
		if (x==0) {x=y;return;}
		if (y==0) return;
		if (l==r) {mul[x]+=mul[y];size[x]+=size[y];return;}
		Push_Down(x);Push_Down(y);
		if (ls[y]) Merge(l,mid,ls[x],ls[y]);
		if (rs[y]) Merge(mid+1,r,rs[x],rs[y]);
		Update(x);
	}
	
	void Change_Zero(int l,int r,int x,int a,int b)
	{
		if (l>r) return;
		if (a<=l && r<=b) {Mark_Zero(x);return;}
		Push_Down(x);
		if (a<=mid && ls[x]) Change_Zero(l,mid,ls[x],a,b);
		if (b> mid && rs[x]) Change_Zero(mid+1,r,rs[x],a,b);
		Update(x);
	}

	void Change_Add(int l,int r,int &x,int a,int b,double c)
	{
		if (x==0) x=++IDs;
		if (l==r) {size[x]+=b;mul[x]+=c*b;return;}
		Push_Down(x);
		if (a<=mid) Change_Add(l,mid,ls[x],a,b,c);
		else Change_Add(mid+1,r,rs[x],a,b,c);
		Update(x);
	}

	int Query_Kth(int l,int r,int x,int k)
	{
		while (1)
		{
			Push_Down(x);
			if (l==r) return l;
			int lsz=size[ls[x]];
			if (lsz>=k) x=ls[x],r=mid;
			else k-=lsz,x=rs[x],l=mid+1;
		}
	}
	
	int Query_Size(int l,int r,int x,int a,int b)
	{
		if (l>r) return 0;
		if (a<=l && r<=b) return size[x];
		Push_Down(x);
		int res=0;
		if (a<=mid && ls[x]) res+=Query_Size(l,mid,ls[x],a,b);
		if (b> mid && rs[x]) res+=Query_Size(mid+1,r,rs[x],a,b);
		return res;
	}

	void Build_NewRoot(int x,int a,int b) {Build(1,n,root[x],a,log2(b));}
	void Link(int a,int b) {Merge(1,n,root[a],root[b]);}
	void Mark_Up(int x,int a,int b)   {int num=(a==1)?0:Query_Size(1,n,root[x],1,a-1);if (a>1) Change_Zero(1,n,root[x],1,a-1);Change_Add(1,n,root[x],a,num,log2(b));}
	void Mark_Down(int x,int a,int b) {int num=(a==n)?0:Query_Size(1,n,root[x],a+1,n);if (a<n) Change_Zero(1,n,root[x],a+1,n);Change_Add(1,n,root[x],a,num,log2(b));}
	int Query_Kth(int x,int k) {return Query_Kth(1,n,root[x],k);}
	double Query_Mul(int x) {return mul[root[x]];}
	int Query_Size(int x) {return size[root[x]];}
}T;

struct Query {int c,a,b;}Q[maxn];

int fa[maxn];
int temp[maxn];
int n,m;

int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

int main()
{
	read(m);
	for (int i=1;i<=m;i++)
	{
		read(Q[i].c),read(Q[i].a);
		if (Q[i].c>1 && Q[i].c<7) read(Q[i].b);
		if (Q[i].c==1) temp[++n]=Q[i].a;
		if (Q[i].c==3 || Q[i].c==4) temp[++n]=Q[i].b;
	}
	sort(temp+1,temp+1+n);
	n=unique(temp+1,temp+1+n)-(temp+1);
	T.n=n;
	for (int i=1;i<=m;i++)
	{
		if (Q[i].c==1) Q[i].a=lower_bound(temp+1,temp+1+n,Q[i].a)-temp;
		if (Q[i].c==3 || Q[i].c==4) Q[i].b=lower_bound(temp+1,temp+1+n,Q[i].b)-temp;
	}
	for (int i=1,cnt=0;i<=m;i++)
	{
		int ctr=Q[i].c;
		if (ctr==1) T.Build_NewRoot(++cnt,Q[i].a,temp[Q[i].a]),fa[cnt]=cnt;
		else if (ctr==2) {if (Find(Q[i].a)!=Find(Q[i].b)) T.Link(Find(Q[i].a),Find(Q[i].b)),fa[Find(Q[i].b)]=Find(Q[i].a);}
		else if (ctr==3) T.Mark_Up(Find(Q[i].a),Q[i].b,temp[Q[i].b]);
		else if (ctr==4) T.Mark_Down(Find(Q[i].a),Q[i].b,temp[Q[i].b]);
		else if (ctr==5) printf("%d\n",temp[T.Query_Kth(Find(Q[i].a),Q[i].b)]);
		else if (ctr==6) printf("%d\n",T.Query_Mul(Find(Q[i].a))>T.Query_Mul(Find(Q[i].b))?1:0);
		else if (ctr==7) printf("%d\n",T.Query_Size(Find(Q[i].a)));
	}
	return 0;
}