标签：13 le 颓废 int 线段 2022.8 ans dist dp

Preface

最后一天~

Content

[CF1175E]Minimal Segment Cover

给定形如 \([l,r]\) 的 \(n\) 条线段。\(m\) 次询问，询问每次至少选几条线段才能使它们的并集包含线段 \([x,y]\)。无解输出 \(-1\)。

\(1\le n,m\le 2\times 10^5,0 \le l\lt r\le 5\times 10^5,0\le x\lt y \le 5\times 10^5\)。

简单题。先从一组询问 \([x,y]\) 的情况找思路。

根据贪心的思想，发现我们首先肯定是找一条线段 \([l,r]\)，使得 \(l \le x\) 且 \(r\) 最大化，这样就覆盖上了 \([x,r]\)，转化为 \([r,y]\) 的子问题。

不难发现，这个问题其实相当于从 \(x\) 跳到某条线段 \([l,r](l\le x\le r)\) 的右端点 \(r\)，再从 \(r\) 继续往右跳，直到 \(x\ge y\)。

这个问题显然可以用倍增处理。时间复杂度 \(O((n+m)\log V)\)。

Code

写代码的时候智力下线，WA 了好几发 QAQ。

// Problem: CF1175E Minimal Segment Cover
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1175E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxm = 6e5 + 5;
int n,m,cnt,f[maxm][22];
int main() {
    cnt = 0;
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++ i) {
        int l,r;
        scanf("%d %d",&l,&r);
        f[l][0] = max(f[l][0] , r);
        cnt = max(cnt , r);
    }
    for(int i = 1;i <= cnt;++ i)f[i][0] = max(f[i][0] , f[i - 1][0]);
    for(int k = 1;k <= 20;++ k) {
        for(int i = 0;i <= cnt;++ i) {
            f[i][k] = f[f[i][k - 1]][k - 1];
        }
    }
    while(m --) {
        int x,y,ans = 0;
        scanf("%d %d",&x,&y);
        for(int k = 20;~ k;-- k) {
            if(f[x][k] < y)ans += 1 << k,x = f[x][k];
        }
        if(f[x][0] >= y)printf("%d\n",ans + 1);
        else puts("-1");
    }
    return 0;
}

[CF1009F]Dominant Indices

题解放在了长链剖分入门这篇文章里。

[CF1051F]The Shortest Statement

\(n\) 个点，\(m\) 条边的无向连通图。\(q\) 次询问，每次询问 \(x,y\) 间的最短路。

\(1\le n,m,q \le 10^5,m-n\le 20\)。

注意到 \(m-n\le 20\) 这个条件非常奇怪，它其实是在告诉我们，至多有 \(21\) 条非树边。

这样的话，至多会产生 \(42\) 个特殊节点。

\(x\to y\) 的路径只有两种可能：不经过任何一个特殊节点，或经过某个特殊节点。

那么我们把这些特殊节点选出来，跑 Dijkstra 得出最短路。

每次询问中，枚举得出 \(x\to y\) 经过每个特殊节点的最短路，和 \(x\to y\) 在树上的距离取最小值即可。

时间复杂度 \(O(n\log n+(m-n+1)\times n\log n)\)。

Code

// Problem: CF1051F The Shortest Statement
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1051F
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
typedef pair<ll,int> pii;
const ll INF = 1e14;
int head[maxn],from[maxn << 1],ver[maxn << 1],nxt[maxn << 1],dis[maxn << 1],cnt;
void add(int u,int v,int t) {
    ver[++ cnt] = v;
    from[cnt] = u;
    nxt[cnt] = head[u];
    head[u] = cnt;
    dis[cnt] = t;
    return ;
}
bool vis[maxn << 1],ins[maxn];
int n,m,f[maxn][20],lg[maxn],d[maxn];
ll dp[maxn][20],dist[45][maxn];
void dfs(int u) {
    ins[u] = true;
    for(int i = head[u];~ i;i = nxt[i]) {
        int v = ver[i],w = dis[i];
        if(ins[v])continue ;
        vis[i] = vis[i ^ 1] = true;
        f[v][0] = u;
        dp[v][0] = w;
        d[v] = d[u] + 1;
        for(int k = 1;(1 << k) <= d[v];++ k) {
            f[v][k] = f[f[v][k - 1]][k - 1];
            dp[v][k] = dp[v][k - 1] + dp[f[v][k - 1]][k - 1];
        }
        dfs(v);
    }
    return ;
}
ll calcdis(int u,int v) {
    if(d[u] < d[v])swap(u , v);
    ll ans = 0;
    for(int k = lg[d[u]];~ k;-- k) {
        if(d[u] - (1 << k) >= d[v]) {
            ans += dp[u][k];
            u = f[u][k];
        }
        if(u == v)return ans;
    }
    for(int k = lg[d[u]];~ k;-- k) {
        if(f[u][k] != f[v][k]) {
            ans += dp[u][k] + dp[v][k];
            u = f[u][k];
            v = f[v][k];
        }
    }
    return ans + dp[u][0] + dp[v][0];
}
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijkstra(int k,int s) {
    memset(vis , false , sizeof(vis));
    for(int i = 1;i <= n;++ i)dist[k][i] = INF;
    q.emplace(dist[k][s] = 0 , s);
    while(!q.empty()) {
        auto [p , u] = q.top();
        q.pop();
        if(vis[u])continue ;
        vis[u] = true;
        for(int i = head[u];~ i;i = nxt[i]) {
            int v = ver[i],w = dis[i];
            if(dist[k][v] > dist[k][u] + w) {
                dist[k][v] = dist[k][u] + w;
                q.emplace(dist[k][v] , v);
            }
        }
    }
    return ;
}
int main() {
    scanf("%d %d",&n,&m);
    memset(head , -1 , sizeof(head));
    cnt = -1;
    for(int i = 2;i <= n;++ i)lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= m;++ i) {
        int u,v,t;
        scanf("%d %d %d",&u,&v,&t);
        add(u , v , t);
        add(v , u , t);
    }
    dfs(1);
    memset(ins , false , sizeof(ins));
    for(int i = 0;i <= cnt;++ i) {
        if(vis[i]||vis[i ^ 1])continue ;
        ins[from[i]] = ins[ver[i]] = vis[i] = vis[i ^ 1] = true;
    }
    int cur = 0;
    for(int i = 1;i <= n;++ i) {
        if(ins[i])dijkstra(cur ++ , i);
    }
    int Q;
    scanf("%d",&Q);
    while(Q --) {
        int x,y;
        scanf("%d %d",&x,&y);
        ll t = calcdis(x , y);
        for(int i = 0;i < cur;++ i)t = min(t , dist[i][x] + dist[i][y]);
        printf("%lld\n",t);
    }
    return 0;
}

这是暑假的最后一天了，后面准备打一场 ABC，然后用小号玩玩 CF。

upd：ABC F 题不会摆烂，CF D 不会摆烂，哈哈，反正最后一天了。

趁着还能碰电子产品赶紧再看一会末日三问（

标签：13,le,颓废,int,线段,2022.8,ans,dist,dp
From： https://www.cnblogs.com/Royaka/p/16584679.html