考场没看见随机化数据,写了一个主席树+二分,但是之前练习的时候没有做过多实例,忘记初始化上层用到的所有节点信息了, wa麻了。
思路:主席树+二分, O(nlogn^2)
二分距离当前点最近的,大于等于a[i]的数的个数最靠右的位置,
然后利用主席树区间询问在mid到i-1这段大于x的数的数量,
作为check函数
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1e5+10;
struct Node
{
int l, r;
int cnt;
};
int tfind(int l, int r, int k, int x);
int query(int pre, int now, int l, int r, int x);
int build(int l, int r);
void push_up(int u);
int add(int pre, int l, int r, int x);
int find(int x);
int T;
int n, k;
int a[N];
Node tr[4*N+N*18];
int root[N], idx;
vector<int> alls;
signed main()
{
cin>>T;
while(T--)
{
alls.clear();
for(int i=0;i<=idx;i++) tr[i]={0, 0, 0};
idx=0;//不要忘记初始化!!!!!
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++)
{
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
alls.push_back(-2e9);
sort(alls.begin(), alls.end());//离散化
alls.erase(unique(alls.begin(), alls.end()), alls.end());
root[0]=build(1, alls.size()-1);//建树
for(int i=1;i<=n;i++)
{
if(i-1<k||query(root[0], root[i-1], 1, alls.size()-1, find(a[i]))<k)//左边不足k个数或者大于x的数的个数小于k个, 无解
{
puts("-1");
root[i]=add(root[i-1], 1, alls.size()-1, find(a[i]));
}
else
{
printf("%d\n", tfind(0, i-1, k, find(a[i])));//二分查找
root[i]=add(root[i-1], 1, alls.size()-1, find(a[i]));
}
}
}
}
int find(int x)
{
return lower_bound(alls.begin(), alls.end(), x)-alls.begin();
}
int query(int pre, int now, int l, int r, int x)
{
if(l==r)
{
if(l>x) return tr[now].cnt-tr[pre].cnt;
return 0;
}
int cntr=tr[tr[now].r].cnt-tr[tr[pre].r].cnt;
int sum=0;
int mid=l+r>>1;
if(mid+1>x) sum+=cntr;//如果右边都大于, 直接加上
else sum+=query(tr[pre].r, tr[now].r, mid+1, r, x);//否则大于x的数还在右边
if(mid>x) sum+=query(tr[pre].l, tr[now].l, l, mid, x);//若左边也有, 递归左边
return sum;//返回结果
}
int tfind(int l, int r, int k, int x)//二分出来1~i-1中最靠右的位置, 使得>x的数的数量等于k
{
int i=r;
while(l<r)
{
int mid=l+r+1>>1;//判断当前mid到i-1的位置, 大于x的数的数量,若<k则说明r更小
if(query(root[mid-1], root[i], 1, alls.size()-1, x)<k) r=mid-1;//若mid到i-1小于k说明,还在左边
else l=mid;//否则往右走
}
return a[l];//最后这个l就是最靠右的大于x数的个数的位置, 输出a[l]即可
}
int add(int pre, int l, int r, int x)
{
int now=++idx;
tr[now]=tr[pre];
if(l==r)
{
tr[now].cnt++;
return now;
}
int mid=l+r>>1;
if(x<=mid) tr[now].l=add(tr[pre].l, l, mid, x);
else tr[now].r=add(tr[pre].r, mid+1, r, x);
push_up(now);
return now;
}
void push_up(int u)
{
tr[u].cnt=tr[tr[u].l].cnt+tr[tr[u].r].cnt;
}
int build(int l, int r)
{
int now=++idx;
if(l==r) return now;
int mid=l+r>>1;
tr[now].l=build(l, mid), tr[now].r=build(mid+1, r);
return now;
}