Tyvj 1730 二逼平衡树

目前还没AC qaq

先是写了线段树套splay,然而可耻的挂了.. 然后又写了分块,完美的tle了... 待更新

    
    //分块tle
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    //define
    const int maxn = 300 + 5;
    const int maxm = 5e5 + 5;
    const int inf = 0x7FFFFFFF;
    
    int chunk_len[maxn], chunk[maxn][maxn], a[maxm], n, m, cnt, len;
    
    void modify(int ck, int k){
        a[ck] = k;
        int tmp=(ck + len - 1) / len;
        for(register int i = 1; i <= chunk[tmp][0]; ++i)
            chunk[tmp][i] = a[(tmp - 1) * len + i];
        stable_sort(chunk[tmp] + 1,chunk[tmp] + chunk_len[tmp] + 1);
    }
    
    int __lower_bound(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid] >= k)rr = mid;
            else ll = mid + 1;
        }
        if(aa[ll] >= k)return ll - 1;
        else return ll;
    }
    
    int __sub_search(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid + 1] <= k)ll = mid + 1;
            else rr = mid;
        }
        if(aa[ll] <= k)return ll + 1;
        else return ll;
    }
    
    int pre(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = -inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            rr++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __lower_bound(chunk[i], k) != 0){
                    ans = max(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans = max(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int sub(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __sub_search(chunk[i], k) != chunk_len[i] + 1){
                    ans = min(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] > k){
                    ans = min(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int rnk(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = 0;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans++;
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans++;
            }
            for(register int i = ll; i < rr; ++i){
                ans += __lower_bound(chunk[i], k);
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans++;
                }
            }
        }return ans+1;
    }
    
    int kth(int l, int r, int k){
        int ll = 0, rr = inf, ans = 0;
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(rnk(l, r, mid) > k) rr = mid;
            else ll = mid+1, ans = mid;
        }return ans;
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for(register int i = 1; i <=n; ++i){
            cin >> a[i];
        }
        cnt = sqrt(n) + 2;len = cnt;
        for(register int i = 1; i <= cnt; ++i){
            for(register int j = 1; j <= len; ++j){
                chunk[i][j] = a[(i - 1) * len + j];
            }
            stable_sort(chunk[i] + 1, chunk[i] + len + 1);
            chunk_len[i] = len;
        }
        if(n % len != 0){
            cnt++;chunk_len[cnt] = n % len;
            for(register int i = 1; i <= chunk_len[cnt]; ++i){
                chunk[cnt][i] = a[(cnt - 1) * len + i];
            }
            stable_sort(chunk[cnt] + 1, chunk[cnt] + chunk_len[cnt] + 1);
        }
        int opt, x, y, z;
        while(m--){
            cin >> opt;
            if(opt == 1){
                cin >> x >> y >> z;
                cout << rnk(x, y, z) << endl;
            }
            else if(opt == 2){
                cin >> x >> y >> z;
                cout << kth(x, y, z) << endl;
            }
            else if(opt == 3){
                cin >> x >> y;
                modify(x, y);
            }
            else if(opt == 4){
                cin >> x >> y >> z;
                cout << pre(x, y, z) << endl;
            }else {
                cin >> x >> y >> z;
                cout << sub(x, y, z) << endl;
            }
        }
        return 0;
    }

Comments

BeyondLimits: tql%%%

Polarnova: 催更