【题解】Luogu P2880 【[USACO07JAN]平衡的阵容Balanced Lineup】

zkw线段树

发现普通线段树居然T飞了,

而zkw线段树就快的飞起,

显然,zkw线段树非常厉害,也非常好打的。看下代码就知道了。
关于zkw线段树可以看博客的讲解:http://www.cinema000.xyz/tag/zkwsegmenttree。

#include<cstdio>

const int MAXN = 5e4 + 6;
const int INF = 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 println(int x){
    print(x);
    putchar('\n');
}

int n,M;

void maintain(int p){
    t[p].min = min(t[LEFT(p)].min,t[RIGHT(p)].min);
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
}

void build(){
    for(M = 1;M < (n + 1);M <<= 1);
    for(int i = M + 1;i <= M + n;i++){
        t[i].min = t[i].max = read();
    }
    for(int i = M - 1;i;i--){
        maintain(i);
    }
}

zkw ask(int l,int r){
    zkw ans;ans.max = -INF;ans.min = INF;
    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;
}

int main(){
    int q;
    n = read();q = read();

    build();

    int l,r;
    zkw ans;
    while(q--){
        l = read();r = read();
        ans = ask(l,r);
        println(ans.max - ans.min);
    }

    return 0;
}

发布者:Cinema

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

留下评论

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