pku2823slidingwindow(线段树||rmq||单调队列)

关键词：

#include<cstdio>
#include<algorithm>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
int Segtree_min[maxn<<2],Segtree_max[maxn<<2];
int n,k,value;
int begin,end;
//每个结点保存该区间线段的最大/小值
void Build(int l,int r,int pos)
{
    if(l==r){
        scanf("%d",&value);
        Segtree_max[pos]=Segtree_min[pos]=value;
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,2*pos);
    Build(mid+1,r,2*pos+1);
    Segtree_min[pos]=min(Segtree_min[2*pos],Segtree_min[2*pos+1]);
    Segtree_max[pos]=max(Segtree_max[2*pos],Segtree_max[2*pos+1]);
}
int Query_min(int ll,int rr,int l,int r,int pos)
{
    if(ll<=l&&r<=rr)
        return Segtree_min[pos];
    int mid=(l+r)/2;
    //int begin=inf,end=inf;
    if(ll<=mid)
        begin=Query_min(ll,rr,l,mid,2*pos);
    if(rr>mid)
        end=Query_min(ll,rr,mid+1,r,2*pos+1);
    return min(begin,end);
}
int Query_max(int ll,int rr,int l,int r,int pos)
{
    if(ll<=l&&r<=rr)
        return Segtree_max[pos];
    int mid=(l+r)/2;
    //int begin=-inf,end=-inf;
    if(ll<=mid)
        begin=Query_max(ll,rr,l,mid,2*pos);
    if(rr>mid)
        end=Query_max(ll,rr,mid+1,r,2*pos+1);
    return max(begin,end);
}

int main()
{
    scanf("%d%d",&n,&k);
    Build(1,n,1);
    for(int i=1;i<=n-k+1;i++)
        printf("%d ",Query_min(i,i+k-1,1,n,1));
    printf("
");
    for(int i=1;i<=n-k+1;i++)
        printf("%d ",Query_max(i,i+k-1,1,n,1));
    printf("
");
}

slidingwindow

poj2823SlidingWindow　　　　题目大意：给你一个n个数的序列，有一个长度固定的窗口，求出两个数列，分别是窗口从左滑到右，窗口内的最小值和最大值，分两行输出。　　　　注释：n<=$10^6$，内存<=64.　　　　　　想法：这... 查看详情

bzoj3212:pku3468asimpleproblemwithintegers（线段树）(代码片段)

3212:Pku3468ASimpleProblemwithIntegers题目：传送门    题解：　　感谢Rose_max大佬的倾情相（推）助（水题）　　一起打线段树啊~~~~   代码：1#include<cstdio>2#include<cstring>3#include<cstdlib&g 查看详情

pku-3468simpleproblemwithinteger线段树ll坑点(欢迎讨论)

YouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.InputThefirst 查看详情

poj2823slidingwindow

SlidingWindow Description　　Anarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseetheknumbersinthewindow.Eachtimetheslidin 查看详情

pku3667hotel（线段树，区间合并，最长连续区间）

题意：宾馆有N个房间（1~N），M个操作，a=1，输入b，表示N间房是否有连续的b间房。有输出最左边的房编号没有输出0。a=2，输入b，c表示房间b到c清空。模仿了大神的代码，敲了一遍，有些地方还要深入了解。#include<stdio.h>#in... 查看详情

poj2823slidingwindow

SlidingWindow链接：http://poj.org/problem?id=2823TimeLimit: 12000MS MemoryLimit: 65536K   CaseTimeLimit: 5000MSDescriptionAnarrayofsize n ≤106 isgiventoy 查看详情

poj2823slidingwindow

SlidingWindowTimeLimit:12000MS MemoryLimit:65536KTotalSubmissions:54824 Accepted:15777CaseTimeLimit:5000MSDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovi 查看详情

poj2823slidingwindow

SlidingWindowTimeLimit:12000MS MemoryLimit:65536KTotalSubmissions:62915 Accepted:17956CaseTimeLimit:5000MSDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovi 查看详情

poj2823slidingwindow题解

POJ2823Sliding Window 题解DescriptionAnarrayofsize n ≤106 isgiventoyou.Thereisaslidingwindowofsize k whichismovingfromtheveryleftofthearraytotheveryright.Youcanonly 查看详情

poj2823slidingwindow题解

SlidingWindowTimeLimit:12000MS MemoryLimit:65536KTotalSubmissions:53037 Accepted:15207CaseTimeLimit:5000MSDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovi 查看详情

poj#2823.slidingwindow

题目描述Anarrayofsize n ≤106 isgiventoyou.Thereisaslidingwindowofsize k whichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseethe k numbersinthewindow.Eac 查看详情

poj2823slidingwindow

SlidingWindowTimeLimit: 12000MS  MemoryLimit: 65536KCaseTimeLimit: 5000MSDescriptionAnarrayofsize n ≤106 isgiventoyou.Thereisaslidingwindowofsize k  查看详情

poj2823slidingwindow

SlidingWindowTimeLimit: 12000MS MemoryLimit: 65536KTotalSubmissions: 54931 Accepted: 15815CaseTimeLimit: 5000MSDescriptionAnarrayofsize n ≤106 isgi 查看详情

poj2823slidingwindow单调队列

SlidingWindowTimeLimit: 12000MS MemoryLimit: 65536KTotalSubmissions: 63635 Accepted: 18150CaseTimeLimit: 5000MSDescriptionAnarrayofsize n ≤106 isgi 查看详情

poj2823slidingwindow——单调队列

题目：http://poj.org/problem?id=2823单调队列模板。代码如下：#include<iostream>#include<cstdio>usingnamespacestd;intn,k,a[1000005],mx[1000005],mn[1000005];intmain(){ scanf("%d%d",&n,&k); for(inti= 查看详情

poj--2823--slidingwindow----单调队列问题

SlidingWindowTimeLimit:12000MS    MemoryLimit:65536KB    64bitIOFormat:%I64d&%I64uDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhic 查看详情

poj2823slidingwindow

经典题类似单调队列，好像不能用stl里的队列直接模拟QAQCodes: 1#include<iostream>2#include<cstring>3#include<cstdio>4#include<algorithm>56usingnamespacestd;7constintN=1000000+5;89intcnt1,cnt2,n,k,a 查看详情

bzoj2823slidingwindow

经典单调队列1#include<cstdio>2#include<cstring>3usingnamespacestd;4constintN=1000010;5intmaxq[N],minq[N],a[N],ans1[N],ans2[N],lmax,lmin,rmax,rmin;6intmain(){7intn,k;8lmax=lmin=rmax=rmin=0;9scanf 查看详情