JDOJ 1065

https://neooj.com/oldoj/problem.php?id=1065

题目描述

【”客观”背景】苏修是苏联修正主义的简称。从1956年到1966年的10年间，过去“亲密
无间”的中苏两党突然翻脸相向，中共批判苏共是“修正主义”， 苏共则指中共为“教条主
义”，双方起初密函对责，继而公开论战，由意识形态之争发展到指著对方领袖点名道姓地互
骂，两党、两国关系遂急剧恶化，终致爆发1969年的中苏边界武装冲突。中国从此把只能把苏
联视为主要敌人，为了钳制苏联而于1972年与美国复好。“中苏大论战”的遗恨延续了30年，
直到1989年戈尔巴乔夫夫访华中苏两党的关系才算回归到正常化。事虽不远，如今竟无几人能
说得清两党当年究竟有何深仇大恨。20世纪80年代以来，当初专用于指责苏联和苏共的“修正
主义”、“苏联社会帝国主义”等词汇已基本上从官方的意识形态话语中消失，这段本来就深
藏种种隐情的历史被掩埋得不露痕迹，70年代以后出生的人甚至可能一无所知。
苏联发起了现代修正主义，他不仅在经济上走资本主义道路，还企图坑害中国。
MZD当然不会让苏联欺骗，他已经弄通了苏联欺骗中国的方式，苏联在与中国的贸易
中偷鸡摸狗…经常缺斤短两.MZD为了制止这种行为,他会发动全国广大fans来抵制苏联出
售的产品.
但是MZD需要找到证据…他希望知道在苏联出售给Z国的一批货物在第i天和第j天之间
贸易额最大的一个.

输入

第一行:两个数n,m.分别表示中国与苏联进行了n天贸易,MZD想提出m个问题.
接下来第2行到第n+1行每行一个数,第i行表示第i-1天当天的贸易额.
然后的第n+2行到文件末尾的m行中,每行两个数x,y(x,y<=maxlongint)表示MZD想知道的区间.

输出

一共m行,第i行表示MZD的第i个问题的答案.

样例输入

3 2
1
3
2
1 2
1 3

样例输出

3
3

提示

数据范围：
30% n,m<=2000
60% n<=500000 m<=2000
80% n<=1000000,m<=2000
100% n<=1000000,m<=20000

 
ps:个人认为题目描述就是个(脏话)
 
我交的时候一直在RE
RERERERERERERERERERERE
检查又检查，没什么毛病？
不就是一道ST算法的裸题么？
请大家注意，这道题并没有给x，y谁大谁小，也就是说我们在做区间求最值的ST算法中，针对每一个询问还需要判一下谁大…（脏话）
好不容易AC了之后的Code

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[1000001][21],lg[1000001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i][0]);
    for(int i=2;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);//太太太重要了！！！
        int k=lg[y-x+1];
        printf("%d
",max(f[x][k],f[y-(1<<k)+1][k]));
    }
    return 0;
}