Codeforces 1313 C. Skyscrapers (단조 로 운 대기 열 또는 RMQ)
52385 단어 데이터 구조 - 단조 로 운 대기 열CodeForces
The outskirts of the capital are being actively built up in Berland. The company “Kernel Panic” manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought n plots along the highway and is preparing to build n skyscrapers, one skyscraper per plot.
Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.
Formally, let’s number the plots from 1 1 1 to n n n. Then if the skyscraper on the i-th plot has a i a_i ai floors, it must hold that ai is at most m i ( 1 ≤ a i ≤ m i ) m_i (1≤a_i≤mi) mi(1≤ai≤mi). Also there mustn’t be integers j j j and k k k such that j < i < k jj
Input
The first line contains a single integer n ( 1 ≤ n ≤ 500000 ) n (1≤n≤500000) n(1≤n≤500000) — the number of plots.
The second line contains the integers m 1 , m 2 , … , m n ( 1 ≤ m i ≤ 1 0 9 ) m_1,m_2,…,m_n (1≤m_i≤10^9) m1,m2,…,mn(1≤mi≤109) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.
Output
Print n n n integers a i a_i ai — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.
If there are multiple answers possible, print any of them.
Examples
input
5 1 2 3 2 1
output
1 2 3 2 1
input
3 10 6 8
output
10 6 6
Note
In the first example, you can build all skyscrapers with the highest possible height.
In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer [ 10 , 6 , 6 ] [10,6,6] [10,6,6] is optimal. Note that the answer of [ 6 , 6 , 8 ] [6,6,8] [6,6,8] also satisfies all restrictions, but is not optimal.
제목:
길이 가 n n n 인 서열 을 제시 하고 이 서열 을 그 어떠한 요소 에 도 존재 하지 않 는 양쪽 이 그 보다 큰 서열 로 바 꾸 는 것 은 바로 역 v v 와 유사 하 며 C 1 C1 C1 데이터 가 매우 작 아서 어떻게 해도 된다.복잡 도가 더 낮은 방법 은 단조 로 운 대기 열 로 피크 수 치 를 유지 한 다음 n n 개 수 를 유지 한 후에 다시 한 번 찾 고 가장 큰 것 을 찾 는 것 입 니 다. 구체 적 인 조작 은 코드 를 볼 수 있 습 니 다.
AC 코드:
#include
", n)
#define pc(n) printf("%c", n)
#define pdd(n, m) printf("%d %d
", n, m)
#define pld(n) printf("%lld
", n)
#define pldd(n, m) printf("%lld %lld
", n, m)
#define sld(n) scanf("%lld", &n)
#define sldd(n, m) scanf("%lld%lld", &n, &m)
#define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
#define sf(n) scanf("%lf", &n)
#define sc(n) scanf("%c", &n)
#define sff(n, m) scanf("%lf%lf", &n, &m)
#define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
#define ss(str) scanf("%s", str)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, n, a) for (int i = n; i >= a; i--)
#define mem(a, n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mod(x) ((x) % MOD)
#define gcd(a, b) __gcd(a, b)
#define lowbit(x) (x & -x)
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
inline int read()
{
int ret = 0, sgn = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
sgn = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret * sgn;
}
inline void Out(int a) //Êä³öÍâ¹Ò
{
if (a > 9)
Out(a / 10);
putchar(a % 10 + '0');
}
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
return a * b / gcd(a, b);
}
/// m^k%mod
ll qpow(ll x, ll n, ll mod)
{
if (n == 0)
return 1;
ll res = qpow((x * x) % mod, n / 2, mod) % mod;
if (n & 1)
res = (res * x) % mod;
return res % mod;
}
//
int Fermat(int a, int p) // a b
{
return qpow(a, p - 2, p);
}
///
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll g = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return g;
}
const int N = 500010;
ll a[N], b[N], x[N], y[N], ans, sum;
int tmp, n, pos = 0, res[N];
int main()
{
sd(n);
pos = 0;
rep(i, 1, n)
{
sld(a[i]);
b[i] = a[i];
}
sum = pos = 0;
rep(i, 1, n)
{
while (pos && b[i] <= b[res[pos]])
{
sum -= 1ll * (res[pos] - res[pos - 1]) * b[res[pos]];
pos--;
}
res[++pos] = i;
sum += 1ll * (res[pos] - res[pos - 1]) * b[i];
x[i] = sum;
}
for (int i = 1; i * 2 <= n; ++i)
{
swap(b[i], b[n - i + 1]);
}
sum = pos = 0;
rep(i, 1, n)
{
while (pos && b[i] <= b[res[pos]])
{
sum -= 1ll * (res[pos] - res[pos - 1]) * b[res[pos]];
pos--;
}
res[++pos] = i;
sum += 1ll * (res[pos] - res[pos - 1]) * b[i];
y[i] = sum;
}
rep(i, 1, n)
{
if (ans < x[i] + y[n - i + 1] - a[i])
{
ans = x[i] + y[n - i + 1] - a[i];
tmp = i;
}
}
per(i, tmp - 1, 1)
{
a[i] = min(a[i], a[i + 1]);
}
rep(i, tmp + 1, n)
{
a[i] = min(a[i], a[i - 1]);
}
rep(i, 1, n)
printf("%lld ", a[i]);
printf("
");
return 0;
}
다음은 더 잘 이해 할 수 있 는 RMQ 방법 을 배 웠 습 니 다. 전체적인 사고방식 은 똑 같 습 니 다. 바로 유지 하기 가 비교적 간단 하 다 는 것 입 니 다.
먼저 RMQ 에서 데 이 터 를 처리 하고 모든 위치 에 대해 2 분 동안 현재 위치 에서 가장 가 까 운 위 치 를 찾 습 니 다. 예 를 들 어 53454 보다 작은 위 치 를 찾 습 니 다. 마지막 4 에 대해 3 을 찾 는 것 은 바로 53454 를 53444 로 바 꾸 는 것 입 니 다. 첫 번 째 는 자신 보다 작 아서 자신의 중간 부분 과 똑 같 습 니 다.
prei 는 i 를 최고점 으로 1 - i 를 증가 시 키 는 최소 비용 이 고, suf 는 i 를 최고점 으로 i - n 을 감소 시 키 는 최소 비용 이다.그리고 모든 위 치 를 최고치 로 하 는 최소 비용 을 한 번 훑 어보 면 된다.
AC 코드:
const int N = 500010;
int n, x, y;
ll a[N];
ll dp[N][25];
ll pre[N], suf[N];
void rmq_init()
{
for (int i = 1; i <= n; i++)
dp[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
}
ll rmq_query(int l, int r)
{
int k = log2(r - l + 1);
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
void solve(ll t[])
{
t[1] = a[1];
rep(i, 2, n)
{
if (rmq_query(1, i - 1) >= a[i])
t[i] = i * a[i]; // ， 。
else
{
int l = 1, r = i - 1, ans, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (rmq_query(mid, r) < a[i]) //
l = mid + 1, ans = mid;
else
r = mid - 1;
}
t[i] = (i - ans) * a[i] + t[ans];
}
}
}
int main()
{
sd(n);
rep(i, 1, n)
sld(a[i]);
rmq_init();
solve(pre);
reverse(a + 1, a + 1 + n);
rmq_init();
solve(suf);
int id;
ll ans = 0;
reverse(a + 1, a + 1 + n);
rmq_init();
rep(i, 1, n)
{
if (pre[i] + suf[n - i + 1] - a[i] > ans)
{
ans = pre[i] + suf[n - i + 1] - a[i];
id = i;
}
}
rep(i, 1, id)
{
printf("%lld ", rmq_query(i, id));
}
vector<ll> rec;
per(i, n, id + 1)
rec.pb(rmq_query(id, i));
int len = rec.size();
per(i, len - 1, 0)
printf("%lld ", rec[i]);
puts("");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2019-2020 ICPC North-Western Russia Regional Contest[부분 문제풀이]나무 한 그루를 정하고 m개의 관건을 제시하면 이 점에서 m개의 관건까지의 거리가 같을 수 있는 점을 찾아낼 수 있다 (2) 문제는 하나의 점을 찾는 것으로 전환할 수 있다. 모든 관건점을 그 거리의 최대치로 최소화...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
