首页 > 其他分享 >Codeforces Round 864 (Div. 2) E. Li Hua and Array

Codeforces Round 864 (Div. 2) E. Li Hua and Array

时间：2023-04-10 18:01:12浏览次数：55  
标签：dep return Hua int 864 Codeforces fa maxn lca

Codeforces Round 864 (Div. 2E. Li Hua and Array)(暴力修改线段树+lca和数论的结合)

Question

Example

input
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4
output
10
2
1

Solution

首先你得知道什么是欧拉函数

  • 我们\(O(n)\)求出\([1, 5e6]\)范围内的每个数的欧拉函数后可以求一下最大的跳转次数是多少，也就是连着求几次欧拉函数之后这个数变成\(1\)，利用桶的思想做一个\(O(n)\)的递推即可知道最多跳转\(23\)次，其实就是\(\log 5e6\)次
void pre() {//筛法求欧拉函数
    for (int i = 1; i <= 5000000; i++) {
        is_prime[i] = 1;
    }
    int cnt = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    for (int i = 2; i <= 5000000; i++) {
        if (is_prime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int nxt[maxn];

void get_max_time() {
    int ans = 0;
    for (int i = 2; i <= 5000000; ++i) {
        nxt[i] = nxt[phi[i]] + 1;
        ans = max(ans, nxt[i]);
    }
    cout << ans << '\n';
}

  • 那也就是说我们进行区间修改的时候即使是逐一去跳转也只需要跳转大约\(n \times 23\)次，但我们需要快速判断这个区间是否还需要修改，这一点可以里用线段树来维护。然后还有一个问题就是如何实现查询，询问是区间内所有点跳到同一个点所需的最小次数，如果把这些跳转看成连边，其实就是这些点到他们\(lca\)的距离和。由于最深点的深度也只有\(20+\)所以倍增最多只会跳\(5\)次左右，我们可以直接在线段树上维护这个\(lca\)，我们在记一个\(ans\)数组用来直接在线段树上维护出我们要的答案，这样我们每次\(push\_up\)时就应该是如下的式子

    \[ ans[p] = (dep[lca[p << 1]] - dep[lca[p]]) * cnt[p << 1] + (dep[lca[p << 1 | 1]] - dep[lca[p]]) * cnt[p << 1 | 1] + ans[p << 1] + ans[p << 1 | 1]; \]

    也就是每次上传要把答案更新成当前区间\(lca\)到两个子区间的\(lca\)的距离并且分别乘上子区间的点的个数，在\(query\)进行求答案的时候也要进行这样的计算，本质上\(query\)也是在做一个\(push\_up\)的事情。

  • 或者也可以直接在线段树上维护每个区间最大最小的点的dfn序，这样的话区间的\(lca\)就是其中最大\(dfn\)和最小\(dfn\)的\(lca\)最后的答案是如下的式子

    \[ans=(\sum_{i=l}^r dep[i]) - (r-l+1)\times dep[lca(l\cdots r)] \]

    但是这样的话要求一个\(dfn\)序，递归会让程序慢很多但也能过，并且求答案的时候思路更简单

CODE

线段树直接维护答案

int n, m;
bool is_prime[maxn];
int phi[maxn];
int prime[maxn];
void pre() {//筛法求欧拉函数
    for (int i = 1; i <= 5000000; i++) {
        is_prime[i] = 1;
    }
    int cnt = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    for (int i = 2; i <= 5000000; i++) {
        if (is_prime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}


int a[maxn];
struct node {
    int lca, cnt, ans;
};
int dep[maxn];
int fa[maxn][6];
int lca[maxm << 2], sum[maxm << 2], ans[maxn << 2], cnt[maxm << 2];
void init_lca(int n) {
    for (int j = 1; j < 6; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int get_lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    if (u == 0) return v;
    if (v == 0) return u;
    for (int i = 5; i >= 0; --i)
        if (dep[v] - dep[u] >= (1 << i))
            v = fa[v][i];
    if (u == v) return u;
    for (int i = 5; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}


void push_up(int p) {
    cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
    lca[p] = get_lca(lca[p << 1], lca[p << 1 | 1]);
    ans[p] = (dep[lca[p << 1]] - dep[lca[p]]) * cnt[p << 1] + (dep[lca[p << 1 | 1]] - dep[lca[p]]) * cnt[p << 1 | 1]  + ans[p << 1] + ans[p << 1 | 1];
}
void build(int p, int l, int r) {
    if (l == r) {
        lca[p] = a[l];
        sum[p] = dep[a[l]];
        cnt[p] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}

void update(int p, int l, int r, int ql, int qr) {
    if (!sum[p]) return ;
    if (l == r) {
        sum[p]--;
        lca[p] = fa[lca[p]][0];
        return ;
    }
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr);
    push_up(p);
}

node query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {lca[p], cnt[p], ans[p]};
    node L = {0, 0, 0}, R = {0, 0, 0};
    int mid = l + r >> 1;
    node ans = {0, 0, 0};
    if (ql <= mid) {
        L = query(p << 1, l, mid, ql, qr);
    }
    if (mid < qr) {
        R = query(p << 1 | 1, mid + 1, r, ql, qr);
    }
    ans.lca = get_lca(L.lca, R.lca);
    ans.cnt = L.cnt + R.cnt;
    if (L.lca) {
        ans.ans += L.ans + L.cnt * (dep[L.lca] - dep[ans.lca]);
    }
    if (R.lca) {
        ans.ans += R.ans + R.cnt * (dep[R.lca] - dep[ans.lca]);
    }
    return ans;
}

int nxt[maxn];

void get_max_time() {
    int ans = 0;
    for (int i = 2; i <= 5000000; ++i) {
        nxt[i] = nxt[phi[i]] + 1;
        ans = max(ans, nxt[i]);
    }
    cout << ans << '\n';
}

void solve(int cas) {
    pre();
    // get_max_time();
    for (int i = 2; i <= 5000000; ++i) {
        fa[i][0] = phi[i];
        dep[i] = dep[phi[i]] + 1;
    }
    init_lca(5000000);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            update(1, 1, n, l, r);
        } else {
            cout << query(1, 1, n, l, r).ans << '\n';
        }
    }
}

通过dfn序求lca

//省略了筛法求欧拉函数
int a[maxn];
vector<int> e[maxn];
int dep[maxn];
int fa[maxn][6];
int sum[maxm << 2], cnt[maxm << 2], mx[maxm << 2], mn[maxm << 2];
int dfn, in[maxn], id[maxn];
 
 
void dfs(int u) {
    in[u] = ++dfn;
    id[dfn] = u;
    for (int v : e[u])
        dfs(v);
}
 
 
void init_lca(int n) {
    for (int j = 1; j < 6; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int get_lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    if (u == 0) return v;
    if (v == 0) return u;
    for (int i = 5; i >= 0; --i)
        if (dep[v] - dep[u] >= (1 << i))
            v = fa[v][i];
    if (u == v) return u;
    for (int i = 5; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
 
 
void push_up(int p) {
    cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}
 
void build(int p, int l, int r) {
    if (l == r) {
        sum[p] = dep[a[l]];
        cnt[p] = 1;
        mx[p] = mn[p] = in[a[l]];
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}
 
void update(int p, int l, int r, int ql, int qr) {
    if (!sum[p]) return ;
    if (l == r) {
        sum[p]--;
        int ID = id[mx[p]];
        ID = phi[ID];
        mx[p] = in[ID];
        mn[p] = in[ID];
        return ;
    }
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr);
    push_up(p);
}
 
pii query_m(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {mx[p], mn[p]};
    int mid = l + r >> 1;
    pii ans = {0, INF};
    if (ql <= mid) {
        pii L = query_m(p << 1, l, mid, ql, qr);
        ans.fir = max(L.fir, ans.fir); ans.sec = min(L.sec, ans.sec);
    }
    if (mid < qr) {
        pii R = query_m(p << 1 | 1, mid + 1, r, ql, qr);
        ans.fir = max(R.fir, ans.fir); ans.sec = min(R.sec, ans.sec);
    }
    return ans;
}
 
pii query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {sum[p], cnt[p]};
    int mid = l + r >> 1;
    pii ans = {0, 0};
    if (ql <= mid) {
        pii L = query(p << 1, l, mid, ql, qr);
        ans.fir += L.fir; ans.sec += L.sec;
    }
    if (mid < qr) {
        pii R = query(p << 1 | 1, mid + 1, r, ql, qr);
        ans.fir += R.fir; ans.sec += R.sec;
    }
    return ans;
}
 
void solve(int cas) {
    cin >> n >> m;
    pre();
    for (int i = 2; i <= 5000000; ++i) {
        fa[i][0] = phi[i];
        e[phi[i]].pb(i);
        dep[i] = dep[phi[i]] + 1;
    }
    dfs(1);
    init_lca(5000000);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            update(1, 1, n, l, r);
        } else {
            pii res = query(1, 1, n, l, r);
            pii k = query_m(1, 1, n, l, r);
            int lca = get_lca(id[k.fir], id[k.sec]);
            cout << res.fir - dep[lca] * res.sec << '\n';
        }
    }
}

标签：dep,return,Hua,int,864,Codeforces,fa,maxn,lca
From： https://www.cnblogs.com/Fighoh/p/17303778.html

相关文章

  • Codeforces Round 863 (Div. 3)
    题解报告基本的一些理解和问题都在注释中A：InsertDigit找到第一个小于输入数字的数的位置塞进去就好了，可以细推，但是粗略想想也能知道#include<bits/stdc++.h>usingnamespacestd;intmain(void){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int......
  • Codeforces Round 865 (Div. 2)
    CodeforcesRound865(Div.2)A.IanVisitsMaryvoidsolve(){intx=read(),y=read();if(__gcd(y,x)!=1){cout<<2<<endl;cout<<1<<""<<y-1<<endl;cout<<x<<"&q......
  • Codeforces Round 864 (Div. 2) C和D
    比赛地址C.LiHuaandChess题意：给出一个棋盘长宽n,m，有一颗棋子在棋盘上，向八个方向走一步的路程代价都为1，现在进行最多3次询问，问能否确认棋子的位置Solution第一次做交互题，想很好想，先询问(1,1)，得到x，再询问(1+x,1+x)，得到y，最后询问(1+x,1+x-y)，如果得到的是0，则输出这个点，反之输......
  • 练习记录-cf-div2-864（A-D)
    状态不怎么好场上就写出3道还磨磨蹭蹭推错结论qwq 警钟长鸣A.LiHuaandMaze一开始以为要切割发现就把其中一个包起来就行了计算包某个块需要的最小块数#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)usingn......
  • Codeforces Round 860 (Div. 2)
    CodeforcesRound860(Div.2)Date:04/08/2023Link:CodeforcesRound860(Div.2)A|ShowstopperBrief:两组数\(\{a_i\}\)和\(\{b_i\}\)，长度都为\(n\).\(\foralli\),可以交换\(a_i\)和\(b_i\),问是否可以使得\(a_n=\max(a_i)\),\(b_n=\max(b_i......
  • 【cf864】赛后结
    属实是失踪人口了，想了一下还是把题解打到这儿。conteset地址：https://codeforces.com/contest/1797 A.题目大意：n*m的方格上给两个点，询问最少增加的障碍格子使得这两个点不连通。解题思路：水题，但是手速有点慢。直接问靠不靠墙，靠几面墙，不靠墙答案4，靠一面答案3，靠两面答案2，取两个点......
  • Codeforces Round 864 (Div. 2)
    评价：A~E感觉出的挺一般，特别是D怎么放这种暴力题，场上我还没调出来，F没看。但是Orzrui_er。A在一个点周围放障碍即可。B求出最少需要的操作次数\(p\)，若\(p>k\)就无解，否则若\(n\)为偶数只能任选一个格子翻偶数次，即有解当且仅当\(2\mid(k-p)\)；若\(n\)为奇数可......
  • 热点网络统计 huawei od
    本期题目：热点网络统计题目企业路由器的统计页面，有一个功能，需要动态统计公司访问最多的网页URLtopN请设计一个算法，可以高效动态统计TopN的页面输入每一行都是一个URL或一个数字如果是URL代表一段时间内的网页访问如果是一个数字N 代表本次需要输出的TopN个URL 输入约束:......
  • Edu Round 板刷计划 4. Educational Codeforces Round 4 题解
    ChangeLog:2023.04.06开坑.A-TheTextSplitting弱智题.枚举分出来多少个长度为\(p\)的串，则能计算出长度为\(q\)的串有多少个，若合法则直接输出即可.无解输出-1.Samplesubmission.B-HDDisOutdatedTechnology比A还弱智.直接记录每个数的位置，然后模拟一......
  • codeforces 1804D Accommodation
    https://codeforces.com/problemset/problem/1804/D解题思路每个楼层是独立的，考虑怎么解决一层就可以了。求最大值就是尽量避免1和1合并，也就是尽量在不存在连续1的子序列中进行合并，如果还有需要合并的就只能用1和1合并。求最小值就是尽量合并1和1。由于只需要输出最大最小值，所......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99