subtask 1过了，subtask 0 全都TLE咋回事

如题，求求大佬看看，必关注！思路同深基，代码是自己写的，代码如下（会附上每个板块的解释）

第一部分就是定义

CPP

#include<iostream>
using namespace std;
const int INF = 0x7fffffff;
const int _INF = -0x7fffffff;
int q, root, cnt, opt, x;
struct tree
{
    int left, right, size, value, num;
}t[100010];

第二部分是树的构建

CPP

void update(int root)
{
    t[root].size = t[t[root].left].size + t[t[root].right].size + t[root].num;
}
void add(int x, int root)
{
        if(x == t[root].value) t[root].num++;
        if(t[root].left == 0 && t[root].value > x)
        {
            cnt++;
            t[cnt].value = x, t[cnt].num = 1, t[cnt].size = 1;
            t[root].left = cnt;
        }else if(t[root].right == 0 && t[root].value < x)
        {
            cnt++;
            t[cnt].value = x, t[cnt].num = 1, t[cnt].size = 1;
            t[root].right = cnt;
        }else if(x > t[root].value)
        {
            add(x, t[root].right);
        }else if(x < t[root].value) add(x, t[root].left);
        update(root);
}

第三部分是找x的排名，我感觉是这里错了，如果x不在其中我的做法是找出负数的排名然后输出0

CPP

int ran(int x, int root)
{
   if(root)
   {
       if(x == t[root].value) return t[t[root].left].size + 1;
       if(x < t[root].value) return ran(x, t[root].left);
       if(x > t[root].value) return ran(x, t[root].right) + t[t[root].left].size + t[root].num;
   }else return -114514;
}

第四部分是找排名为x的数

CPP

int select(int x, int root)
{
    if(x == 0) return 0;
    if(x == t[t[root].left].size + 1) return t[root].value;
    if(x <= t[t[root].left].size) return select(x, t[root].left);
    if(x > t[t[root].left].size + 1) return select(x-t[t[root].left].size - 1, t[root].right);
}

最后就是主体操作部分了，前后继采用的是定位x排名后找排名的前或者后数字。

CPP

int main()
{
    cin >> q;
    for(int i = 1;  i <= q; i++)
    {
        cin >> opt;
        if(opt == 1)
        {
            cin >> x;
            if(ran(x,1) < 0) cout << 0 << endl;
            else cout << ran(x,1) << endl;
        }
        if(opt == 2)
        {
            cin >> x;
            cout << select(x,1) << endl;
        }
        if(opt == 3)
        {
            cin >> x;
            int a = ran(x, 1);
            if(select(a - 1, 1)) cout << select(a - 1, 1) << endl;
            else cout << _INF << endl;
        }
        if(opt == 4)
        {
            cin >> x;
            int a = ran(x, 1);
            if(select(a + 1, 1)) cout << select(a + 1, 1) << endl;
            else cout << INF << endl;
        }
        if(opt == 5)
        {
            cin >> x;
            if(cnt == 0) cnt++, t[cnt].value = x, t[cnt].num = 1, t[cnt].size = 1;
            else add(x, 1);
        }
    }
    return 0;
}

subtask 1过了，subtask 0 全都TLE咋回事

讨论操作

回复

相关推荐

subtask 1过了，subtask 0 全都TLE咋回事