BZOJ 5042 LWD的分科岛

题目大意

维护序列最大/最小值，单点修改，区间查询。

这题就暴力上线段树呗……

然后T了。

之后考虑优化……

某种特♂殊的优化（高级读入优化+高级输出优化）似乎可以解决……但是没啥必要

这题实际上是要求zkw线段树的……

加上各种优化成功进入第一页前半段23333

#include <cctype>
#include <cstdio>
#include <cstring>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define R register
using namespace std;
typedef unsigned long long ull;
int n,q,opt,l,r,tot=1;
ull maxn[12000010],minn[12000010];
char pbuf[100000] , *pp = pbuf;
inline void push(const char ch)
{
    if(pp == pbuf + 100000) fwrite(pbuf , 1 , 100000 , stdout) , pp = pbuf;
    *pp ++ = ch;
}
inline void flush()
{
    fwrite(pbuf , 1 , pp - pbuf , stdout);
}
inline void write(ull x)
{
    static char sta[30];
    int tot = 0;
    if(!x) push('0');
    while(x) sta[++tot] = x % 10 + '0' , x /= 10;
    while(tot) push(sta[tot -- ]);
    push('\n');
}
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ull rd()
{
    char ch=nc();ull sum=0;
    while(!isdigit(ch))ch=nc();
    while(isdigit(ch))sum=((sum+(sum<<2))<<1)+(ch^48),ch=nc();
    return sum;
}
inline int rdb()
{
    char ch=nc();int sum=0;
    while(!isdigit(ch))ch=nc();
    while(isdigit(ch))sum=((sum+(sum<<2))<<1)+(ch^48),ch=nc();
    return sum;
}
  
int main()
{
    n=rdb(),q=rdb();//scanf("%d%d",&n,&q);
    while(tot<=n) tot<<=1;
    for(R int i=tot+1;i<=tot+n;++i) minn[i]=maxn[i]=rd();
    for(R int i=tot-1;i;i--) maxn[i]=max(maxn[i<<1],maxn[i<<1|1]),minn[i]=min(minn[i<<1],minn[i<<1|1]);
    R ull ret;
    while(q--)
    {
        opt=rdb(),l=rdb(),r=rdb();//scanf("%d%d%d",&opt,&l,&r);
        if(opt==1)
        {
            ret=0xffffffffffffffffull;
            for(l=l+tot-1,r=r+tot+1;l^r^1;l>>=1,r>>=1)
            {
                if(r&1) ret=min(ret,minn[r^1]);
                if(~l&1) ret=min(ret,minn[l^1]);
            }
            write(ret);
        }
        if(opt==2)
        {
            ret=0;
            for(l=l+tot-1,r=r+tot+1;l^r^1;l>>=1,r>>=1)
            {
                if(r&1) ret=max(ret,maxn[r^1]);
                if(~l&1) ret=max(ret,maxn[l^1]);
            }
            write(ret);
        }
    }
    flush();
    return 0;
}