UESTC 1593 老司机破阵 优先队列+双端链表

老司机破阵优先队列+双端链表

Source

2017 UESTC Training for Data Structures

My Solution

优先队列+双端链表
cf原题，直接贴的以前的代码
反向做，按着反的顺序把元素一个一个的添加进去，用priority_queue 维护当前最值，
用双向链表维护当前区间的状态，L[i]表示以i为端点的区间的区间左端点，
R[i]表示以i为区间端点的右端点。
对于每个点 j，当只R[i + 1] != 0 时，右边有区间，可以把两个链表合并成一个，
R[i] = R[i + 1], L[i] = i;
当只L[i - 1] != 0 时，左边有区间，可以把两个链表合并成一个，
R[L[i - 1]] = i, R[i] = i, L[i] = L[i - 1]
当两边都有区间时，先合并一边，再合并另一边最后得到的区间是 [ L[i - 1]， R[i + 1] ];
然后根据合并来的区间得到新的区间和，push到priority_queue里，这个和必定比原来分开的子区间大，
所以原来的子区间和就留在pq里不用管了。最多维护n个元素。
区间和用 map<pair<int, int>, LL> mp,来维护， mp[ii(i, i)] = a[per[i]];，
然后 mp[ii(l, r)]就用来维护新的区间的和，然后push到pq里。
复杂度 O(nlogn)

#include 
#include 
#include 
#include 

#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int maxn = 1e5 + 8;

priority_queue pq;
map<ii, LL> mp;

LL a[maxn], per[maxn], L[maxn], R[maxn], ans[maxn];

int main()
{
    #ifdef LOCAL
    freopen("k.txt", "r", stdin);
    //freopen("k.out", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    LL n, l, r, sum;
    //cin >> n;
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++){ //cin >> a[i];
        scanf("%lld", &a[i]);
    }
    for(int i = 1; i <= n; i++){ //cin >> per[i];
        scanf("%lld", &per[i]);
    }

    for(int i = n; i > 0; i--){
        if(i == n){
            L[per[n]] = per[n];
            R[per[n]] = per[n];
            mp[ii(per[n], per[n])] = a[per[n]];
            pq.push(a[per[n]]);
            ans[n] = 0;
        }
        else{
            ans[i] = pq.top();
            sum = a[per[i]];
            l = per[i], r = per[i];
            L[l] = l, R[l] = l;
            if(L[per[i]+1] != 0){
                L[per[i]] = per[i];
                R[per[i]] = R[per[i]+1];
                L[R[per[i]+1]] = per[i];
                r = R[per[i]];
                sum += mp[ii(per[i]+1, r)];
            }
            if(R[per[i]-1] != 0){
                if(R[per[i]] != 0){
                    R[L[per[i]-1]] = R[per[i]];
                    L[R[per[i]]] = L[per[i]-1];
                    l = L[per[i]-1];
                    sum += mp[ii(l, per[i]-1)];

                }
                else{
                    R[L[per[i]-1]] = per[i];
                    R[per[i]] = per[i];
                    L[per[i]] = L[per[i]-1];
                    l = L[per[i]-1];
                    sum += mp[ii(l, per[i]-1)];
                }

            }
            mp[ii(l, r)] = sum;
            pq.push(sum);
        }
    }

    for(int i = 1; i <= n; i++){
        //cout << ans[i] << "n";
        printf("%lldn", ans[i]);
    }
    #ifdef LOCAL
    memset(L, 0, sizeof L);
    memset(R, 0, sizeof R);
    mp.clear();
    while(!pq.empty()) pq.pop();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 1593 老司机破阵优先队列+双端链表

老司机破阵优先队列+双端链表

Source

My Solution

相关推荐

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) C. Destroying Array 双向链表+反向做+优先队列

Gym – 100507H H. Pair: normal and paranormal 栈

UESTC 1595 老司机的毒奶贪心+二叉树+优先队列

UESTC 2016 Summer Training #1 Div.2 J – Objects Panel (A) dfs、按条件遍历树、interesting

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1593 老司机破阵 优先队列+双端链表

老司机破阵 优先队列+双端链表

Source

My Solution

相关推荐

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) C. Destroying Array 双向链表+反向做+优先队列

Gym – 100507H H. Pair: normal and paranormal 栈

UESTC 1595 老司机的毒奶 贪心+二叉树+优先队列

UESTC 2016 Summer Training #1 Div.2 J – Objects Panel (A) dfs、按条件遍历树、interesting

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1593 老司机破阵优先队列+双端链表

老司机破阵优先队列+双端链表

UESTC 1595 老司机的毒奶贪心+二叉树+优先队列