# 14220: 【原4220】Count Count

### 题目描述

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

# 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);

## 样例输入

5 2
1 2 3 4 5
1 2
1 5


## 样例输出

2
5


## q4x3's solution

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

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() {
for(re int i = 0;i < n;++ i)
init();
for(re int i = 0;i < q;++ i) {
re int ans = 0;
-- 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;
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;
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) {
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;
}