14220: 【原4220】Count Count

题目描述

author: Pikachu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4220 #### 时间限制：1s 空间限制：256MB

题目描述

在春天这种这种大好时光里，当然要出去玩啦！
小源和小思一起去了某知名植物园游玩，他们惊讶的发现路旁边种着一排树，树上有一些果子，每棵树的果子数量各不相同。小源决定和小思玩一个游戏，小源指了两棵树，小思需要回答出这两棵数之间（包括这两棵树）中果子最多的树有几个果子。小思有点发烧，数不过来，想来求助你，请你帮助他完成这个小游戏。

温馨提示1

由于读入数据可能会很大，请使用cstdio头文件作为输入输出，并且使用如下读入/输出优化： ```

include

// Other headers you need and your variables inline int read() { int X = 0, w = 0; char ch = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return X; }

inline void write(int x) { int y = 10, len = 1; while (y <= x) { y *= 10; len++; } while (len--) { y /= 10; putchar(x / y + 48); x %= y; } } 使用方法：读取一个**无符号**整数a = read();，输出一个**无符号**整数write(a);```

温馨提示2

给出\(log\ 2\)的数值0.69314718

输入格式

输入数据有若干行，第一行为树的数量\(n\)，以及询问的次数\(q\)。
第二行有\(n\)个数\(a_i\)，表示第\(i\)棵树有\(a_i\)个果子。(1-based)
第三行开始有\(q\)行，每一行两个整数\(l_i\)，\(r_i\)，代表第\(i\)次询问的区间。

输出格式

输出\(q\)行，第\(i\)行表示第\(i\)个询问的结果。

样例输入

样例输出

2
5

数据规模

对于\(30\%\)的数据有\(1\leq n \leq 10^3, 1\leq a_i \leq 10^9, 1\leq q\leq 10^4\)。
对于\(50\%\)的数据有\(1\leq n \leq 10^3, 1\leq a_i \leq 10^9, 1\leq q \leq 10^6\)。
对于\(100\%\)的数据有\(1\leq n \leq 2\times 10^5, 1\leq a_i \leq 10^9, 1\leq q \leq 10^6\)。

q4x3's solution

/**
 * 分块
 * 线段树也可但是我不会写
 * 分块nb！快读nb！inline nb！register nb！
 **/
#include <iostream>
#include <stdio.h>
#include <cmath>
#define re register
using namespace std;

inline void read(int &x) {
    x = 0;
    char ch;
    while (ch = getchar(), ch < '0' || ch > '9');
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
}

int n, q, a[200233], maxi[200233], blocknum;
// int n, q, a[200], maxi[200], blocknum;
int tmp1, tmp2, tmp3, tmp4;
inline void init() {
    blocknum = sqrt(n);
    for(re int i = 0;i < blocknum;++ i) {
        int tmp = i * blocknum;
        for(re int j = 0;j < blocknum;++ j) {
            if(a[tmp + j] > maxi[i])
                maxi[i] = a[tmp + j];
        }
    }
    int tmp = blocknum * blocknum;
    for(re int i = 0;i < n - tmp;++ i) {
        if(a[tmp + i] > maxi[blocknum])
            maxi[blocknum] = a[tmp + i];
    }
}

int main() {
    read(n);
    read(q);
    for(re int i = 0;i < n;++ i) 
        read(a[i]);
    init();
    for(re int i = 0;i < q;++ i) {
        re int ans = 0;
        read(tmp1);
        read(tmp2);
        -- tmp1; -- tmp2;
        tmp3 = tmp1 / blocknum + 1;
        tmp4 = tmp2 / blocknum - 1;
        for(re int j = tmp3;j <= tmp4;++ j)
            if(maxi[j] > ans) ans = maxi[j];
        int tmp5 = tmp1;
        while(tmp1 < tmp3 * blocknum && tmp1 < tmp2) {
            if(a[tmp1] > ans) ans = a[tmp1];
            ++ tmp1;
        }
        while(tmp2 >= tmp4 * blocknum && tmp2 >= tmp5) {
            if(a[tmp2] > ans) ans = a[tmp2];
            -- tmp2;
        }
        printf("%d\n", ans);
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX_N 200010
#define MAX_BIT 32
#define max(a, b) ((a) > (b) ? (a) : (b))
#define lowbit(x) ((x) & (-(x)))
using namespace std;
int a[MAX_N][MAX_BIT];
int pow_2[MAX_BIT];
int n, q;
inline int read() {
    int X = 0, w = 0; char ch = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return X;
}
inline void write(int x) {
    int y = 10, len = 1;
    while (y <= x) { y *= 10; len++; }
    while (len--) { y /= 10; putchar(x / y + 48); x %= y; }
    putchar('\n');
}
int main() {
    pow_2[0] = 1;
    for (int i = 1; i < MAX_BIT; ++i) pow_2[i] = pow_2[i - 1] << 1;
    n = read(), q = read();
    for (register int i = 1; i <= n; ++i) a[i][0] = read();
    for (register int j = 1; pow_2[j] <= n; ++j)
        for (register int i = 0; i + pow_2[j] - 1 <= n; ++i)
            a[i][j] = max(a[i][j - 1], a[i + pow_2[j - 1]][j - 1]);

    register int l, r, k;
    for (register int i = 0; i < q; ++i) {
        l = read(), r = read();
        k = log(r - l + 1) / 0.69314718;
        write(max(a[l][k], a[r - (1 << k) + 1][k]));
    }
    return 0;
}

zqy2018's solution

/*
    Hint: use sparse table
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, logg;
int f[200005][20], a[200005];
void build_ST(){
    for(int i = 1; i <= n; ++i)
        f[i][0] = a[i];
    logg = 1;
    while((1 << logg) < n) logg++;
    for(int i = 1; i < logg; ++i){
        int p = (1 << i);
        for(int j = 1; j + p - 1 <= n; ++j)
            f[j][i] = max(f[j][i - 1], f[j + (p >> 1)][i - 1]);
    }
    f[1][logg] = max(f[1][logg - 1], f[1 << (logg - 1)][logg - 1]);
}
int getLog(int x){
    if(x <= 2) return 0;
    if(x <= 4) return 1;
    if(x <= 8) return 2;
    if(x <= 16) return 3;
    if(x <= 32) return 4;
    if(x <= 64) return 5;
    if(x <= 128) return 6;
    if(x <= 256) return 7;
    if(x <= 512) return 8;
    if(x <= 1024) return 9;
    if(x <= 2048) return 10;
    if(x <= 4096) return 11;
    if(x <= 8192) return 12;
    if(x <= 16384) return 13;
    if(x <= 32768) return 14;
    if(x <= 65536) return 15;
    if(x <= 131072) return 16;
}
int query(int l, int r){
    int od = getLog(r - l + 1);
    return max(f[l][od], f[r - (1 << od) + 1][od]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    build_ST();
    int l, r;
    while(m--)
        scanf("%d%d", &l, &r),
        printf("%d\n", query(l, r));
    return 0;
}