求助
  • 板块灌水区
  • 楼主Habseligkeit
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/17 23:05
  • 上次更新2023/10/24 00:32:11
查看原帖
求助
545516
Habseligkeit楼主2023/2/17 23:05

求各位帮我纠一下错。调了一晚上了,脑子宕机了。感恩,感谢。

题面 代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
ll ans;
int a[N] , b[N] , p[N] , q[N] , tp , tq , n;
int l[N] , r[N] , cnt[N] , c[N];

int main() {
	ios::sync_with_stdio(false);
	
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> a[i];
	
	int Max , k;
	for(int i = 0; i < n; i ++) if(a[i] > Max) k = i , Max = a[i];
	
	for(int i = 0; i < n; i ++) b[i] = a[(i + k) % n];
	
	
	for(int i = 0; i < n; i ++) {
		while(tp && b[p[tp]] <= b[i]) tp --;
		if(tp) l[i] = p[tp];
		else l[i] = -1;
		p[++ tp] = i;
	}
	for(int i = n - 1; i >= 0; i --) {
		while(tq && b[q[tq]] <= b[i]) {
			if(b[q[tq]] == b[i]) cnt[i] += cnt[q[tq]] + 1;
			tq --;
		}
		if(tq) r[i] = q[tq];
		else r[i] = n;
		q[++ tq] = i;
	}
	
	/*for(int i = 0; i < n; i ++) cout << l[i] << ' ';
	cout << endl;
	for(int i = 0; i < n; i ++) cout << r[i] << ' ';
	cout << endl;
	for(int i = 0; i < n; i ++) cout << cnt[i] << ' ';
	cout << endl;*/
	
	for(int i = 0; i < n; i ++) {
		ans += cnt[i];
		if(l[i] != -1 && r[i] != n) ans += 2;
		if(l[i] == -1 && r[i] != n) ans ++;
		if(l[i] != -1 && r[i] == n) {
			ans += 2;
			if(l[i] == 0) ans --;
		}
	}
	
	cout << ans << endl;
	return 0;
}
2023/2/17 23:05
加载中...