【线段树 细节题】bzoj1067: [SCOI2007]降雨量

主要还是细节分析;线段树作为工具

Description

  我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意
Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,
则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知,有的说法是可能正确也可以不正确的。

Input

  输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小
到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

  对于每一个询问,输出true,false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9


题目分析

题意很简单,但是一道需要细细思考的细节题。

具体的思路,挂一个很详细的博客好了题解 P2471 【[SCOI2007]降雨量】

至于具体实现我用了离散化,然后用线段树查询(x,y)区间内的最值。

 #include<bits/stdc++.h>
const int maxn = ; struct QRs
{
int x,y;
}qr[];
struct node
{
int x,val;
}a[maxn];
int n,m;
int tot[],t[],cnt;
int val[],f[]; int read()
{
char ch = getchar();
int num = ;
bool fl = ;
for (; !isdigit(ch); ch = getchar())
if (ch=='-') fl = ;
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
if (fl) num = -num;
return num;
}
void pushup(int x)
{
f[x] = std::max(f[x<<], f[x<<|]);
}
void build(int rt, int l, int r)
{
if (l==r){
f[rt] = val[l];
return;
}
int mid = (l+r)>>;
build(rt<<, l, mid), build(rt<<|, mid+, r);
pushup(rt);
}
int query(int rt, int L, int R, int l, int r)
{
if (L > R) return ;
if (L <= l&&r <= R) return f[rt];
int mid = (l+r)>>, ret = ;
if (L <= mid) ret = query(rt<<, L, R, l, mid);
if (R > mid)
ret = std::max(ret, query(rt<<|, L, R, mid+, r));
return ret;
}
int main()
{
n = read();
for (int i=; i<=n; i++)
t[++cnt] = a[i].x = read(), a[i].val = read();
m = read();
for (int i=; i<=m; i++)
t[++cnt] = qr[i].x = read(), t[++cnt] = qr[i].y = read(), t[++cnt] = qr[i].y-, t[++cnt] = qr[i].x+;
std::sort(t+, t+cnt+);
cnt = std::unique(t+, t+cnt+)-t-;
int pre = ;
for (int i=; i<=n; i++)
{
int tt = std::lower_bound(t+, t+cnt+, a[i].x)-t;
val[tt] = a[i].val, tot[tt] = tot[pre]+, pre = tt;
}
build(, , cnt);
for (int i=; i<=m; i++)
{
int x = std::lower_bound(t+, t+cnt+, qr[i].x)-t;
int y = std::lower_bound(t+, t+cnt+, qr[i].y)-t;
int dex = std::lower_bound(t+, t+cnt+, qr[i].x+)-t;
int dey = std::lower_bound(t+, t+cnt+, qr[i].y-)-t;
if (val[x]&&val[y]){
if (val[x] < val[y]) puts("false");
else{
bool exCheck = query(, dex, dey, , cnt)<val[y];
if (!exCheck) puts("false");
else{
exCheck = exCheck&&((tot[y]-tot[x])==(qr[i].y-qr[i].x));
if (!exCheck) puts("maybe");
else puts("true");
}
}
continue;
}
if ((!val[x])&&(!val[y])) puts("maybe");
else{
int secMx = query(, dex, dey, , cnt);
if (!secMx){
puts("maybe");
continue;
}
if (val[x]){
if (secMx >= val[x]) puts("false");
else puts("maybe");        //注意这里是maybe而不是true因为中间值未知
}
if (val[y]){
if (secMx >= val[y]) puts("false");
else puts("maybe");
}
}
}
return ;
}

END

上一篇:bzoj 1067: [SCOI2007]降雨量


下一篇:Java中的NIO基础知识