题目描述
blablabla
样例
blablabla
算法1
(线段树) $O(klogn)$
blablabla
时间复杂度
参考文献
C++ 代码
const int N = 1e5+5;
class Solution {
public:
struct node{
int l,r;
int lv,rv;
int inc,dec;
}tr[4*N];
void pushup(int u){
node left=tr[u<<1],right=tr[u<<1|1];
tr[u].lv=left.lv;
tr[u].rv=right.rv;
if(left.inc&&right.inc&&left.rv<=right.lv){
tr[u].inc=1;
}
else tr[u].inc=0;
if(left.dec&&right.dec&&left.rv>=right.lv){
tr[u].dec=1;
}
else tr[u].dec=0;
}
void build(int u, int l, int r, vector<int>& a){
if(l==r){
tr[u]={l,r,a[l],a[l],1,1};
return;
}
tr[u]={l,r};
int mid = (l+r)>>1;
build(u<<1,l,mid,a);
build(u<<1|1,mid+1,r,a);
pushup(u);
}
void modify(int u,int c,int x){
if(tr[u].l==tr[u].r&&tr[u].l==c){
tr[u].lv=tr[u].rv=x;
}
else{
int mid=tr[u].l+tr[u].r>>1;
if(c<=mid) modify(u<<1,c,x);
else modify(u<<1|1,c,x);
pushup(u);
}
}
node query(int u,int nl, int nr)
{
int l=tr[u].l,r=tr[u].r;
if(nl<=l&&nr>=r) return tr[u];
int mid=(l+r)>>1;
node left={-1,-1,-1,-1,-1,-1};
node right={-1,-1,-1,-1,-1,-1};
if(nl<=mid) left=query(u<<1,nl,nr);
if(nr>mid) right=query(u<<1|1,nl,nr);
if(left.lv==-1&&right.lv==-1) return {-1,-1,-1,-1,-1,-1};
else if(left.lv!=-1&&right.lv==-1) return left;
else if(left.lv==-1&&right.lv!=-1) return right;
node res;
res={0,0,left.lv,right.rv};
if(left.inc&&right.inc&&left.rv<=right.lv){
res.inc=1;
}
else res.inc=0;
if(left.dec&&right.dec&&left.rv>=right.lv){
res.dec=1;
}
else res.dec=0;
return res;
}
vector<int> goodIndices(vector<int>& nums, int k) {
int n = nums.size();
build(1,0,n-1,nums);
vector<int> res;
for(int i=0;i<n;i++){
if(i>=k&&i<n-k){
node l = query(1,i-k,i-1);
node r = query(1,i+1,i+k);
if(l.dec && r.inc)
res.push_back(i);
}
modify(1,i,nums[i]);
}
return res;
}
};