效率至上

Time Limit: 5000MS Memory Limit: 65536KB

SubmitStatistic

PRoblemDescription

題意很簡單,給出一個數(shù)目為n的非有序序列,然后有m次查詢.對于每次查詢輸入兩個正整數(shù)l,r請輸出區(qū)間[l,r]的最大值與最小值的差值

Input

 第一行：輸入兩個正整數(shù)n,m    (1<=n<=50000,  1<=m<=200000  )；

第二行：輸入n個整數(shù) 大小范圍為[1,100000];

接下來的m行,每次兩個正整數(shù)l,r (1<=l<=r<=n);

Output

 輸出區(qū)間[l,r]最大值與最小值的差值.

ExampleInput

6 3
1
7
3
4
2
5
1 5
4 6
2 2
ExampleOutput
6
3
0
Hint
  
Author
#include <iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<stdlib.h>//#include<bits/stdc++.h>using namespace std;#define M 100001#define lson l,m,bh*2#define rson m+1,r,bh*2+1const int INF = 0x3f3f3f3f;long long sum[M*4],Max[M*4],Min[M*4];void pushup(int bh)//遞歸完成合并左右信息{  sum[bh] = sum[bh*2]+sum[bh*2+1];  Max[bh] = max(Max[bh*2],Max[bh*2+1]);  Min[bh] = min(Min[bh*2],Min[bh*2+1]);}void build(int l,int r,int bh){   if(l ==r)   {     scanf("%lld",&sum[bh]);     Min[bh] = Max[bh] = sum[bh];     return ;   }   int m = (l+r)/2;   build(lson);   build(rson);   pushup(bh);}void update(int p,long long v,int l,int r,int bh){   if(l ==r )   {      sum[bh] += v;      return ;   }   int m = (l+r)/2;   if(p <= m)update(p,v,lson);   else update(p,v,rson);   pushup(bh);}//查詢L到R的和long long ask(int L,int R,int l,int r,int bh){    if(L<=l&&r<=R)    return sum[bh];    int m = (l+r)/2;    long long temp = 0;    if(L<=m) temp +=ask(L,R,lson);    if(R>m) temp +=ask(L,R,rson);    return temp;}long long int askmax(int L,int R,int l,int r,int bh){   if(L<=l&&r<=R) return Max[bh];   int m = (l+r)/2;   long long int temp = -INF;   if(L<=m) temp = max(temp,askmax(L,R,lson));   if(R>m) temp = max(temp,askmax(L,R,rson));   return temp;}long long int askmin(int L,int R,int l,int r,int bh){    if(L<=l&&R>=r)return Min[bh];    int m = (l+r)/2;    long long int temp = INF;    if(L <= m) temp = min(temp,askmin(L,R,lson));    if(R>m)  temp = min(temp,askmin(L,R,rson));    return temp;}int main(){  int n,q,p,l,r,op,o;  long long v;  while(~scanf("%d",&n))  {     scanf("%d",&o);     build(1,n,1);     for(int i=0;i<o;i++)     {          scanf("%d %d",&l,&r);          printf("%lld/n",askmax(l,r,1,n,1)-askmin(l,r,1,n,1));     }  }  return 0;}/*struct node{   int cnt;   int next[26];} tree[500005];int a;int creat(){   memset(tree[a].next,0,sizeof(tree[a].next));   tree[a].cnt =0;   return a++;}//用next數(shù)組名字本身存字母，數(shù)組中的數(shù)據(jù)存的是下一代節(jié)點位置//top 為代數(shù)序號void insert(int top,char *str){   int i,len,t;   len = strlen(str);   //for循環(huán)決定了代數(shù)只能 按時間序依次進(jìn)行   for(i=len-1;i>=0;i--)//每增加一個字母相當(dāng)于多增加了一代   {       t = str[i]-'0';       if(tree[top].next[t]==0)//開辟下一代       {          tree[top].next[t]= creat();       }       tree[top].cnt++;       top = tree[top].next[t];//存儲完成進(jìn)入下一代   }   //   ++tree[top].cnt;//cnt 則存儲以當(dāng)前字母結(jié)束字符串出現(xiàn)次數(shù)}int search(int top,char *str){   int i,t,len;   len = strlen(str);   for(i=len-1;i>=0;i--)   {      t = str[i]-'0';      if(tree[top].next[t]==0)//假如在樹家族中后繼無人，立即截止      {         return 0;      }      top = tree[top].next[t];//進(jìn)入下一代，看似沖突的相同名字      //實際上占據(jù)了不同的空間，相同的建立查找規(guī)則使得沖突矛盾消失      //此時才取出字符串出現(xiàn)次數(shù)   }   return tree[top].cnt;}int main(){    char str[11];    int n,m,i,top;    while(~scanf("%d",&n))    {        a = 0;        top = creat();        for(i = 0;i< n;i++)        {            scanf("%s",str);            insert(top,str);        }        scanf("%d",&m);        //getchar();        for(i = 0;i<m;i++)        {            scanf("%s",str);            printf("%d/n",search(top,str));        }    }    return 0;}*//***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 248msTake Memory: 928KBSubmit time: 2017-02-10 15:45:21****************************************************/