「计蒜客模拟赛」自适应平衡多叉处理数据结构

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

const int MAXN = 3e5 + 5;

int t, q, l; //tql

int c[MAXN], d[MAXN];
// s[i] = c[i] + d[i / l]

inline void modify(int p) {
    int t1 = (p / l + 1) * l - 1;
    t1 = min(t1, t);
    for (int i = p; i <= t1; ++i)
        c[i]++;
    int t2 = t / l;
    for (int i = p / l + 1; i <= t2; ++i)
        d[i]++;
}

inline int query(int p) {
    return c[p] + d[p / l];
}

int main() {
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    scanf("%d%d", &t, &q);
    l = sqrt(t);
    while (q--) {
        int tp, cur;
        scanf("%d%d", &tp, &cur);
        if (tp == 0) {
            modify(cur);
        } else {
            int stp = 0, lst = 0;
            while (1) {
                int t1 = query(cur), t2 = query(lst);
                stp = t1 - t2;
                if (!stp) break;
                lst = cur, cur += t1;
                if (cur > t) {
                    cur = -1;
                    break;
                }
            }
            printf("%d\n", cur);
        }
    }
    return 0;
}