调题就没有不疯的

问题讨论区 提高段
1

P2471 [SCOI2007] 降雨量 - 洛谷 洛谷上是这题,WA30pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50005;
int rain[N],year[N],st[N][20],lg[N],n;
int find(int x){
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(year[mid]==x)
            return mid;
        if(year[mid]<x)
		    l=mid+1;
		else
		    r=mid-1;
	}
	return 0; 
}
int findy(int x){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)/2;
		if(year[mid]<=x)
		    l=mid+1;
		else
		    r=mid;
	}
	return l;
}
int findx(int x){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)/2;
		if(year[mid]<=x)
		    l=mid;
		else
		    r=mid-1;
	}
	return l;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
	map<int,int> mp;
    for(int i=1;i<=n;i++){
		cin>>year[i]>>rain[i];
		st[i][0]=rain[i];
		mp[year[i]]=i;
	}
	for(int i=2;i<=n;i++)
	    lg[i]=lg[i/2]+1;
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++)
		    st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	int q;
	cin>>q;
	while(q--){
		int y,x;
		cin>>y>>x;
		if(x-y==mp[x]-mp[y]){
			int yw=find(y)+1,xw=find(x)-1;
	        int l=lg[xw-yw+1];
			if(max(st[yw][l],st[xw-(1<<l)+1][l])<rain[xw+1]){
	            cout<<"true\n";
	            continue;
			}            
        }
        if(find(x)&&find(y)){
            int yw=find(y)+1,xw=find(x)-1;
	        int l=lg[xw-yw+1];
			if(max(st[yw][l],st[xw-(1<<l)+1][l])>=rain[xw+1]){
	            cout<<"false\n";
	            continue;
			}                 
        }
        if(find(x)){
            int yw=findy(y),xw=find(x)-1;
	        int l=lg[xw-yw+1];
			if(max(st[yw][l],st[xw-(1<<l)+1][l])>=rain[xw+1]){
	            cout<<"false\n";
	            continue;
			}                 
        }
        if(find(y)){
            int yw=find(y)+1,xw=findx(x);
	        int l=lg[xw-yw+1];
			if(max(st[yw][l],st[xw-(1<<l)+1][l])>=rain[yw-1]){
	            cout<<"false\n";
	            continue;
			}               
        }
        cout<<"maybe\n";
	}
	return 0;	
}

大佬们帮忙看看吧

2

大佬召唤术：@2345安全卫士 @我命由我不由天 @金杭东 @stringdp100005

3

蒟蒻召唤成功

1 个赞
4

开始帮我调一下，代码有点抽象

5

好消息这题我去年春季有这题。
坏消息：不会，到现在没AC。
感觉到时候可以看看，今天要睡了，明天把

6

哦对了，记得调成问题讨论区

7

这是提高的啊

8

点错了

9

睡了，我明天做一下

10

@360病毒 这个和提高小班的拿到题目一样吗？

11

啥意思？

12

@360病毒 就是这道题目和提高小班里面的拿到题目一样？

13

是的，是周六的T7

14

这就非常好玩了
image

16

是判断条件有问题

17

这是判断条件

	if(mp.find(r)==mp.end()){
		if(mp.find(l)==mp.end()||lca(mp[l]+1,check(r))<f[0][mp[l]]) cout<<"maybe"<<endl;
		else cout<<"false"<<endl;			
	}else if(mp.find(l)!=mp.end()){
		if(f[0][mp[l]]<f[0][mp[r]]||lca(mp[l]+1,mp[r]-1)>=f[0][mp[r]]) cout<<"false"<<endl;
		else if(r-l==mp[r]-mp[l]) cout<<"true"<<endl;
		else cout<<"maybe"<<endl;			
	}else{
		if(lca(check(l)+1,mp[r]-1)>=f[0][mp[r]]) cout<<"false"<<endl;
		else cout<<"maybe"<<endl;			
	}

if(右端点不存在){
    if(左端点不存||降雨量比最大值要大) cout<<"maybe"<<endl;
    else cout<<"false"<<endl;
}else if(左端点存在){
    if(右端点比左端点大||右端点不是最大值) cout<<"false"<<endl;
    else if(所有年份已知) cout<<"true"<<endl;
    else cout<<"maybe"<<endl;
}else{
    if(右端点不是最大值) cout<<"false"<<endl;
    else cout<<"maybe"<<endl;
}
//最大值用倍增求，找左右端点用二分
18

为什么我那样不行？

19

因为你情况考虑太少

20

有一点不理解，右端点不存在为什么不一定是maybe呢？

21

具体哪个？