bitset神力 n^2过50000

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mid ((l + r) >> 1)
#define lson tre[fa].le
#define rson tre[fa].re
#define pii pair<int, int>
using namespace std;
using namespace __gnu_pbds;

bitset<50010> bs;
int n, m, tot, cnt;
map<int, int> mp[50010];

int main(){
    cin >> n >> m;
    tot = n;
    for(int j = 1; j <= m; j++){
        int typ;
        cin >> typ;
        if(typ == 1){
            
            int x;
            cin >> x;
            if(mp[cnt].find(x) != mp[cnt].end()) {
                cout << mp[cnt][x] << endl;
                
            }
            else{
                if(x > tot){
                    cout << 0 << endl;
                    continue;
                }
                int lf = 1, rf = 1, ok = 0;
                while(lf + x - 1 <= n){
                    while(bs[lf] && lf + x - 1 <= n) lf++;
                    if(lf + x - 1 > n) break;
                    rf = lf;
                    do{
                        if(rf - lf + 1 == x){
                            ok = 1;
                            break;
                        }
                        rf++;
                    }while(rf <= n && !bs[rf]);
                    if(ok) break;
                    lf = rf;
                }
                if(ok){
                    cout << lf << endl;
                    tot -= x;
                    for(int i = lf; i < lf + x; i++) bs[i] = 1;
                    cnt++;
                }
                else{
                    cout << 0 << endl;
                    mp[cnt][x] = 0;
                }
                
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            cnt++;
            for(int i = l; i < l + r; i++){
                if(bs[i]) tot++;
                bs[i] = 0;
            }
        }
    }
    return 0;
}