QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384303#6533. Traveling in Cellsmai123WA 1ms5588kbC++145.0kb2024-04-09 21:31:522024-04-09 21:31:53

Judging History

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

  • [2024-04-09 21:31:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5588kb
  • [2024-04-09 21:31:52]
  • 提交

answer

#include<bits/stdc++.h>

#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef pair<int, int> PII;
const int Maxn = 1e5 + 10;
int c[Maxn], v[Maxn];
unordered_map<int, unordered_set<int>> pos;//记录每个颜色的位置
// 树状数组维护区间和
int tr[Maxn];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int d) {
    for (; x < Maxn; x += lowbit(x))tr[x] += d;
}

int sum(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x))res += tr[x];
    return res;
}


struct Node {
    int l, r, val;
} T[Maxn << 2];

void pushUp(int node) {
    T[node].val = T[node << 1].val + T[node << 1 | 1].val;
}

void build(int node, int l, int r) {
    T[node] = {l, r, 0};
    if (l == r)return;
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    pushUp(node);
}

void update(int node, int l, int r, int d) {
    if (l <= T[node].l && T[node].r <= r) {
        T[node].val = d;
        return;
    }
    int mid = (T[node].l + T[node].r) >> 1;
    if (l <= mid)update(node << 1, l, r, d);
    if (mid < r)update(node << 1 | 1, l, r, d);
    pushUp(node);
}

// 查询[l,r]区间内,最左边的完全填充区
int query_left(int node, int l, int r) {
    int mid = (T[node].l + T[node].r) >> 1;
    // 该节点被查询区间完全包括
    if (l <= T[node].l && T[node].r <= r) {
        if (T[node].val == T[node].r - T[node].l + 1) {
            return T[node].l;
        }
        // 该区间未完全填充
        if (T[node].l == T[node].r)return T[node].r + 1;
        // 先查询靠近x的区域
        int left = query_left(node << 1 | 1, l, r);
        if (left == mid + 1) left = query_left(node << 1, l, r);
        return left;
    } else if (l <= mid && mid < r) {
        // 查询区间被当前节点包括,且中点被查询区间包括
        int left = query_left(node << 1 | 1, l, r);
        if (left == mid + 1)left = query_left(node << 1, l, r);
        return left;
    } else if (l <= mid)return query_left(node << 1, l, r);//查左子树
    else if (mid < r)return query_left(node << 1 | 1, l, r);//查右子树
}

// 查询[l,r]区间内,最右边的完全填充区
int query_right(int node, int l, int r) {
    int mid = (T[node].l + T[node].r) >> 1;
    // 该节点被查询区间完全包括
    if (l <= T[node].l && T[node].r <= r) {
        if (T[node].val == T[node].r - T[node].l + 1) {
            return T[node].r;
        }
        // 该区间未完全填充
        if (T[node].l == T[node].r)return T[node].l - 1;
        int right = query_right(node << 1, l, r);
        if (right == mid + 1)right = query_right(node << 1 | 1, l, r);
        return right;
    } else if (l <= mid && mid < r) {
        // 查询区间被当前节点包括,且中点被查询区间包括
        int right = query_right(node << 1, l, r);
        if (right == mid)right = query_right(node << 1 | 1, l, r);
        return right;
    } else if (l <= mid)return query_right(node << 1, l, r);//查左子树
    else if (mid < r)return query_right(node << 1 | 1, l, r);//查右子树
}


signed main() {
    int cnt = 0;
    ios;
    int t;
    cin >> t;
    while (t--) {
        pos.clear();
        int n, q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++)tr[i] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
            pos[c[i]].insert(i);
        }
        for (int i = 1; i <= n; i++) {
            cin >> v[i];
            add(i, v[i]);
        }
        while (q--) {
            int op, p, x, k;
            cin >> op;
            cout<<op<<" ";
            if (op == 1) {
                cin >> p >> x;
                cout<<p<<" "<<x<<endl;
                //cp改成x
                pos[c[p]].erase(p);
                if (pos[c[p]].empty())pos.erase(c[p]);
                pos[x].insert(p);
                c[p] = x;
            } else if (op == 2) {
                cin >> p >> x;
                cout<<p<<" "<<x<<endl;
                int diff = x - v[p];
                add(p, diff);
                v[p] = x;
            } else {
                for (int i = 1; i <= (n << 2); i++)T[i] = {0, 0, 0};
                build(1, 1, n);
                cin >> x >> k;
                cout<<x<<" "<<k<<" ";
                for (int i = 0; i < k; i++) {
                    int a;
                    cin >> a;
                    cout<<a<<" ";
                    // 遍历颜色a的所有位置,并 +1
                    for (int c_pos: pos[a]) {
                        update(1, c_pos, c_pos, 1);
                    }
                }
                int left = query_left(1, 1, x);
                int right = query_right(1, x, n);
                int ans = sum(right) - sum(left - 1);
                cout<<endl;
//                cout << ans << endl;
            }
        }
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5588kb

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:

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 
3 4 4 1 2 3 4 

result:

wrong answer 1st numbers differ - expected: '100', found: '3'