蒟蒻求助,分数现在随机分布。。。
查看原帖
蒟蒻求助,分数现在随机分布。。。
455490
Sharpsmile楼主2021/12/19 18:50

rt,调不出来了QAQ,现在同一份代码分数36到52不等,反复横跳。。。。。

代码如下:

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#define int long long
#define inlind inline void
#define inlinl inline bool
#define inlint inline int
#define inlinc inline char
#define inlins inline string
#define mem0(a) memset(a,0,sizeof(a))
#define memf(a) memset(a,0x3f,sizeof(a))
#define mem_f(a) memset(a,0x80,sizeof(a))
#define mem_1(a) memset(a,-1,sizeof(a))
#define pb(a,b) a.push_back(b)
#define mp(a,b) make_pair(a,b)
#define p1(x) x.first
#define p2(x) x.second
using namespace std;
const int M = 19260817;
inlind re(int &x) {
    x = 0;
    bool f = 0;
    int w = getchar();

    while (w < '0' || w > '9') {
        if (w == '-')
            f = 1;

        w = getchar();
    }

    while (w <= '9' && w >= '0') {
        x = (x << 3) + (x << 1) + w - '0';
        x %= M;
        w = getchar();
    }

    if (f)
        x = -x;
}
inlind wr(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }

    if (x > 9)
        wr(x / 10);

    putchar(x % 10 + '0');
}
struct node {
    int s[2], si, x, val;
} a[1000030];
int n;
inlind upd(int i) {
    a[i].si = a[a[i].s[1]].si + a[a[i].s[0]].si + 1;
}
inlind sw(int &i, bool p) {
    int t = a[i].s[p];
    a[i].s[p] = a[t].s[!p];
    a[t].s[!p] = i;
   
    upd(t);
    upd(i);
    i = t;
}
int cnt = 0;
inlind ins(int &i, int x) {
    if (!i) {
        i = ++cnt;
        a[i].si = 1;
        a[i].x = x;
        a[i].val = rand();
        return ;
    }
    a[i].si++;
    if (x > a[i].x){
        ins(a[i].s[1], x);
        if (a[i].val > a[a[i].s[1]].val)
            sw(i, 1);
    }
    else{
        ins(a[i].s[0], x);
        if (a[i].val > a[a[i].s[0]].val)
            sw(i, 0);
    }



  
}
inlind del(int &i, int x) {
    if (x == a[i].x) {
        if (a[i].s[1] == 0) {
            i = a[i].s[0];
            return ;
        }

        else if (a[i].s[0] == 0) {
            i = a[i].s[1];
            return ;
        }

        else {
            if (a[a[i].s[0]].val > a[a[i].s[1]].val)
                sw(i, 1), del(a[i].s[0], x);
            else
                sw(i, 0), del(a[i].s[1], x);
        }
    }

    else if (x < a[i].x)
        del(a[i].s[0], x);
    else
        del(a[i].s[1], x);

    upd(i);
}
inlint fi(int i, int x) {
    if (!i)
        return 1;

    if (x > a[i].x)
        return a[a[i].s[0]].si + 1 + fi(a[i].s[1], x);
    else
        return fi(a[i].s[0], x);
}
inlint ge(int i, int x) {

    if (a[a[i].s[0]].si == x - 1)
        return a[i].x;

    if (a[a[i].s[0]].si >= x)
        return ge(a[i].s[0], x);
    else
        return ge(a[i].s[1], x - a[a[i].s[0]].si - 1);
}
inlint lt(int i, int x) {
    if (!i)
        return -2e9-10;

    if (x > a[i].x)
        return max(a[i].x, lt(a[i].s[1], x));
    else
        return lt(a[i].s[0], x);
}
inlint nt(int i, int x) {
    if (!i)
        return 2e9+10;

    if (x < a[i].x)
        return min(nt(a[i].s[0], x), a[i].x);
    else
        return nt(a[i].s[1], x);

}
int st;
signed main() {
    srand(time(0)+3);
    re(n);

    for (int i = 1; i <= n; i++) {
        int op, x;
        re(op);
        re(x);

        switch (op) {
        case 1:
            ins(st, x);
            break;

        case 2:
            del(st, x);
            break;

        case 3:
            printf("%lld\n", fi(st, x));
            break;

        case 4:
            printf("%lld\n", ge(st, x));
            break;

        case 5:
            printf("%lld\n", lt(st, x));
            break;

        case 6:
            printf("%lld\n", nt(st, x));
            break;
        }
    }

    return 0;
}

2021/12/19 18:50
加载中...