Hướng dẫn giải của CP GBUP


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include<bits/stdc++.h>
#define int long long 
using namespace std;
struct Sus
{
    priority_queue<pair<int, int>> left_part, delete_left_part;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> right_part, delete_right_part;
    int sum_left = 0, sum_right = 0;
    void init()
    {
        sum_left = sum_right = 0;
        while(left_part.size() > 0) left_part.pop();
        while(right_part.size() > 0) right_part.pop();
        while(delete_left_part.size() > 0) delete_left_part.pop();
        while(delete_right_part.size() > 0) delete_right_part.pop();
    }
    void add(pair<int, int> v){
        if(right_part.size() == 0 || v < right_part.top()){
            left_part.push(v); sum_left += v.second;
        }
        else{
            right_part.push(v); sum_right += v.second;
        }
    }
    void del(pair<int, int> v){
        if(right_part.size() == 0 || v < right_part.top()){
            sum_left -= v.second;
            if(left_part.size() > 0 && left_part.top() == v) left_part.pop();
            else delete_left_part.push(v);
        }
        else{
            sum_right -= v.second;
            if(right_part.size() > 0 && right_part.top() == v) right_part.pop();
            else delete_right_part.push(v);
        }
    }
    void clean_left(){
        while(delete_left_part.size() > 0 && left_part.top() == delete_left_part.top()){
            left_part.pop(); delete_left_part.pop(); 
        }
    }
    void clean_right(){
        while(delete_right_part.size() > 0 && right_part.top() == delete_right_part.top()){
            right_part.pop(); delete_right_part.pop(); 
        }
    }
    void balance(){
        while(sum_left < sum_right){
            clean_right();
            pair<int, int> v = right_part.top(); right_part.pop();
            sum_left += v.second; sum_right -= v.second;
            left_part.push(v);
        }
        while(sum_left > sum_right){
            clean_left();
            pair<int, int> v = left_part.top(); left_part.pop();
            sum_right += v.second; sum_left -= v.second;
            right_part.push(v);
        }
    }
    int maxval(){
        balance();
        int ans = sum_left * sum_right;
        clean_right();
        pair<int, int> v = right_part.top(); //This should always exist
        ans = max(ans, (sum_left + v.second) * (sum_right - v.second));
        return ans;
    }
    inline int sz(){return left_part.size() + right_part.size();}
    vector<pair<int, int>> all_element(){
        vector<pair<int, int>> ans;
        while(left_part.size() > 0){
            clean_left();
            if(left_part.size() == 0) break;
            ans.push_back(left_part.top()); left_part.pop();
        }
        while(right_part.size() > 0){
            clean_right();
            if(right_part.size() == 0) break;
            ans.push_back(right_part.top()); right_part.pop();
        }
        init();
        return ans;
    }
};
const int maxlen = 12;
signed main()
{
    int n, q; cin>>n>>q;

    auto encode = [&](string s) -> pair<int, int>{
        int num = 0, sum = 0;
        for(int i = 0; i < s.size(); i++) sum += s[i] - 'a' + 1001;
        while(s.size() < maxlen) s.push_back('a' - 1);
        for(int i : s) num = num * 27 + i; //This is smaller than 2e17
        return make_pair(num, sum);
    };

    vector<Sus> st(n+5);
    for(int i = 1; i <= n; i++){
        int m; cin>>m;
        for(int j = 1; j <= m; j++){
            string s; cin>>s;
            st[i].add(encode(s));
        }
    }

    for(int test = 0; test < q; test++){
        int type; cin>>type;
        if(type == 1){
            int p; string s; cin>>p>>s;
            st[p].add(encode(s));
        }
        else if(type == 2){
            int p; string s; cin>>p>>s;
            st[p].del(encode(s));
        }
        else if(type == 3){
            int u, v; cin>>u>>v;
            if(st[u].sz() > st[v].sz()){
                swap(st[u].sum_left, st[v].sum_left);
                swap(st[u].sum_right, st[v].sum_right);
                st[u].left_part.swap(st[v].left_part);
                st[u].right_part.swap(st[v].right_part);
                st[u].delete_left_part.swap(st[v].delete_left_part);
                st[u].delete_right_part.swap(st[v].delete_right_part);
            }
            vector<pair<int, int>> val = st[u].all_element();
            for(pair<int, int> i : val) st[v].add(i);
        }
        else{
            int p; cin>>p;
            cout<<st[p].maxval()<<'\n';
        }
    }
}

Đang tải...