Description

Input

Output

Sample Input

輸入1：

5 3 1
1 4
4 2
1 5
4 3
1 3
1 4
2 4
3 2

輸入2：

10 5 4
10 3
6 9
6 3
6 8
9 5
1 8
6 4
7 3
6 2
1 10
6 9
6 8
4 5
1 9
1 5
5 2
1 3
3 2

Sample Output

輸出1：

3 1 2

輸出2：

1 5 3 4 2

Data Constraint

Solution

• 這題我打的是二維線(xiàn)段樹(shù)（樹(shù)上每個(gè)點(diǎn)代表一個(gè)矩形，將長(zhǎng)割一半作為兩個(gè)子節(jié)點(diǎn)）。

• 每條路徑 $(x,y)$ 加入二維線(xiàn)段樹(shù)的位置 $(dfn[x],dfn[y])$ 上，這里要保證 $dfn[x]<dfn[y]$ 。

• 那么我們要查詢(xún)每條路徑被哪些路徑包含，就相當(dāng)于在線(xiàn)段樹(shù)上查詢(xún)一個(gè)或兩個(gè)矩形。

• 注意查詢(xún)的時(shí)候也要保證矩形的左下角 $(x,y)$ 滿(mǎn)足 $x<y$ ，這樣避免了很多討論。

• 線(xiàn)段樹(shù)優(yōu)化連邊后跑拓?fù)渑判蚣纯伞?/p>

• 時(shí)間復(fù)雜度 $O(nlo{g}^{2}n)$ 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cctype> using namespace std; const int N=1e5+5,M=20; struct data {int l,r; }f[N*M+N]; int tot,cnt,qx,qy,qxx,qyy,qz,rt; int first[N*M],nex[N*M*M/2],en[N*M*M/2],d[N*M]; int dfn[N],size[N],fa[N][17],dep[N]; int a[N],b[N],c[N],q[N*M]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void insert1(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y;d[y]++; } void dfs(int x) {dfn[x]=++tot;size[x]=1;dep[x]=dep[fa[x][0]]+1;for(int i=first[x];i;i=nex[i])if(en[i]^fa[x][0]){fa[en[i]][0]=x;dfs(en[i]);size[x]+=size[en[i]];} } void change(int &v,int pre,int xl,int xr,int yl,int yr) {if(!v){if(xl==xr && yl==yr) v=qz; else v=++cnt;if(pre) insert1(v,pre);}if(xl==xr && yl==yr) return;if(xr-xl>yr-yl){int mid=xl+xr>>1;if(qx<=mid) change(f[v].l,v,xl,mid,yl,yr); elsechange(f[v].r,v,mid+1,xr,yl,yr);}else{int mid=yl+yr>>1;if(qy<=mid) change(f[v].l,v,xl,xr,yl,mid); elsechange(f[v].r,v,xl,xr,mid+1,yr);} } void find(int v,int xl,int xr,int yl,int yr) {if(!v) return;if(qx<=xl && xr<=qy)if(qxx<=yl && yr<=qyy){if(qz^v) insert1(v,qz);return;}if(xr-xl>yr-yl){int mid=xl+xr>>1;if(qx<=mid) find(f[v].l,xl,mid,yl,yr);if(qy>mid) find(f[v].r,mid+1,xr,yl,yr);}else{int mid=yl+yr>>1;if(qxx<=mid) find(f[v].l,xl,xr,yl,mid);if(qyy>mid) find(f[v].r,xl,xr,mid+1,yr);} } inline int lca(int x,int y) {for(int i=log2(dep[x]);i>=0;i--)if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];if(x==y) return x;for(int i=log2(dep[x]);i>=0;i--)if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0]; } int main() {freopen("stier.in","r",stdin);freopen("stier.out","w",stdout);int n=read(),m=read(),k=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}tot=0;dfs(1);for(int j=1;j<17;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];tot=0;memset(first,0,sizeof(first));cnt=m;for(int i=1;i<=m;i++){a[i]=read(),b[i]=read();if(dep[a[i]]<dep[b[i]]) swap(a[i],b[i]);c[i]=lca(a[i],b[i]);qx=dfn[a[i]];qy=dfn[b[i]];if(qx>qy) swap(qx,qy);qz=i;change(rt,0,1,n,1,n);}for(int i=1;i<=k;i++){int x=read(),y=read();insert1(x,y);}for(int i=1;i<=m;i++){qz=i;if(c[i]==b[i]){int pos=a[i];for(int j=log2(dep[pos]);j>=0;j--)if(dep[fa[pos][j]]>dep[b[i]]) pos=fa[pos][j];qx=dfn[a[i]];qy=dfn[a[i]]+size[a[i]]-1;qxx=1;qyy=dfn[b[i]]-1;if(qx>qxx) swap(qx,qxx),swap(qy,qyy);if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);qx=dfn[a[i]]+1;qy=dfn[a[i]]+size[a[i]]-1;qxx=1;qyy=dfn[pos]-1;if(qx>qxx) swap(qx,qxx),swap(qy,qyy);if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);qx=dfn[a[i]];qy=dfn[a[i]]+size[a[i]]-1;qxx=dfn[b[i]]+1;qyy=dfn[pos]-1;if(qx>qxx) swap(qx,qxx),swap(qy,qyy);if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);qx=dfn[a[i]];qy=dfn[a[i]]+size[a[i]]-1;qxx=dfn[pos]+size[pos];qyy=n;if(qx>qxx) swap(qx,qxx),swap(qy,qyy);if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);}else{if(dfn[a[i]]>dfn[b[i]]) swap(a[i],b[i]);qx=dfn[a[i]]+1;qy=dfn[a[i]]+size[a[i]]-1;qxx=dfn[b[i]];qyy=dfn[b[i]]+size[b[i]]-1;if(qx<=qy) find(rt,1,n,1,n);qx=dfn[a[i]];qy=dfn[a[i]]+size[a[i]]-1;qxx=dfn[b[i]]+1;qyy=dfn[b[i]]+size[b[i]]-1;if(qxx<=qyy) find(rt,1,n,1,n);}}int l=0,r=0;for(int i=1;i<=cnt;i++)if(!d[i]) q[++r]=i;while(l<r){int x=q[++l];if(x<=m) write(x),putchar(' ');for(int i=first[x];i;i=nex[i])if(!--d[en[i]]) q[++r]=en[i];}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5982. 【WC2019模拟12.27】路径排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。