本来想刷刷水题,结果刷出问题来了,查询区间自己还是没有彻底弄透,警告!!
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #include <map> #include <limits> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 200001; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int N,M; int MAX[maxn<<2],MIN[maxn<<2]; void PushUP(int rt){ MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]); } void build(int l,int r,int rt){ if(l==r){ SD(MAX[rt]); MIN[rt]=MAX[rt]; return ; } int m=(l+r)>>1; build(lson); build(rson); PushUP(rt); } int query1(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return MAX[rt]; } int m = (l + r) >> 1; int ret =0; if (L <= m) ret = max(ret , query1(L , R , lson)); if (R > m) ret = max(ret , query1(L , R , rson)); return ret; } int query2(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return MIN[rt]; } int m = (l + r) >> 1; int ret = INF; if (L <= m) ret = min(ret , query2(L , R , lson)); if (R > m) ret = min(ret , query2(L , R , rson)); return ret; } void print(int l,int r,int rt){ printf("l:%d r:%d max:%d min:%d \n",l,r,MAX[rt],MIN[rt]); if(l==r) return ; int m=(l+r)>>1; print(lson); print(rson); } int main() { SD(N);SD(M); build(1,N,1); FOR(i,1,M){ int ql,qr; SD(ql);SD(qr); int maxans=query1(ql,qr,1,N,1); int minans=query2(ql,qr,1,N,1); printf("%d\n",maxans-minans); } return 0; }