【线段树合并】魔法少女LJJ

线段树

传送门：BZOJ4399

思路：

  • 首先8、9两个操作不要理
  • 对于每个连通块开一个权值线段树
  • 比较乘积用log

注意：此题卡空间，一定要动态开点

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 400030
int n,m,x,y,tot,xb,cnt,a[N][3],b[N],fa[N],rt[N],sum[N*18],ls[N*18],rs[N*18];
double LOG[N],mul[N*18];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
inline int lower(int x){
	int l=1,r=xb,mid,t;
	while (l<=r) if (b[mid=(l+r)>>1]<=x) l=(t=mid)+1; else r=mid-1;
	return t;
}
int gfa(int x){return x==fa[x]?x:fa[x]=gfa(fa[x]);}
inline void update(int cur){
	sum[cur]=sum[ls[cur]]+sum[rs[cur]];
	mul[cur]=mul[ls[cur]]+mul[rs[cur]];
}
void add(int &root,int l,int r,int x,double s,int cnt){
	if (root==0) root=++tot;
	mul[root]+=s*cnt; sum[root]+=cnt;
	if (l==r) return;
	int mid=(l+r)>>1;
	if (x<=mid) add(ls[root],l,mid,x,s,cnt);
	if (x>mid) add(rs[root],mid+1,r,x,s,cnt);
}
int del(int root,int l,int r,int L,int R){
	if (root==0) return 0;
	if (l==r){int t=sum[root]; sum[root]=mul[root]=0; return t;}//改的是root不是l 
	int mid=(l+r)>>1,t=0;;
	if (L<=mid && sum[ls[root]]) t+=del(ls[root],l,mid,L,R);
	if (R>mid && sum[rs[root]]) t+=del(rs[root],mid+1,r,L,R);
	update(root);
	return t;
}
int merge(int x,int y,int l,int r){
	if (!x) return y; if (!y) return x;
	if (l==r){sum[x]+=sum[y]; mul[x]+=mul[y]; return x;}
	int mid=(l+r)>>1;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	update(x);
	return x;
}
int kth(int root,int l,int r,int k){
	if (l==r) return l;
	int mid=(l+r)>>1;
	if (sum[ls[root]]>=k) return kth(ls[root],l,mid,k);
	else return kth(rs[root],mid+1,r,k-sum[ls[root]]);
}
	
int main(){
	m=getint();
	for (int i=1;i<=m;i++){
		a[i][0]=getint(); a[i][1]=getint();
		if (a[i][0]==1) b[++xb]=a[i][1];
		if (a[i][0]==2) a[i][2]=getint();
		if (a[i][0]==3 || a[i][0]==4){a[i][2]=getint(); b[++xb]=a[i][2];}
		if (a[i][0]==5 || a[i][0]==6) a[i][2]=getint();
	}
	sort(b+1,b+xb+1);
	for (int i=1;i<=xb;i++) LOG[i]=log(b[i]);
	for (int i=1;i<=m;i++){
		if (a[i][0]==1){//------build one new block
			n++; fa[n]=n; x=lower(a[i][1]);
			add(rt[n],1,xb,x,LOG[x],1);
		}
		if (a[i][0]==2){//------merge two blocks
			x=gfa(a[i][1]); y=gfa(a[i][2]);
			if (x==y) continue;//------judge if two blocks already in the same block
			rt[fa[x]=y]=merge(rt[x],rt[y],1,xb);
			
		}
		if (a[i][0]==3){//------change
			x=gfa(a[i][1]); y=lower(a[i][2]); cnt=0;
			cnt=del(rt[x],1,xb,1,y-1);
			if (cnt) add(rt[x],1,xb,y,LOG[y],cnt);
		}
		if (a[i][0]==4){//------change
			x=gfa(a[i][1]); y=lower(a[i][2]); cnt=0;
			cnt=del(rt[x],1,xb,y+1,xb);
			if (cnt) add(rt[x],1,xb,y,LOG[y],cnt);
		}
		if (a[i][0]==5){x=gfa(a[i][1]); y=a[i][2]; printf("%d\n",b[kth(rt[x],1,xb,y)]);}
		if (a[i][0]==6){x=gfa(a[i][1]); y=gfa(a[i][2]); printf("%d\n",mul[rt[x]]>mul[rt[y]]?1:0);}
		if (a[i][0]==7){x=gfa(a[i][1]); printf("%d\n",sum[rt[x]]);}
	}
	
	return 0;
}