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

My Solution

双向链表+反向做+优先队列

反向做，按着反的顺序把元素一个一个的添加进去，用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("c.txt", "r", stdin);
    //freopen("c.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;
    for(int i = 1; i <= n; i++){ cin >> a[i];
    }
    for(int i = 1; i <= n; i++){ cin >> 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";
    }
    #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

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

相关推荐

Codeforces Round #376 (Div. 2) F. Video Cards 数论+数据结构+前缀和

2016 UESTC Training for Data Structures D – 卿学姐与魔法优先队列、构造

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum 离线操作，树状数组，last[value]，异或和

HDU – 3487 Play with Chain __ Splay

共有 0 条评论

公告

游戏服务器开发 最新文章

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

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

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

公众号

推荐系统开发 最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

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

相关推荐

Codeforces Round #376 (Div. 2) F. Video Cards 数论+数据结构+前缀和

2016 UESTC Training for Data Structures D – 卿学姐与魔法 优先队列、构造

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum 离线操作，树状数组，last[value]，异或和

HDU – 3487 Play with Chain __ Splay

共有 0 条评论

公告

游戏服务器开发最新文章

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

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

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

公众号

推荐系统开发最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

2016 UESTC Training for Data Structures D – 卿学姐与魔法优先队列、构造