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: 催更
