最初分块-未来日记
#include<bits/stdc++.h>
using namespace std;
using cint = const int&;
const int maxn = 1e5 + 1,maxm = 170, maxv = 1e5, siz = 600;
int n, m, a[maxn], l, r, x, y, bl, br,lb,rb,k;
char opt;
int fa[maxn], tmpc[maxn],tmpb[maxn],rt[maxm][maxn],beg[maxm],in[maxn];
inline int getfa(cint x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
int tmp,tmps,cnt[maxm][maxn], sumc[maxm][maxn], sumb[maxm][maxn];
stack<int> st;
inline void initfa(cint b, cint i) {
    if (!rt[b][a[i]]) rt[b][a[i]] = i;
    fa[i] = rt[b][a[i]];
}
inline void build(cint b) {
    for (int i = beg[b]; i < beg[b + 1]; ++i) {
        initfa(b, i);
        ++cnt[b][a[i]];
    }
}
inline void replace(cint b,cint l, cint r, cint x, cint y) {
    bl = beg[b],br = beg[b+1]-1;
    tmp = rt[b][x] = rt[b][y] = 0;
    for (int i = bl; i <= br; ++i) {
        a[i] = a[getfa(i)];
        if (a[i] == x || a[i] == y) st.push(i);
    }
    for (int i = l; i <= r; ++i)
        if (a[i] == x) a[i] = y,++tmp;
    while (!st.empty()) {
        const auto i = st.top();st.pop();
        initfa(b, i);
    }
    cnt[b][x] -= tmp, cnt[b][y] += tmp;
    for (int i = b; i <= k; ++i) {
        sumc[i][x] -= tmp, sumc[i][y] += tmp;
        sumb[i][in[x]] -= tmp, sumb[i][in[y]] += tmp;
    }
}
inline void replace(cint l, cint r, cint x, cint y) {
    lb = in[l], rb = in[r];
    if (lb == rb) return replace(lb, l, r, x, y);
    replace(lb, l, beg[lb + 1] - 1, x, y);
    replace(rb, beg[rb], r, x, y);
    tmp = tmps = 0;
    for (int i = lb + 1; i < rb; ++i) {
        if (rt[i][x])
            if (!rt[i][y]) rt[i][y] = rt[i][x], a[rt[i][x]] = y;
            else fa[rt[i][x]] = rt[i][y];
        rt[i][x] = 0, tmp = cnt[i][x], tmps += tmp;
        cnt[i][x] = 0, cnt[i][y] += tmp;
        sumc[i][x] -= tmps, sumc[i][y] += tmps;
        sumb[i][in[x]] -= tmps, sumb[i][in[y]] += tmps;
    }
    for (int i = rb; i <= k; ++i) {
        sumc[i][x] -= tmps, sumc[i][y] += tmps;
        sumb[i][in[x]] -= tmps, sumb[i][in[y]] += tmps;
    }
}
inline int get(cint b, cint l, cint r, cint x) {
    for (int i = l; i <= r; ++i) a[i] = a[getfa(i)],++tmpc[a[i]],++tmpb[in[a[i]]];
    int i;
    for (tmp=0,i = 1; tmp < x; ++i)
        tmp += tmpb[i];
    tmp -= tmpb[i];
    for (i = beg[i]; tmp < x; ++i)
        tmp += tmpc[i];
    for (tmp = l; tmp <= r; ++tmp) --tmpc[a[tmp]], --tmpb[in[a[tmp]]];
    return i;
}
inline int get(cint l, cint r, cint x) {
    lb = in[l], rb = in[r];
    if (lb == rb) return get(lb, l, r, x);
    for (int i = l; i < beg[lb + 1]; ++i) 
        a[i] = a[getfa(i)], ++tmpc[a[i]], ++tmpb[in[a[i]]];
    for (int i = beg[rb]; i <= r; ++i) 
        a[i] = a[getfa(i)], ++tmpc[a[i]], ++tmpb[in[a[i]]];
    int i;
    for (tmp = 0, i = 1; tmp < x; ++i)
        tmp += tmpb[i] + sumb[rb - 1][i] - sumb[lb][i];
    tmp -= tmpb[i] + sumb[rb - 1][i] - sumb[lb][i];
    for (i = beg[i]; tmp < x; ++i)
        tmp += tmpc[i] + sumc[rb - 1][i] - sumc[lb][i];
    for (int i = l; i < beg[lb + 1]; ++i) --tmpc[a[i]], --tmpb[in[a[i]]];
    for (int i = beg[rb]; i <= r; ++i) --tmpc[a[i]], --tmpb[in[a[i]]];
    return i;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    k = (n - 1) / siz + 1;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= maxv; ++i) in[i] = (i - 1) / siz + 1;
    beg[1] = 1;
    for (int i = 1; i <= k; ++i) {
        beg[i + 1] = min(i * siz + 1,n);
        build(i);
        memcpy(sumb[i]+1, sumb[i - 1]+1, sizeof(sumb[0][0]) * siz);
        for (int j = 1; j <= maxv; ++j) sumc[i][j] = sumc[i][j] + cnt[i][j];
        for (int j = beg[i]; j < beg[i + 1]; ++j) ++sumb[i][in[a[i]]];
    }
    while (m--) 
        if (cin >> opt; opt == '1') {
            cin >> l >> r >> x >> y;
            if (x == y) continue;
            replace(l, r, x, y);
        }
        else {
            cin >> l >> r >> x;
            cout << get(l, r, x) << '\n';
        }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇