【平板电视无TLE】非加强能过,加强过不了

P6136 【模板】普通平衡树(数据加强版)

LiuTianyou @ 2022-07-22 16:20:56

这段代码非加强版(P3369)是可以过的,但是加强版把解密用了之后就过不去了

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define I64 "%d"
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> data;
signed main(){
    int n, m, cnt = 0, last = 0, ans = 0;
    scanf(I64 I64, &n, &m);
    for(int i = 1, t; i <= n; i++){
        scanf(I64, &t);
        data.insert(std::make_pair(t, cnt++));
    }
    for(int i = 1; i <= m; i++){
        int op, x;
        scanf(I64 I64, &op, &x);
        x ^= last;
        if(op == 1){
            data.insert(std::make_pair(x, cnt++));
        }else if(op == 2){
            auto it = data.lower_bound(std::make_pair(x, 0));
            data.erase(it);
        }else if(op == 3){
            last = data.order_of_key(std::make_pair(x, 0)) + 1;
        }else if(op == 4){
            last = data.find_by_order(x  - 1)->first;
        }else if(op == 5){
            last = data.find_by_order(data.order_of_key(std::make_pair(x, 0)) - 1)->first;
        }else{
            last = data.find_by_order(data.order_of_key(std::make_pair(x, 2147483647)))->first;
        }
        ans ^= last;
    }
    printf(I64 "\n", ans);
    return 0;
}

两个点AC,8个点WA,无TLE,所以我平板电视如果写对了是可以过的,不用优化,不是时间问题.


by LiuTianyou @ 2022-07-22 16:22:42

我猜想应该是从非加强到加强修改的过程中存在问题


by Hagasei @ 2022-07-22 16:25:09

元素可能不存在,所以你删除的方法有误


by LiuTianyou @ 2022-07-22 16:26:38

@Stream_X 操作 2 保证存在至少一个 x,题目写的,我理解有问题吗


by LiuTianyou @ 2022-07-22 16:27:40

@Stream_X 所以应该怎么删除


by LiuTianyou @ 2022-07-22 16:32:24

@Pozhu


by Hagasei @ 2022-07-22 16:32:30

好吧,我没看题,是操作1,2不需要异或last


by Hagasei @ 2022-07-22 16:32:52

你不能全部都异或


by LiuTianyou @ 2022-07-22 16:37:04

@Stream_X 明白


by Cat_shao @ 2022-07-22 18:30:46

@Stream_X 你读题了吗?


by Hagasei @ 2022-07-22 19:34:54

@Cat_shao 我是说 ans 不用异或,可能是没说清楚


| 下一页