22.1.18

· · 个人记录

A

题意：

给你 n 对二维平面上的点，然后给出一个 r \times c 的矩形，保证所有的点都在矩形内部或者边上。问你能不能在线条不相交的情况下，把每对点都用曲线连接起来。

n\leq10^5

题解：

我们可以发现，只要不是两个顶点均在长方形的边上，我们就可以沿着这个线段画个轮廓线划过去，也就是说，除了那些两个顶点都在长方形边上的线段，其他的线段对答案是没有一点影响的。那么我们现在来考虑什么情况下会相交。我们可以把这个矩形的四边都标上序号，从 0 \sim 2 \times (n+m) -1 每个格点一个序号。这样，如果 i 和 j 这两条线段会相交的话，那么一定就满足条件：l_i \leq l_j \leq r_i \leq r_j。这样的话我们就先把所有的线段全部按照左端点的编号排序，这样我们就只用看看右端点了。之后我们去维护一个单调栈来保存右端点，对于第 i 条线段，先把所有的右端点编号小于 i 的左端点的线段从单调栈里删去，然后看看栈顶那个线段的右端点在不在 i 的中间，如果在话，答案就是 NO ，否则就是 YES。

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int r,c,n,m,p,q,s,t;
stack<int>st;
pair<int,int>a[1001001];
int get(int x,int y)
{
    if(x==0||y==c)
        return x+y;
    else if(y==0||x==r)
        return (r+c)*2-x-y;
    return -1;
}
signed main()
{
    freopen("connect.in","r",stdin);
    freopen("connect.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>r>>c>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p>>q>>s>>t;
        int x=get(p,q),y=get(s,t);
        if(x>y)
            swap(x,y);
        if(x>=0)
            a[++m]={x,y};
    }
    sort(a+1,a+m+1);
    for(int i=1,top=0;i<=m;i++)
    {
        while(!st.empty()&&st.top()<a[i].first)
            st.pop();
        if(!st.empty()&&st.top()<a[i].second)
        {
            cout<<"NO";
            return 0;
        }
        st.push(a[i].second);
    }
    cout<<"YES";
    return 0;
}

B

题意：

给定一颗 n 个节点的无根树，两种操作，一种操作是把第 x 条边的边权更改为 y 保证 y 是小于 x 原来的边权的，另外一种操作就是从 u 遍历到 v 每经过一条边，就把当前的 z 变为 \lfloor \dfrac{z}{a_i} \rfloor，问你最后 z 会变成什么值。

n,m\leq2 \times 10^5 z\leq10^{18}

题解：

我们不难看出， z 在经过至多 60 次非 1 操作之后就变为 0 了，所以我们可以暴力去找路径，不过如果一条边的边权是 1 的话，会很慢，我们可能走了很长一段的 1 结果 z 没有变化，所以我们可以再考虑并查集，我们维护一下目前这个节点离他最近的祖先，向他父亲那条边的边权不是 1 的节点是哪个。之后我们查询的时候先找到 u 和 v 的最近公共祖先是谁，之后暴力去跑一边每次找到目前这个节点并查集的祖先是谁，然后跳过去就好了，这样至多只会进行 60 次操作就好了。

复杂度分析：

时间复杂度：O(n \log n)

空间复杂度：O(n \log n)

代码：

// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q,dp[201001],b[201001],f[201001][20],fa[201001],val[201001],w[201001],u,v,opt,z;
vector<pair<int,int>>g[201001];
void dfs(int u,int fa,int d)
{
    dp[u]=d;
    f[u][0]=fa;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].first;
        if(v==fa)
            continue;
        dfs(v,u,d+1);
        val[v]=w[g[u][i].second];
        b[g[u][i].second]=v;
    }
}
int lca(int u,int v)
{
    if(dp[u]<dp[v])
        swap(u,v);
    int t=dp[u]-dp[v];
    for(int i=0;i<=17;i++)
        if(t&(1<<i))
            u=f[u][i];
    if(u==v)
        return u;
    for(int i=17;i>=0;i--)
        if(f[u][i]!=f[v][i])
        {
            u=f[u][i];
            v=f[v][i];
        }
    return f[u][0];
}
int fd(int x)
{
    return fa[x]==x?x:fa[x]=fd(fa[x]);
}
signed main()
{
    freopen("liveon.in","r",stdin);
    freopen("liveon.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w[i];
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=17;i++)
        for(int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
    for(int i=1;i<=n;i++)
        if(val[i]==1)
            fa[i]=f[i][0];
    val[1]=1;
    while(q--)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>u>>v>>z;
            int l=lca(u,v);
            while(u>0&&z>0)
            {
                u=fd(u);
                if(dp[u]<=dp[l])
                    break;
                z/=val[u];
                u=f[u][0];
            }
            while(v>0&&z>0)
            {
                v=fd(v);
                if(dp[v]<=dp[l])
                    break;
                z/=val[v];
                v=f[v][0];
            }
            cout<<z<<'\n';
        }
        else
        {
            cin>>v>>z;
            if(z==1)
                fa[b[v]]=f[b[v]][0];
            else
                val[b[v]]=z;
        }
    }
    return 0;
}

C

题意：