线段树合并
壹.
什么是线段树合并？ 简单来说就是合并两棵线段树
对于当前要合并的节点 \(x,y\)
-
如果一方为空返回另一方
-
否则分别合并左右子树
int merge(int x,int y){
if(!x||!y) return x+y;
cnt(x)+=cnt(y);
//...
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
return x;
}
有时候需要到叶子结点再合并，然后 \(pushup\)
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r){
cnt(x)+=cnt(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);
pushup(x);
return x;
}
大概就是这样。
我们多数情况是在动态开点线段树中使用线段树合并，动态开点，就是非静态地开一些点， 就是一棵缺胳膊少腿的线段树，我们需要用哪个节点，再现开，很节省空间。、
嗯，很是简单，对吧，但是——
线段树合并题的难点从来不在线段树合并上(我口胡的)
贰.\(hs\)题单
\(T_A\) 雨天的尾巴
假板子。
对于暴力做法是开 \(O(N\times num)\) 的数组存每个节点存的每个物品的个数，最后每个点 \(O(num)\) 遍历求答案。这无疑会浪费很多时间空间，那么动态开点权值线段树就是处理这种情况的有力武器( \(num\) 为物品种数)
那么树上差分，最后跑子树求和的时候把子节点合并到父亲上，\(pushup\) 统计答案。
！！！警示后人
线段树合并要"及时行乐"，合并完当前节点就赶紧存储答案，因为把它往上合并时他的信息会发生改变，因为
if(!x||!y) return x+y;，我在这卡了半天，不要到最后再输出每个节点的答案。
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
#define swap(x,y) (x^=y,y^=x,x^=y)
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n,m;
int ans[N];
int qu[N],qv[N],z[N],num;
int lsh[N];
namespace GETLCA{
struct EDGE{int next,to;}e[N<<1];
int head[N],tot;
void add(int u,int v){e[++tot]={head[u],v};head[u]=tot;}
int fa[N][18],depth[N];
int lg2[N];
void dfs(int x){
depth[x]=depth[fa[x][0]]+1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa[x][0]) continue;
fa[y][0]=x;dfs(y);
}
}
void init(){
for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
for(int j=1;j<=lg2[n];j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int LCA(int u,int v){
if(depth[u]<depth[v]) swap(u,v);
int k=lg2[depth[u]-depth[v]];
for(int i=k;i>=0;i--)
if(depth[fa[u][i]]>=depth[v]) u=fa[u][i];
if(u==v) return u;
k=lg2[depth[u]];
for(int i=k;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
}using namespace GETLCA;
namespace Segment_Tree{
struct Tree{
int ls,rs,cnt,id;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define cnt(i) tr[i].cnt
#define id(i) tr[i].id
}tr[5000000];
int root[N];int sum;
void pushup(int i){
cnt(i)=max(cnt(ls(i)),cnt(rs(i)));
id(i)=cnt(ls(i))>=cnt(rs(i))?id(ls(i)):id(rs(i));
}
void create(int &i,int l,int r,int x,int k){
if(!i) i=++sum;
if(l==r){
cnt(i)+=k;
id(i)=cnt(i)?l:0;
return;
}
int mid=(l+r)>>1;
if(x<=mid) create(ls(i),l,mid,x,k);
else create(rs(i),mid+1,r,x,k);
pushup(i);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r){
cnt(x)+=cnt(y);
id(x)=cnt(x)?l:0;
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);
pushup(x);
return x;
}
void solve(int x){
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa[x][0]) continue;
solve(y);
root[x]=merge(root[x],root[y],1,num);
}
ans[x]=id(root[x]);//及时存答案！
}
}using namespace Segment_Tree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,m=read;
for(int i=1,a,b;i<n;i++){
a=read,b=read;add(a,b);add(b,a);
}
dfs(1);init();
for(int i=1;i<=m;i++) qu[i]=read,qv[i]=read,lsh[i]=z[i]=read;
sort(lsh+1,lsh+m+1);num=unique(lsh+1,lsh+m+1)-lsh-1;
for(int i=1;i<=m;i++) z[i]=lower_bound(lsh+1,lsh+num+1,z[i])-lsh;
for(int i=1;i<=m;i++){
int u=qu[i],v=qv[i];
int lca=LCA(u,v);
create(root[u],1,num,z[i],1);
create(root[v],1,num,z[i],1);
create(root[lca],1,num,z[i],-1);
create(root[fa[lca][0]],1,num,z[i],-1);
}
solve(1);
for(int i=1;i<=n;i++) write(lsh[ans[i]]),pt;
return 0;
}
\(T_B\) bzoj4636蒟蒻的数列
值域很大，考虑动态开点，然后从左右儿子更新答案，貌似不用线段树合并
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 40010
#define m 1000000000
int n;
int ans;
namespace SegmentTree{
struct Tree{
int ls,rs,k;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define k(i) tr[i].k
}tr[10000000];
int root;
int tot;
void create(int &i,int l,int r,int L,int R,int k){
if(l>R||r<L) return;
if(!i) i=++tot;
if(L<=l&&r<=R){
k(i)=max(k(i),k);
return;
}
int mid=(l+r)>>1;
create(ls(i),l,mid,L,R,k);
create(rs(i),mid+1,r,L,R,k);
return;
}
void query(int i,int l,int r){
int mid=(l+r)>>1;
if(!ls(i)) ans+=(mid-l+1)*k(i);
if(!rs(i)) ans+=(r-mid)*k(i);
if(ls(i)) k(ls(i))=max(k(ls(i)),k(i));
if(rs(i)) k(rs(i))=max(k(rs(i)),k(i));
if(ls(i)) query(ls(i),l,mid);
if(rs(i)) query(rs(i),mid+1,r);
return;
}
}using namespace SegmentTree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
int l,r,k;
for(int i=1;i<=n;i++){
l=read,r=read-1,k=read;
if(l>r) continue;
create(root,1,m,l,r,k);
}
query(root,1,m);
write(ans);
return 0;
}
\(T_C\) Promotion Counting
这才是真板子。
每个节点开一棵权值线段树，从下往上合并，查询比该节点的能力值大的牛个数即可。
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 100010
int n;
int p[N];
int t[N];
void LSH(){
sort(t+1,t+n+1);
int tt=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++)
p[i]=lower_bound(t+1,t+tt+1,p[i])-t;
}
struct Edge{int next,to;}e[N<<1];
int tot,head[N];
void add(int u,int v){
e[++tot]={head[u],v};
head[u]=tot;
}
int ans[N];
namespace SegmentTree{
int sum;
int root[N];
struct Tree{
int ls,rs;
int L,R;
int pro;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define L(i) tr[i].L
#define R(i) tr[i].R
#define pro(i) tr[i].pro
}tr[100000000];
void create(int &rt,int x,int l,int r){
if(!rt) rt=++sum;
L(rt)=l,R(rt)=r;
if(l==r){
pro(rt)=1;
return;
}
int mid=(l+r)>>1;
if(x<=mid) create(ls(rt),x,l,mid);
else create(rs(rt),x,mid+1,r);
pro(rt)=pro(ls(rt))+pro(rs(rt));
}
int merge(int x,int y){
if(!x||!y) return x+y;
pro(x)+=pro(y);
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
return x;
}
int ask(int rt,int l,int r){
if(!rt) return 0;
if(l<=L(rt)&&R(rt)<=r) return pro(rt);
int res=0,mid=(L(rt)+R(rt))>>1;
if(l<=mid) res+=ask(ls(rt),l,r);
if(r>mid) res+=ask(rs(rt),l,r);
return res;
}
void dfs(int x){
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
dfs(y);
root[x]=merge(root[x],root[y]);
}
ans[x]=ask(root[x],p[x]+1,n);
}
}using namespace SegmentTree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
for(int i=1;i<=n;i++) t[i]=p[i]=read;
LSH();
for(int i=1;i<=n;i++){
create(root[i],p[i],1,n);
}
for(int v=2;v<=n;v++){
int u=read;add(u,v);
}
dfs(1);
for(int i=1;i<=n;i++)
write(ans[i]),pt;
return 0;
}
\(T_D\) 永无乡
怎么判断两个岛的联通情况？并查集维护。
-
对于
B操作，合并两个点所在并查集对应的权值线段树。 -
对于
Q操作，查询该并查集内第 \(k\) 大点，从节点 \(i\) 出发(如果有解的话)：- 如果 \(ls(i)\) 的点数大于 \(k\)，则第 \(k\) 大点一定在左子树内，递归查询。
- 否则就是在右子树。
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 100010
int n,m;
int w[N],id[N];
int fa[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
namespace SegmentTree{
struct Tree{
int ls,rs,son;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define son(i) tr[i].son
}tr[10000000];
int cnt;
int root[N];
void create(int &i,int l,int r,int x){
if(!i) i=++cnt;
++son(i);
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) create(ls(i),l,mid,x);
else create(rs(i),mid+1,r,x);
return;
}
int merge(int x,int y){
if(!x||!y) return x+y;
son(x)+=son(y);
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
return x;
}
int ask(int i,int l,int r,int k){
if(l==r) return id[l];
int mid=(l+r)>>1;
if(son(ls(i))>=k) return ask(ls(i),l,mid,k);
else return ask(rs(i),mid+1,r,k-son(ls(i)));
}
}using namespace SegmentTree;
void link(int x,int y){
x=find(x);y=find(y);
if(x==y) return;
root[x]=merge(root[x],root[y]);
fa[y]=fa[x];
}
int ans;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,m=read;
for(int i=1;i<=n;i++){
w[i]=read;id[w[i]]=i;
fa[i]=i;
create(root[i],1,n,w[i]);
}
for(int i=1,a,b;i<=m;i++) a=read,b=read,link(a,b);
int T=read,x,y,k;
for(int t=1;t<=T;t++){
char op=getchar();while(op!='Q'&&op!='B')op=getchar();
if(op=='B') x=read,y=read,link(x,y);
else{
x=read,k=read;x=find(x);
if(son(root[x])<k) puts("-1");
else write(ask(root[x],1,n,k)),pt;
}
}
return 0;
}
\(T_E\) 魔法少女LJJ
此题不难，但是很烦。
- 操作\(1\)，动态开点
- 操作\(2\)，并查集维护，线段树合并
- 操作\(3\)，从根节点出发，访问左右子树，如果 \(mid<x\)，那么左子树显然都要变成 \(0\)(可以直接把左儿子断掉，不用\(pushdown\))，注意这是权值线段树，然后我们用 \(sum\) 记录有多少个点被赋值为 \(0\)，再将 \(x\) 处 \(update\) 即可。
- 操作\(4\)，同上。
- 操作\(5\)，类似永无乡。
- 操作\(6\)，小技巧，将 \(a\times b\) 转化为 \(log_2(a\times b)=log_2(a)+log_2(b)\)，就不会爆了，值域缩小。但是注意开 \(double\)。
- 操作\(7\)，直接查询。
- 操作\(8、9\)，线段树分裂(口胡)，我们注意到 \(c\leq 7\)，出题人无意义行为 \(\dots\)
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N=400010;
const int M=1e9+5;
int m,n;
int sum;
int fa[N];
int find(int x){
return (fa[x]==x?x:(fa[x]=find(fa[x])));
}
namespace Segment_Tree{
struct Tree{
int ls,rs,cnt;
double lgsum;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define cnt(i) tr[i].cnt
#define lgsum(i) tr[i].lgsum
}tr[5000000];
int rt[N];
int tot;
void pushup(int i){
cnt(i)=cnt(ls(i))+cnt(rs(i));
lgsum(i)=lgsum(ls(i))+lgsum(rs(i));
}
void create(int &i,int l,int r,int x){
if(!i) i=++tot;
if(l==r){
cnt(i)++;
lgsum(i)=1.0*cnt(i)*log2(l);
return;
}
int mid=(l+r)>>1;
if(x<=mid) create(ls(i),l,mid,x);
else create(rs(i),mid+1,r,x);
pushup(i);
return;
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r){
cnt(x)+=cnt(y);
lgsum(x)=1.0*cnt(x)*log2(l);
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);
pushup(x);
return x;
}
void link(int a,int b){
int A=find(a);int B=find(b);
if(A==B) return;
rt[A]=merge(rt[A],rt[B],1,M);
fa[B]=A;
}
void modify1(int i,int l,int r,int x){
if(l==r) return;
int mid=(l+r)>>1;
if(mid<x){
sum+=cnt(ls(i));ls(i)=0;
modify1(rs(i),mid+1,r,x);
}
else modify1(ls(i),l,mid,x);
pushup(i);
}
void modify2(int i,int l,int r,int x){
if(l==r) return;
int mid=(l+r)>>1;
if(mid>x){
sum+=cnt(rs(i));rs(i)=0;
modify2(ls(i),l,mid,x);
}
else modify2(rs(i),mid+1,r,x);
pushup(i);
}
void update(int &i,int l,int r,int x){
if(!i) i=++tot;
if(l==r){
cnt(i)+=sum;
lgsum(i)=1.0*cnt(i)*log2(x);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(ls(i),l,mid,x);
else update(rs(i),mid+1,r,x);
pushup(i);
}
int ask(int i,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=cnt(ls(i))) return ask(ls(i),l,mid,k);
return ask(rs(i),mid+1,r,k-cnt(ls(i)));
}
}using namespace Segment_Tree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
m=read;
for(int i=1;i<=m;i++) fa[i]=i;
int op,x,a,b,k;
for(int i=1;i<=m;i++){
op=read;
switch(op){
case 1:
x=read;
create(rt[++n],1,M,x);
break;
case 2:
a=read,b=read;
link(a,b);
break;
case 3:
a=read,x=read;
a=find(a);sum=0;
modify1(rt[a],1,M,x);
update(rt[a],1,M,x);
break;
case 4:
a=read,x=read;
a=find(a);sum=0;
modify2(rt[a],1,M,x);
update(rt[a],1,M,x);
break;
case 5:
a=read,k=read;
a=find(a);
write(ask(rt[a],1,M,k)),pt;
break;
case 6:
a=read,b=read;
a=find(a),b=find(b);
puts(lgsum(rt[a])>lgsum(rt[b])?"1":"0");
break;
case 7:
a=read;a=find(a);
write(cnt(rt[a])),pt;
break;
default:break;
}
}
return 0;
}
\(T_F\) 大根堆
\(DP\)题，先跑dfs到叶子节点，向上合并时判断是否选父节点，然后线段树上跑二分确定最大值域。
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 200010
int n;
int v[N],fa[N];
int vv[N],num;
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
namespace Segment_Tree{
struct{
int ls,rs,cnt;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define cnt(i) tr[i].cnt
}tr[5000000];
int rt[N],tot;
void create(int &i,int l,int r,int L,int R){
if(!i) i=++tot;
if(L<=l&&r<=R){
cnt(i)++;
return;
}
int mid=(l+r)>>1;
if(mid>=L) create(ls(i),l,mid,L,R);
if(mid<R) create(rs(i),mid+1,r,L,R);
return;
}
int merge(int x,int y,int l,int r){
if(cnt(x)<cnt(y)) swap(x,y);
if(!x||!y) return x+y;
cnt(x)+=cnt(y);
int mid=(l+r)>>1;
ls(x)=merge(ls(x),ls(y),l,mid);
rs(x)=merge(rs(x),rs(y),mid+1,r);
return x;
}
int ask(int i,int l,int r,int k){
if(!i) return 0;
int mid=(l+r)>>1;
int res=cnt(i);
if(k<=mid) res+=ask(ls(i),l,mid,k);
else res+=ask(rs(i),mid+1,r,k);
return res;
}
void dfs(int x){
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
dfs(y);
rt[x]=merge(rt[x],rt[y],1,num);
}
int ans1=ask(rt[x],1,num,v[x]-1)+1;
int ans2=ask(rt[x],1,num,v[x]);
if(ans1<=ans2) return;
int l=v[x],r=num,pos=v[x];
while(l<=r){
int mid=(l+r)>>1;
if(ask(rt[x],1,num,mid)<ans1){
l=mid+1;pos=mid;
}
else r=mid-1;
}
create(rt[x],1,num,v[x],pos);
return;
}
}using namespace Segment_Tree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
for(int i=1;i<=n;i++){
vv[i]=v[i]=read,fa[i]=read;
if(fa[i]) add(fa[i],i);
}
sort(vv+1,vv+n+1);
num=unique(vv+1,vv+n+1)-vv-1;
for(int i=1;i<=n;i++) v[i]=lower_bound(vv+1,vv+num+1,v[i])-vv;
dfs(1);
write(ask(rt[1],1,num,num));
return 0;
}
\(T_G\) 领导集团问题
上题多倍经验，贺了 \(shadow\) 的 \(muiltiset\) 做法，比我的做法快了 \(3\) 倍。
https://www.cnblogs.com/The-Shadow-Dragon/p/18169047
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 200010
int n;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
multiset<int>s[N];
multiset<int>::iterator it;
void merge(int x,int y){
if(s[x].size()<s[y].size()) swap(s[x],s[y]);
for(it=s[y].begin();it!=s[y].end();++it)
s[x].insert(*it);
s[y].clear();
}
void dfs(int x){
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
dfs(y);
merge(x,y);
}
s[x].insert(w[x]);
it=s[x].lower_bound(w[x]);
if(it!=s[x].begin())
s[x].erase(--it);
return;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
for(int i=1;i<=n;i++) w[i]=read;
int fa;for(int i=2;i<=n;i++) fa=read,add(fa,i);
dfs(1);
write(s[1].size());
return 0;
}
\(T_H\) 大融合
离线建树操作，跑 \(DFS\) 序。
根据 \(DFS\) 序建权值线段树，并查集维护连通状态。(未完)
$CODE$
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
#define int long long
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 100010
int n,m;
struct operate{
int op,u,v;
}q[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
bool exis[N];
int dfn[N],t;
int depth[N];
int out[N];
int id[N<<1];
void get_dfn(int x,int pre){
depth[x]=depth[pre]+1;
dfn[x]=++t;
id[t]=x;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==pre) continue;
get_dfn(y,x);
}
out[x]=t;
}
int fa[N];
int find(int x){return (fa[x]==x?x:(fa[x]=find(fa[x])));}
namespace Segment_Tree{
struct Tree{
int ls,rs,cnt;
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define cnt(i) tr[i].cnt
}tr[5000000];
int rt[N],tot;
void pushup(int i){
cnt(i)=cnt(ls(i))+cnt(rs(i));
}
void create(int &i,int l,int r,int x){
if(!i) i=++tot;
if(l==r){
cnt(i)++;
return;
}
int mid=(l+r)>>1;
if(x<=mid) create(ls(i),l,mid,x);
else create(rs(i),mid+1,r,x);
pushup(i);
return;
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x|y;
if(l==r){
cnt(x)+=cnt(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);
pushup(x);
return x;
}
int query(int i,int l,int r,int ql,int qr){
if(!i) return 0;
if(ql<=l&&r<=qr) return cnt(i);
int mid=(l+r)>>1;
int res=0;
if(ql<=mid) res+=query(ls(i),l,mid,ql,qr);
if(qr>mid) res+=query(rs(i),mid+1,r,ql,qr);
return res;
}
} using namespace Segment_Tree;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,m=read;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
char c=getchar();while(c!='A'&&c!='Q') c=getchar();
q[i].op=(c=='A'?0:1);
q[i].u=read,q[i].v=read;
exis[q[i].u]=exis[q[i].v]=1;
if(c=='A') add(q[i].u,q[i].v),add(q[i].v,q[i].u);
}
for(int i=1;i<=n;i++){
if(!exis[i]) continue;
if(!dfn[i]){
// add(0,i),add(i,0);
depth[i]=1;
get_dfn(i,0);
}
}
for(int i=1;i<=n;i++){
create(rt[i],1,t,dfn[i]);
}
for(int i=1;i<=m;i++){
int u=q[i].u,v=q[i].v;
if(depth[v]<depth[u]) swap(u,v);
int uu=find(u),vv=find(v);
if(!q[i].op){
rt[uu]=merge(rt[uu],rt[vv],1,t);
fa[vv]=uu;
}
else{
int sum=cnt(rt[uu]);
int sumv=query(rt[uu],1,t,dfn[v],out[v]);
int sumu=sum-sumv;
write(sumu*sumv);pt;
}
}
return 0;
}
\(T_I\) [base 基站选址]
不会。
$CODE$