【三维偏序】送信

题目

https://gmoj.net/senior/#contest/show/3227/3

思路

一开始我以为这不是一棵树，想了半天不知道怎么做……

这个东西显然可以转换成dfs序上的二维偏序，加时间1维就3维，cdq随便做

代码

#include
#define ll long long
using namespace std;
const int N=1e5+77;
struct node
{int X,Y1,Y2,s,t;
} a[N<<4];
struct E
{int to,next;
}e[N<<4];
int b[N<<4],c[N<<4],ls[N],bg[N],ed[N],fa[N][17],d[N],ans[N],n,m,Q,Cnt,x,y,z,Lca,tp,tot,j;
char st[21],ch;
namespace T
{int tr[N],d[N],tot,i,j,k,l;bool bz[N];void clear(){for(int i=1; i<=tot; i++) tr[d[i]]=bz[d[i]]=0;tot=0;}void ins(int t,int s){while(t<=n) {if(!bz[t]) bz[t]=1,d[++tot]=t; tr[t]+=s,t+=t&-t;};}int query(int t) {int ans=0; while(t) ans+=tr[t],t-=t&-t; return ans;}
}
void add(int u,int v)
{++Cnt; e[Cnt].to=v; e[Cnt].next=ls[u]; ls[u]=Cnt;
}
void dfs(int Fa,int t)
{d[t]=d[Fa]+1,fa[t][0]=Fa;for(int i=1; i<=16; i++) fa[t][i]=fa[fa[t][i-1]][i-1];bg[t]=++j;for(int i=ls[t]; i; i=e[i].next) if(e[i].to!=Fa) dfs(t,e[i].to);ed[t]=j;
}int work(int x,int y)
{for(int i=16; i>=0; i--) if(d[x]<d[fa[y][i]]) y=fa[y][i];return y;
}
int lca(int x,int y)
{if(d[x]<d[y]) swap(x,y);for(int i=16; i>=0; i--) if(d[fa[x][i]]>=d[y]) x=fa[x][i];for(int i=16; i>=0; i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];if(x!=y) x=fa[x][0];return x;
}void ins(int X1,int Y1,int X2,int Y2,int s)
{++tot,a[tot]={X1,X2,Y2,s,tot};++tot,a[tot]={Y1+1,X2,Y2,-s,tot};
}
void Add(int x,int y)
{Lca=lca(x,y);if(Lca==x)z=work(x,y),ins(1,n,bg[y],ed[y],1),ins(bg[z],ed[z],bg[y],ed[y],-1);elseif(Lca==y)z=work(y,x),ins(bg[x],ed[x],1,n,1),ins(bg[x],ed[x],bg[z],ed[z],-1);elseins(bg[x],ed[x],bg[y],ed[y],1);
}bool cmp(int x,int y) {return a[x].X<a[y].X || a[x].X==a[y].X && a[x].Y2>a[y].Y2;}
void solve(int l,int r)
{int i,j,k,mid=(l+r)/2;if(l==r) return;solve(l,mid),solve(mid+1,r);i=l,j=mid+1,k=l;while(i<=mid && j<=r){if(j>r || i<=mid && cmp(b[i],b[j])) c[k++]=b[i++];else c[k++]=b[j++];}while(i<=mid) c[k++]=b[i++];while(j<=r) c[k++]=b[j++];for(int i=l; i<=r; i++) b[i]=c[i];T::clear();for(int i=l; i<=r; i++)if(a[b[i]].X<=n){if(a[b[i]].t<=mid && a[b[i]].Y2>0)T::ins(a[b[i]].Y1,a[b[i]].s),T::ins(a[b[i]].Y2+1,-a[b[i]].s);elseif(a[b[i]].t>mid && a[b[i]].Y2<0)ans[-a[b[i]].Y2]+=T::query(a[b[i]].Y1);}else break;
}int main()
{freopen("letter.in","r",stdin); freopen("letter.out","w",stdout);scanf("%d%d%d",&n,&m,&Q);for(int i=1; i<n; i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);j=0;dfs(0,1);for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),Add(x,y);int l=0;for(int i=1; i<=Q; i++){scanf("%d%d%d",&tp,&x,&y);if(tp==1){++l,++tot,a[tot]={bg[x],bg[y],-l,0,tot};++tot,a[tot]={bg[y],bg[x],-l,0,tot};}elseAdd(x,y);}for(int i=1; i<=tot; i++) b[i]=i;solve(1,tot);for(int i=1; i<=l; i++) printf("%d\n",ans[i]);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！