php做网站安全,wordpress 分类子类名称,夫唯seo系统培训,浦东建设网站传送门
题意#xff1a; 给定一个数组和k#xff0c;求一段连续区间中位数最大值#xff0c;连续区间长度k。
如果k的话可以直接秒了#xff0c;这里是k#xff0c;我们可以通过二分让后利用k这个条件来检查答案。 二分中位数#xff0c;假设当前二分的为m…传送门
题意 给定一个数组和k求一段连续区间中位数最大值连续区间长度k。
如果k的话可以直接秒了这里是k我们可以通过二分让后利用k这个条件来检查答案。 二分中位数假设当前二分的为midmidmid那么a[i]mida[i]mida[i]mid的数可以变成111a[i]mida[i]mida[i]mid的数变成−1-1−1现在问题就变成了寻找长度k且值为正的序列。这个问题可以用前缀和解决我们枚举序列的结尾假设当前枚举到iii那么只需要check一下pre[i]−mi[i−k]0pre[i]-mi[i-k]0pre[i]−mi[i−k]0即可mi为前缀和最小值这样在保证了序列长度k的同时检查其是否合法。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,k;
int a[N],pre[N],mi[N];bool check(int mid)
{for(int i1;in;i) mi[i]INF;for(int i1;in;i) pre[i]pre[i-1](a[i]mid?1:-1),mi[i]min(mi[i-1],pre[i]);for(int ik;in;i) if(pre[i]-mi[i-k]0) return true;return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,k);for(int i1;in;i) scanf(%d,a[i]);int l1,rn,ans0;while(lr){int midlr1;if(check(mid)) ansmid,lmid1;else rmid-1;}printf(%d\n,ans);return 0;
}
/**/
