首页 > 其他 > 详细

CodeForces 1454F 线段树+二分

时间:2021-03-09 14:35:03      阅读:34      评论:0      收藏:0      [点我收藏+]

难得自己想出最后一题,十分开心的来写题解。

题目给我们一段数组,然后让我们将其分为三段,使得第一段的最大值等于第二段的最小值等于第三段的最大值。

这种区间问题显而易见就得用一些对区间操作的数据结构比如st表树状数组啥的,我比较喜欢线段树那必然就用线段树了。

要寻找的话用n^2的枚举显然是不现实的,所以本蒟蒻便考虑二分答案,先枚举出第一段的位置,再二分出第二段的位置,时间复杂度大概是nlognlogn。

#include<iostream>
#include<algorithm>
using namespace std;
int all[2000005];
struct node {
    int l, r, maxx, minn;
}a[2000005];
void up_data(int i) {
    a[i].maxx = max(a[i << 1].maxx, a[i << 1 | 1].maxx);
    a[i].minn = min(a[i << 1].minn, a[i << 1 | 1].minn);
    return;
}
void build(int l, int r,int i) {
    a[i].l = l; a[i].r = r;
    if (l == r) {
        a[i].maxx = all[l];
        a[i].minn = all[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, i << 1);
    build(mid + 1, r, i << 1 | 1);
    up_data(i);
}
int find_max(int l, int r, int i) {
    if (a[i].l >= l && a[i].r <= r) {
        return a[i].maxx;
    }
    int now = 0;
    if (a[i << 1].r >= l)now = max(now, find_max(l, r, i << 1));
    if (a[i << 1 | 1].l <= r)now = max(now, find_max(l, r, i << 1 | 1));
    return now;
}
int find_min(int l, int r, int i) {
    if (a[i].l >= l && a[i].r <= r) {
        return a[i].minn;
    }
    int now = 0x7fffffff;
    if (a[i << 1].r >= l)now = min(now, find_min(l, r, i << 1));
    if (a[i << 1 | 1].l <= r)now = min(now, find_min(l, r, i << 1 | 1));
    return now;
}
int main() {
    int t; cin >> t;
    while (t--) {
        int n, flag = 0; cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> all[i];
        build(1, n, 1);
        for (int i = 1; i <= n; i++) {
            int here = find_max(1, i, 1);
            int l = i + 1, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                int s = find_min(i + 1 , mid, 1);
                int last = find_max(mid + 1, n, 1);
                if (s == here && last == here)
                {
                    flag = 1;
                    cout << "YES" << endl;
                    cout << i << " " << mid - i << " " << n - mid << endl;
                    break;
                }
                else if (s <= here && last <= here) {
                    r = mid - 1;
                }
                else if (s >= here && last >= here)l = mid + 1;
                else break;
            }
            if (flag)break;
        }
        if(!flag)
        cout << "NO" << endl;
    }
    return 0;
}

 

CodeForces 1454F 线段树+二分

原文:https://www.cnblogs.com/redintoncforever/p/14504784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!