ABC247 E - Max Min

秒速五厘米 2024-03-23 10:57 194阅读 0赞

s b二分调 n m半天调不出来

不写了，写不了一点

直接贴别人代码算了

题意：

![16d036c1f6324a3a9812f9a2fd2c4148.png][]

思路：

![fd5fdc51641344b4b2acd46d03b6d8a1.png][]

Code：

#include <bits/stdc++.h>
    #define eps 1e-6
    typedef long long ll;
    using namespace std;
    const int INF = 1e9, N = 200010;
    
    inline int max(int a, int b){
    	return a > b ? a : b;
    }
    inline int min(int a, int b){
    	return a < b ? a : b;
    }
    
    int n, a[N], X, Y, mn[N][22], mx[N][22], lg[N];
    ll ans;
    
    int qmin(int l, int r){
    	int k = lg[r - l + 1];
    	return min(mn[l][k], mn[r - (1 << k) + 1][k]);
    }
    int qmax(int l, int r){
    	int k = lg[r - l + 1];
    	return max(mx[l][k], mx[r - (1 << k) + 1][k]);
    }
    
    int main(){
    
    	scanf("%d%d%d", &n, &X, &Y);
    	for(int i = 1; i <= n; i++){
    		scanf("%d", &a[i]);
    		mn[i][0] = mx[i][0] = a[i];
    	}
    	for(int i = 2; i < N; i++)
    		lg[i] = lg[i >> 1] + 1;
    	for(int j = 1; 1 << j <= n; j++)
    		for(int i = 1; i + (1 << j) - 1 <= n; i++)
    			mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    	for(int j = 1; 1 << j <= n; j++)
    		for(int i = 1; i + (1 << j) - 1 <= n; i++)
    			mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    	
    	for(int i = 1, l, r, mid, pos1, pos2, pos3, pos4; i <= n; i++){
    		if(qmin(i, n) > Y || qmax(i, n) < X) continue;
    		l = i, r = n;
    		while(l < r){
    			mid = (l + r) >> 1;
    			if(qmax(i, mid) >= X) r = mid;
    			else l = mid + 1;
    		}
    		pos1 = l;//r0_mx
    		l = i, r = n;
    		if(qmax(i, n) > X){
    			while(l < r){
    				mid = (l + r) >> 1;
    				if(qmax(i, mid) > X) r = mid;
    				else l = mid + 1;
    			}
    			pos2 = l;//r1_mx
    		}
    		else pos2 = n + 1;
    		
    		l = i, r = n;
    		while(l < r){
    			mid = (l + r) >> 1;
    			if(qmin(i, mid) <= Y) r = mid;
    			else l = mid + 1;
    		}
    		pos3 = l;//r0_mi
    		
    		l = i, r = n;
    		if(qmin(i, n) < Y){
    			while(l < r){
    				mid = (l + r) >> 1;
    				if(qmin(i, mid) < Y) r = mid;
    				else l = mid + 1;
    			}
    			pos4 = l;//r1_mi
    		}
    		else pos4 = n + 1;
    		cout<<pos3<<" "<<pos4<<" "<<pos1<<" "<<pos2<<'\n';
    		if(qmax(i, pos1) != X || qmin(i, pos3) != Y) continue;
    		pos1 = max(pos1, pos3);
    		pos2 = min(pos2, pos4);
    		if(pos1 <= pos2) ans += pos2 - pos1;
    	}
    	printf("%lld\n", ans);
    
    	return 0;
    }

[16d036c1f6324a3a9812f9a2fd2c4148.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/53a173951f8c47c68e4289fa93e41ee6.png
[fd5fdc51641344b4b2acd46d03b6d8a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/56f3a34b8f2f422c9bcef470aef347b3.png