黄山建设厅官方网站,呼市网站建设,用html做一号店网站怎么做,免费的关键词优化软件Description 每天,农夫 John 的N(1 N 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 Q 180,000) 个可能的牛的… Description 每天,农夫 John 的N(1 N 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 Q 180,000) 个可能的牛的选择和所有牛的身高 (1 身高 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间. Input * 第一行: N 和 Q. * 第2..N1行: 第i1行是第i头牛的身高. * 第N2..NQ1行: 两个整数, A 和 B (1 A B N), 表示从A到B的所有牛. Output *第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个. Sample Input 6 3 1 7 3 4 2 5 1 5 4 6 2 2 Sample Output 6 3 0 第一次敲了个RMQ……因为位运算优先级太低没加括号而一直RE…… #includeiostream
#includecstdio
#includecstring
#includecstdlib
#includecmath
#includealgorithm
using namespace std;
long long f[100001][30];
long long g[100001][30];
long long a[100001];
inline int read()
{int x0;char chgetchar();while(ch0||ch9)chgetchar();while(ch0ch9){xx*10ch-0;chgetchar();}return x;
}
int main()
{
memset(f,-1,sizeof(f));
memset(g,127/3,sizeof(g));
int nread(),qread();
for (int i1;in;i)a[i]read();
for (int i1;in;i)
{
f[i][0]a[i];
g[i][0]a[i];
}
for (int j1;jlog((double)n)/log(2.0);j)
{for (int i1;in1-(1j);i)
{f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);g[i][j]min(g[i][j-1],g[i(1(j-1))][j-1]);
}
}
for (int i1;iq;i){int xread(),yread();int klog(y-x1)/log(2);
int mxmax(f[x][k],f[y1-(1k)][k]);int mnmin(g[x][k],g[y1-(1k)][k]);printf(%d\n,mx-mn);}
}转载于:https://www.cnblogs.com/zhber/p/4036095.html
