BZOJ2276:[Poi2011]Temperature 单调性+线段树

思路:

貌似存在\(O(n)\)的算法,不过由于我太弱只想到了\(O(nlogn)\).

现在很困就发代码了...有问题回复找我吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
struct SegmentTree{
    int a[2100000],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        memset(a,0xc0,sizeof a);
    }
    inline void upd(int x,int to){
        for(a[x+=M]=to,x>>=1;x;x>>=1)a[x]=max(a[x<<1],a[x<<1^1]);
    }
    inline int ask(int tl,int tr){
        int res=-1<<30;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)res=max(res,a[tl^1]);
            if(tr&1)res=max(res,a[tr^1]);
        }return res;
    }
}Seg;
 
int up[N];
 
namespace Fio{
    inline int getc(){
#ifndef ONLINE_JUDGE
        static const int L=1<<1;
#else
        static const int L=1<<15;
#endif
        static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}return*S++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c=0;while(!digit(c=getc())&&c!='-');bool sign=c=='-';x=sign?0:c-'0';
        while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';if(sign)x=-x;
    }
}
 
int main(){
    int n;Fio::Get(n);register int i,j;
    Seg.Init(n);
    int x;for(i=1;i<=n;++i)Fio::Get(x),Fio::Get(up[i]),Seg.upd(i,x);
     
    int nowmax=Seg.ask(1,1);
    int lans,ans;
    for(lans=2;lans<=n;++lans){
        if(nowmax>up[lans])break;
        nowmax=max(nowmax,Seg.ask(lans,lans));
    }ans=--lans;
     
    for(i=2;i<=n;++i){
        nowmax=Seg.ask(i,lans);
        for(++lans;lans<=n;++lans){
            if(nowmax>up[lans])break;
            nowmax=max(nowmax,Seg.ask(lans,lans));
        }--lans;
        ans=max(ans,lans-i+1);
    }
     
    printf("%d",ans);
     
    return 0;
}