【题解】Luogu P1886 【滑动窗口】

这也是一道$RMQ$问题,正如题目名称所示,就是求滑动窗口的最值,然后我想着用线段树去做,发现我的写法让我无论怎样优化或开$-o2$,都无法$A$掉,正好今天学了zkw线段树,这树常数特别小,非常快,然后顺手就$A$掉了。

其实我还是很好奇为何@OYSJ的朴素线段树也过去了。

#include<cstdio>

const int MAXN = 1000000 + 6;
const int INT_MAX = 0x7fffffff;

class zkwSegmentTree{
    public:int max,min;
};
typedef zkwSegmentTree zkw;
zkw t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}

inline int read(){
    int op = 1,ans = 0;char s = getchar();
    while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
    while(s >= '0' && s <= '9'){ans = ans * 10 + s - '0';s = getchar();}
    ans *= op;
    return ans;
}
void print(int x){
    if(x < 0){putchar('-');x = -x;}
    if(x > 9){print(x / 10);}
    putchar(x % 10 + '0');
}
void printse(int x){
    print(x);
    putchar(' ');
}

int n,M;

void build(){
    for(M = 1;M < (n + 1);M <<= 1);
    for(int i = M + 1;i <= M + n;i++){
        //int gg;
        //scanf("%d",&gg);
        t[i].min = t[i].max = read();
    }
    for(int i = M - 1;i;i--){
        t[i].min = min(t[LEFT(i)].min,t[RIGHT(i)].min);
        t[i].max = max(t[LEFT(i)].max,t[RIGHT(i)].max);
    }
}

zkw ask(int l,int r){
    zkw ans;ans.max = -INT_MAX;ans.min = INT_MAX;
    for(l += M - 1,r += M + 1;l ^ r ^ 1;l >>= 1,r >>= 1){
        if(~l & 1){
            ans.min = min(ans.min,t[l ^ 1].min);
            ans.max = max(ans.max,t[l ^ 1].max);
        }
        if(r & 1){
            ans.min = min(ans.min,t[r ^ 1].min);
            ans.max = max(ans.max,t[r ^ 1].max);
        }
    }
    return ans;
}

zkw ANS[MAXN * 4];

int main(){
    int m;
    scanf("%d %d",&n,&m);
    
    build();
    
    int j = n - m + 1;
    for(int i = 1;i <= j;i++){
        ANS[i] = ask(i,i + m - 1);
        printse(ANS[i].min);
    }
    putchar('\n');
    for(int i = 1;i <= j;i++){
        printse(ANS[i].max);
    }
    
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

加入对话

4条评论

电子邮件地址不会被公开。 必填项已用*标注

    1. #include
      #define left (root< <1)
      #define right ((root<<1)+1)
      #define maxn 1000005
      using namespace std;
      
      int n,k,a[maxn];
      struct tree{
          int l;
          int r;
          int max;
          int min;
      };
      tree t[maxn<<2];
      struct ret{
          int min;
          int max;
      };
      inline int max(int x,int y){
          return x>y ? x:y;
      }
      inline int min(int x,int y){
          return x'9')
          {
              if(c=='-'){
                  k=-1;
                  c='0';
                  break;
                  //c='0';//wu
              }
              else    c = getchar();
          }
          while(c>='0'&&c< ='9')
          {
              x=x*10+c-'0';
              c=getchar();
          }
          return x*k;
      }
      
      void built(int l,int r,int root)
      {
          t[root].l=l;t[root].r = r;
          if(l==r){
              t[root].min = a[l];
              t[root].max = a[l];
          }
          else{
              int mid = l+r >> 1;
              built(l,mid,left);
              built(mid+1,r,right);
              t[root].min = min(t[left].min,t[right].min);
              t[root].max = max(t[left].max,t[right].max);
          }
          return;
      }
      
      
      ret get(int l,int r,int root)
      {
          int nl = t[root].l , nr = t[root].r;ret r1;
          if(nl==l&&nr==r)
          {
              r1.max = t[root].max;
              r1.min = t[root].min;
              return r1;
          }
          
          int mid = nl+nr>>1;
          if(r< =mid)  return get(l,r,left);
          if(l>=mid+1)    return get(l,r,right);
          r1 = get(l,mid,left);ret k = get(mid+1,r,right);
          r1.max = max(r1.max,k.max);
          r1.min = min(r1.min,k.min);
          return r1;  
      }
      
      int main()
      {
          //freopen("123.in","r",stdin);
          n=read();k=read();
          for(int i=1;i< =n;i++)
              a[i]=read();
          built(1,n,1);
          
          int end = n-k+1;ret temp;
          for(int i=1;i<=end;i++)
          {
              temp = get(i,i+k-1,1);
              printf("%d ",temp.min);
              a[i] = temp.max;
          }
          printf("\n");
          for(int i=1;i<=end;i++)
              printf("%d ",a[i]);
          return 0;
      }