效率至上
Time Limit: 5000MS Memory Limit: 65536KB
ProblemDescription
题意很简单,给出一个数目为n的非有序序列,然后有m次查询.对于每次查询输入两个正整数l,r请输出区间[l,r]的最大值与最小值的差值
Input
第一行:输入两个正整数n,m (1<=n<=50000, 1<=m<=200000 );
第二行:输入n个整数 大小范围为[1,100000];
接下来的m行,每次两个正整数l,r (1<=l<=r<=n);
Output
输出区间[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+1
const 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数组名字本身存字母,数组中的数据存的是下一代节点位置
//top 为代数序号
void insert(int top,char *str)
{
int i,len,t;
len = strlen(str);
//for循环决定了代数只能 按时间序依次进行
for(i=len-1;i>=0;i--)//每增加一个字母相当于多增加了一代
{
t = str[i]-'0';
if(tree[top].next[t]==0)//开辟下一代
{
tree[top].next[t]= creat();
}
tree[top].cnt++;
top = tree[top].next[t];//存储完成进入下一代
}
// ++tree[top].cnt;//cnt 则存储以当前字母结束字符串出现次数
}
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];//进入下一代,看似冲突的相同名字
//实际上占据了不同的空间,相同的建立查找规则使得冲突矛盾消失
//此时才取出字符串出现次数
}
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: Accepted
Take time: 248ms
Take Memory: 928KB
Submit time: 2017-02-10 15:45:21
****************************************************/