【BZOJ1067】【POJ2637】降雨量

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #define N 50000
 6 using namespace std;
 7 struct  data{int mx,lx,rx,k;}seg[N*4];
 8 int n,m,lb,fb,hb,px,py,maxn,ct;
 9 int know[N],a[N],rain[N];
10 void updata(int now)
11 {
12     seg[now].mx=max(seg[(now<<1)].mx,seg[(now<<1)+1].mx);
13     seg[now].k=seg[(now<<1)].k|seg[(now<<1)+1].k;
14 }
15 void buildtree(int now,int l,int r)
16 {
17     seg[now].lx=l;  seg[now].rx=r;
18     if  (l==r)  {seg[now].mx=rain[l];   seg[now].k=know[l]; return;}
19     int mid=(l+r)>>1;
20     buildtree((now<<1),l,mid);
21     buildtree((now<<1)+1,mid+1,r);
22     updata(now);
23 }
24 int query(int now,int begin,int end)
25 {
26     int l=seg[now].lx,r=seg[now].rx;
27     if (begin<=l && end>=r)   {hb=hb|seg[now].k;  return seg[now].mx;}
28     int mid=(l+r)>>1,ans=0;
29     if (begin<=mid)  ans=max(query((now<<1),begin,end),ans);
30     if (end>mid) ans=max(query((now<<1)+1,begin,end),ans);
31     return ans;
32 }
33 int main()
34 {
35     int i;
36     int x,y;
37     scanf("%d",&n);
38     for (i=1;i<=n;i++)
39     {
40         scanf("%d%d",&a[i],&rain[i]);
41         if (a[i]-a[i-1]!=1&&i!=1)   know[i]=1;
42     }
43     buildtree(1,1,n);
44     scanf("%d",&m);
45     for (i=1;i<=m;i++)
46     {
47         fb=0;   hb=0;   lb=0;   
48         scanf("%d%d",&x,&y);
49         if (x>=y)    {printf("false\n"); continue;}
50         if (y<=a[1]||x>=a[n])   {printf("maybe\n");continue;}
51         px=lower_bound(a+1,a+n+1,x)-a;  py=lower_bound(a+1,a+n+1,y)-a;
52         if (a[px]!=x)   fb=1;   if (a[py]!=y)   lb=1;
53         if (fb&&lb) {printf("maybe\n");continue;}
54         if (!fb)
55             if (a[px+1]-a[px]!=1)   hb=1;
56         if (!lb)
57             if (a[py]-a[py-1]!=1)   hb=1;
58         if (fb&&lb) maxn=query(1,px,py-1);
59         else    if (!fb&&lb)    maxn=query(1,px+1,py-1);
60         else    if (fb&&!lb)    maxn=query(1,px,py-1);
61         else    if (!fb&&!lb)   maxn=query(1,px+1,py-1);
62         if (!fb&&!lb&&!hb&&rain[px]>=rain[py]&&maxn<rain[py]) {printf("true\n");continue;}
63         if (!fb&&!lb&&hb&&rain[px]>=rain[py]&&maxn<rain[py])  {printf("maybe\n");continue;}
64         if (!fb&&lb&&maxn<rain[px])  {printf("maybe\n"); continue;}
65         if (fb&&!lb&&maxn<rain[py])  {printf("maybe\n"); continue;}
66         printf("false\n");
67     }
68     return 0;
69 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 #define N 50000
 7 using namespace std;
 8 struct  data{int mx,lx,rx,k;}seg[N*4];
 9 int n,m,lb,fb,hb,px,py,maxn,T;
10 int know[N],a[N],rain[N];
11 void updata(int now)
12 {
13     seg[now].mx=max(seg[(now<<1)].mx,seg[(now<<1)+1].mx);
14     seg[now].k=seg[(now<<1)].k|seg[(now<<1)+1].k;
15 }
16 void buildtree(int now,int l,int r)
17 {
18     seg[now].lx=l;  seg[now].rx=r;
19     if  (l==r)  {seg[now].mx=rain[l];   seg[now].k=know[l]; return;}
20     int mid=(l+r)>>1;
21     buildtree((now<<1),l,mid);
22     buildtree((now<<1)+1,mid+1,r);
23     updata(now);
24 }
25 int query(int now,int begin,int end)
26 {
27     int l=seg[now].lx,r=seg[now].rx;
28     if (begin<=l && end>=r)   {hb=hb|seg[now].k;  return seg[now].mx;}
29     int mid=(l+r)>>1,ans=0;
30     if (begin<=mid)  ans=max(query((now<<1),begin,end),ans);
31     if (end>mid)    ans=max(query((now<<1)+1,begin,end),ans);
32     return ans;
33 }
34 int main()
35 {
36     int i;
37     int x,y;
38     while (~scanf("%d",&n))
39     {
40     if (n==0) break;
41     memset(seg,0,sizeof(seg));
42     memset(rain,0,sizeof(rain));
43     memset(know,0,sizeof(know));
44     memset(a,0,sizeof(a));
45     for (i=1;i<=n;i++)
46     {
47         scanf("%d%d",&a[i],&rain[i]);
48         if (a[i]-a[i-1]!=1&&i!=1)   know[i]=1;
49     }
50     buildtree(1,1,n);
51     scanf("%d",&m);
52     for (i=1;i<=m;i++)
53     {
54         fb=0;   hb=0;   lb=0;    
55         scanf("%d%d",&x,&y);
56         if (x>=y)    {printf("false\n");    continue;}
57         if (y<=a[1]||x>=a[n])   {printf("maybe\n");continue;}
58         px=lower_bound(a+1,a+n+1,x)-a;  py=lower_bound(a+1,a+n+1,y)-a;
59         if (a[px]!=x)    fb=1;    if (a[py]!=y)    lb=1;
60         if (fb&&lb)    {printf("maybe\n");continue;}
61         if (!fb)
62             if (a[px+1]-a[px]!=1)    hb=1;
63         if (!lb)
64             if (a[py]-a[py-1]!=1)    hb=1;
65         if (fb&&lb)    maxn=query(1,px,py-1);
66         else    if (!fb&&lb)    maxn=query(1,px+1,py-1);
67         else    if (fb&&!lb)    maxn=query(1,px,py-1);
68         else    if (!fb&&!lb)    maxn=query(1,px+1,py-1);
69         if (!fb&&!lb&&!hb&&rain[px]>=rain[py]&&maxn<rain[py])    {printf("true\n");continue;}
70         if (!fb&&!lb&&hb&&rain[px]>=rain[py]&&maxn<rain[py])    {printf("maybe\n");continue;}
71         if (!fb&&lb&&maxn<rain[px])    {printf("maybe\n");    continue;}
72         if (fb&&!lb&&maxn<rain[py])    {printf("maybe\n");    continue;}
73         printf("false\n");
74     }
75     printf("\n");
76     }
77     return 0;
78 }