专栏文章

题解：P5278 算术天才⑨与等差数列

BBlackPanda
P5278题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miohr3yn
此快照首次捕获于
2025/12/02 19:24
3 个月前
此快照最后确认于
2025/12/02 19:24
3 个月前
查看原文
首先考虑等差数列性质。一段区间 [l,r][l,r] 排序后记为 aa，当且仅当 aa 满足如下条件时，称 aa 为公差为 dd 的等差数列。
  • max⁡ai=min⁡ai+d×(r−l+1)\max{a_i}=\min{a_i} + d\times (r-l+1)
  • gcd⁡i=l+1rai−ai−1=d\gcd\limits_{i=l+1}^{r}{a_i-a_{i-1}} = d
  • aa 中无重复元素
对于前两个条件，我们可以用两棵线段树分别维护序列 aa 的区间最值和 aa 的差分序列的区间 gcd⁡\gcd。
对于第三个条件，可以在线段树上维护序列每个元素的前驱（上次出现的位置）， 操作 22 查询一下前驱的区间最大值，如果最大值不小于 ll，则 [l,r][l,r] 区间内某个值有重复。反之无重复。
操作 11 单点修改时，二分查询一下 axa_x 在 xx 后下一次出现的位置 nxtnxt，将 nxtnxt 的前驱更新成 xx 的前驱。最后把新值 yy 更新到序列中，并同步更新 yy 对应相邻位置的前驱即可。
需要注意本题空间限制以及公差为 00 的情况。
CPP
int n, m;
int a[N];
int lst[N];
map<int, set<int> > pos;
/*====================*/
struct Ans {
    int maxv, minv;
    LL sum;
};
struct Tree {
    int l, r;
    int val, maxv, minv;
    LL maxl;
} tree[N << 2];
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void PushUp(int p) {
    tree[p].val = tree[ls(p)].val + tree[rs(p)].val;
    tree[p].maxv = max(tree[ls(p)].maxv, tree[rs(p)].maxv);
    tree[p].maxl = max(tree[ls(p)].maxl, tree[rs(p)].maxl);
    tree[p].minv = min(tree[ls(p)].minv, tree[rs(p)].minv);
}
void Build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        tree[p].maxv = tree[p].minv = tree[p].val = a[l];
        tree[p].maxl = lst[l];
    } else {
        int mid = (l + r) >> 1;
        Build(ls(p), l + 0, mid);
        Build(rs(p), mid + 1, r);
        PushUp(p);
    }
}
void Change(int p, int x, int d) {
    if (tree[p].l == tree[p].r) {
        tree[p].maxv = tree[p].minv = tree[p].val = d;
    } else {
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (x <= mid)Change(ls(p), x, d);
        if (mid < x) Change(rs(p), x, d);
        PushUp(p);
    }
}
void pChange(int p, int x) {
    if (tree[p].l == tree[p].r) {
        tree[p].maxl = lst[x];
    } else {
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (x <= mid)pChange(ls(p), x);
        if (mid < x) pChange(rs(p), x);
        PushUp(p);
    }
}
Ans Ask(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return (Ans) { tree[p].maxv, tree[p].minv, tree[p].val };
    } else {
        int resmx = -1, resmi = inf;
        LL res = 0;
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (l <= mid) {
            Ans ans = Ask(ls(p), l, r);
            resmx = max(resmx, ans.maxv);
            resmi = min(resmi, ans.minv);
            res += ans.sum;
        }
        if (mid < r) {
            Ans ans = Ask(rs(p), l, r);
            resmx = max(resmx, ans.maxv);
            resmi = min(resmi, ans.minv);
            res += ans.sum;
        }
        return { resmx, resmi, res };
    }
}
int pAsk(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].maxl;
    } else {
        int res = -inf;
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (l <= mid) {
            res = max(res, pAsk(ls(p), l, r));
        }
        if (mid < r) {
            res = max(res, pAsk(rs(p), l, r));

        }
        return res;
    }
}
/*====================*/
int c[N];
struct gcdTree {
    int l, r;
    int gd;
} ct[N << 2];
void cPushUp(int p) {
    ct[p].gd = __gcd(ct[ls(p)].gd, ct[rs(p)].gd);
}
void cBuild(int p, int l, int r) {
    ct[p].l = l, ct[p].r = r;
    if (l == r) {
        ct[p].gd = c[l];
    } else {
        int mid = (l + r) >> 1;
        cBuild(ls(p), l + 0, mid);
        cBuild(rs(p), mid + 1, r);
        cPushUp(p);
    }
}
void cChange(int p, int x) {
    if (ct[p].l == ct[p].r) {
        ct[p].gd = c[x];
    } else {
        int mid = (ct[p].l + ct[p].r) >> 1;
        if (x <= mid)cChange(ls(p), x);
        if (mid < x) cChange(rs(p), x);
        cPushUp(p);
    }
}
int cAsk(int p, int l, int r) {
    if (l <= ct[p].l && ct[p].r <= r) {
        return ct[p].gd;
    } else {
        int res = 0;
        int mid = (ct[p].l + ct[p].r) >> 1;
        if (l <= mid)res = __gcd(res, cAsk(ls(p), l, r));
        if (mid < r) res = __gcd(res, cAsk(rs(p), l, r));
        return res;
    }
}
/*====================*/
void Solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        c[i] = abs(a[i] - a[i - 1]);
    }
    memset(lst, -1, sizeof lst);
    for (int i = 1; i <= n; i++) {
        if (pos[a[i]].size()) lst[i] = *(--pos[a[i]].end());
        pos[a[i]].insert(i);
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << lst[i] << " ";
    // }
    Build(1, 1, n);
    cBuild(1, 1, n - 1);
    int cntyes = 0;
    // a[i]-a[i-1];
    // y-a[i-1];
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int x, y; cin >> x >> y;
            x ^= cntyes, y ^= cntyes;
            // cout << x << " " << y << "";
            // assert(x >= 1 && x <= n);
            auto it = pos[a[x]].find(x);
            if (it != pos[a[x]].end()) {
                ++it;
                lst[*it] = lst[x];
                pChange(1, *it);
            }
            if (pos[a[x]].size())
                pos[a[x]].erase(x);
            a[x] = y;
            it = pos[y].lower_bound(x);
            if (it != pos[y].end()) {
                lst[*it] = x;
                pChange(1, *it);
            }
            if (it == pos[y].begin()) {
                lst[x] = -1;
                pChange(1, x);
            } else {
                it--;
                lst[x] = *it;
                pChange(1, x);
                // pos[y].insert(x);
            }
            Change(1, x, y);
            c[x] = abs(y - a[x - 1]);
            pos[y].insert(x);
            cChange(1, x);
            if (x + 1 <= n) {
                c[x + 1] = abs(a[x + 1] - y);
                cChange(1, x + 1);
            }
        } else {
            int l, r, k; cin >> l >> r >> k;
            l ^= cntyes, r ^= cntyes, k ^= cntyes;
            // cout << l << " " << r << " " << k << "@";
            // assert(l >= 1 && l <= n); assert(r >= 1 && r <= n); assert(l <= r);
            if (r - l + 1 == 1) {
                cout << "Yes" << endl;
                cntyes++;
                continue;
            }
            auto [maxx, minn, sum] = Ask(1, l, r);
            if (k == 0) {
                cout << (maxx == minn ? "Yes" : "No") << endl;
                if (maxx == minn) cntyes++;
                continue;
            }
            if (maxx - minn != k * (r - l)) {
                cout << "No" << endl;
                continue;
            }
            if (cAsk(1, l + 1, r) != k) {
                cout << "No" << endl;
                continue;
            }
            if (pAsk(1, l, r) >= l) {
                cout << "No" << endl;
                continue;
            }
            cout << "Yes" << endl;
            cntyes++;
        }
    }
    return;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...