本题数据加强了？

微雨燕双飞 @ 2018-02-03 18:17:26

by ViXbob @ 2018-02-03 18:32:08

您想多了吧，单调队列O(n)，线段树O(mlogn),单调队列被卡了，线段树怎么可能过得去，肯定是您单调队列写错了吧。

by EternalAlexander @ 2018-02-03 19:59:34

又交了一遍单调队列没问题。 您可能是常数写大了。

by EternalAlexander @ 2018-02-03 20:03:34

将您的cin和cout改成scanf和printf就过了

#include<cstdio>
#include <iostream>
using namespace std;
int n,m;
struct node
{
  int num,place;
}q[2000010];
int main()
{
  scanf("%d %d", &n, &m);
  int head=1,tail=1;
  scanf("%d", &q[tail].num); q[tail++].place=1;
  printf("0\n");
  for(int i=2; i<=n; i++) 
  {
    int a;
    scanf("%d", &a);
    if(i-q[head].place>m) head++;
    printf("%d\n", q[head].num);
    while(a<q[tail-1].num&&(tail-head!=0)) tail--;
    q[tail].num=a,q[tail++].place=i;
  }
  return 0;
}

by 微雨燕双飞 @ 2018-02-12 20:55:13

太感谢了，各位巨神，蒟蒻无以为报