QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398454#6533. Traveling in CellsiwewTL 0ms8248kbC++204.1kb2024-04-25 12:43:012024-04-25 12:43:02

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 12:43:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:8248kb
  • [2024-04-25 12:43:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100010;

struct Node {
    int l, r;
    ll v;
}tr[N << 2];

set<pair<int, int>> s[N];

void build(int u, int l, int r, vector<int> &v) {
    if(l == r) {
        tr[u] = {l, r, v[l]};
    } else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, v), build(u << 1 | 1, mid + 1, r, v);
        tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
    }
}

void update(int u, int x, int v) {
    if(tr[u].l == tr[u].r) {
        tr[u].v = v;
    } else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) update(u << 1, x, v);
        else update(u << 1 | 1, x, v);
        tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
    }
}

ll query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) {
        return tr[u].v;
    } else {
        ll res = 0;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) res += query(u << 1, l, r);
        if(r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while(T -- ) {
        int n, q;
        cin >> n >> q;
        vector<int> c(n + 1), v(n + 1);
        for(int i = 1; i <= n; i ++ ) cin >> c[i];
        for(int i = 1; i <= n; i ++ ) cin >> v[i];
        build(1, 1, n, v);

        for(int i = 1; i <= n; i ++ ) s[c[i]].clear();
        for(int i = 1; i <= n; i ++ ) {
            int j = i;
            while(j + 1 <= n && c[j + 1] == c[i]) j += 1;
            s[c[i]].insert({i, j});
            i = j;
        }

        while(q -- ) {
            int type;
            cin >> type;
            if(type == 1) {
                int p, x;
                cin >> p >> x;
                if(c[p] == x) continue;
                auto cur = s[c[p]].upper_bound({p, p});
                cur -- ;
                auto [L, R] = *cur;
                s[c[p]].erase(cur);
                if(p - 1 >= L) s[c[p]].insert({L, p - 1});
                if(p + 1 <= R) s[c[p]].insert({p + 1, R});

                c[p] = x;
                s[c[p]].insert({x, x});
                if(p - 1 >= 1 && c[p - 1] == c[p]) {
                    cur = s[c[p - 1]].upper_bound({p - 1, p - 1});
                    cur -- ;
                    auto now = s[c[p]].upper_bound({p, p});
                    now -- ;

                    auto [l1, r1] = *cur;
                    auto [l2, r2] = *now;
                    s[c[p - 1]].erase(cur), s[c[p]].erase(now);
                    s[c[p]].insert({l1, r2});
                }
                if(p + 1 <= n && c[p + 1] == c[p]) {
                    cur = s[c[p + 1]].upper_bound({p + 1, p + 1});
                    cur -- ;
                    auto now = s[c[p]].upper_bound({p, p});
                    now -- ;

                    auto [l1, r1] = *now;
                    auto [l2, r2] = *cur;
                    s[c[p + 1]].erase(cur), s[c[p]].erase(now);
                    s[c[p]].insert({l1, r2});
                }
            } else if(type == 2) {
                int p, x;
                cin >> p >> x;
                update(1, p, x);
            } else {
                int x, k;
                cin >> x >> k;
                set<int> sa;
                for(int i = 0; i < k; i ++ ) {
                    int a;
                    cin >> a;
                    sa.insert(a);
                }

                int L = x, R = x;
                while(sa.count(c[L])) {
                    auto cur = s[c[L]].upper_bound({L, L});
                    cur -- ;
                    auto [l, r] = *cur;
                    L = l - 1;
                    if(L == 0) break;
                }
                while(sa.count(c[R])) {
                    auto cur = s[c[R]].upper_bound({R, R});
                    cur -- ;
                    auto [l, r] = *cur;
                    R = r + 1;
                    if(R == n + 1) break;
                }
                cout << query(1, L + 1, R - 1) << '\n';
            }
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8248kb

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:

100
110
1200
21211
100010
4000000

result:

ok 6 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

20000
15 15
1 1 3 3 2 3 3 3 3 3 2 3 2 3 3
634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831
3 6 4 1 3 5 10
3 5 7 1 2 3 4 5 9 10
3 4 3 3 8 9
2 13 608033129
3 15 2 3 5
1 9 3
3 8 4 1 3 7 10
2 6 727472865
3...

output:


result: