树状数组求调!!
查看原帖
树状数组求调!!
519573
Daniel_yao楼主2022/4/4 17:35
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, c;
int cnt[N], a[N], num, treen[4*N], treex[4*N];

int lowbit(int x){
  return x & -x;
}

void add(int x, int k){
  while(x <= n){
    treen[x] = min(treen[x], k);
    treex[x] = max(treex[x], k);
    x += lowbit(x);
  }
}

bool plu(int x, int b){
  int maxi = -0x3f3f3f3f, mini = 0x3f3f3f3f;
  while(x <= b){
    while(b - lowbit(b) >= 1){
      maxi = max(maxi, treex[b]);
      mini = min(mini, treen[b]);
      b -= lowbit(b);
    }
    maxi = max(maxi, a[b]);
    mini = min(mini, a[b]);
    b--;
  }
  return (abs(maxi - mini) <= c);
}

int main(){
  cin >> n >> m >> c;
  memset(treen,  0x3f3f3f3f, sizeof(treen));
  memset(treex, -0x3f3f3f3f, sizeof(treex));
  for(int i = 1;i <= n;i++){
    cin >> a[i];
    add(i, a[i]);
  }
  for(int i = 1;i <= n - m + 1;i++){
    if(plu(i, i + m - 1) == 1){
      cnt[++num] = i;
    }
  }
  for(int i = 1;i <= num;i++) cout << cnt[i] << endl;
  if(!num) cout << "NONE" << endl;
  return 0;
}

2022/4/4 17:35
加载中...