题目链接
题意：大小为n(10^5)的数组a，按大小顺序从大到小和字典序从小到大插入的方法重建数组a，m(10^5)个询问，第i次操作后数组中第k个数是多少。
离线+树状数组
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>pii;
const int maxn = 2e5 + 7;
int a[maxn], index[maxn], ans[maxn], sum[maxn];
int n,m;
int lowbit(int x) {return x & (-x);
}void update(int x, int val) {while (x <= n) {sum[x] += val;x += lowbit(x);}
}
int getsum(int x)
{int ans = 0;while (x){ans += sum[x];x -= lowbit(x);}return ans;
}
int kth(int k)
{int ans = 0, cnt = 0;for (int i = 20; i >= 0; i--){if (ans + (1 << i) <= n && cnt + sum[ans + (1 << i)] < k){ans += (1 << i);cnt += sum[ans];}}return ans + 1;
}
struct cmp
{bool operator()(pii a, pii b) { if (a.first == b.first)return a.second > b.second; else return a.first < b.first; }
};
int main()
{cin >> n;priority_queue<pii,vector<pii>,cmp>q;for (int i = 1; i <= n; i++)cin >> a[i],q.push(pii(a[i],i));//while (!q.empty())cout << q.top().second << endl,q.pop();cin >> m;vector<pair<pii, int>>p;for (int i = 0; i < m; i++){int x, y;cin >> x >> y;p.push_back(make_pair(pii(x, y), i));}sort(p.begin(), p.end());int k = 0;for (int i = 0; i < m; i++){while (!q.empty() && k < p[i].first.first){//cout << q.top().second << "*******" << endl;update(q.top().second, 1);q.pop();k++;}int pos = p[i].first.second;ans[p[i].second] = a[kth(pos)];//cout <<"***"<< kth(pos) <<" "<<a[kth(pos)]<< endl;}for (int i = 0; i < m; i++)cout << ans[i] << endl;
}第k小