首页 > 其他分享 >lc493 统计重要翻转对的数目

lc493 统计重要翻转对的数目

时间:2024-03-16 10:34:22浏览次数:25  
标签:node return int data son lc493 TYPE 数目 翻转

给定一个数组nums[n],如果i<j并且nums[i]>2*nums[j],则称(i,j)是一个重要翻转对。求nums[n]中重要翻转对的数量。
1<=n<=5e4; nums[i]在int范围内

直接套平衡树模板即可。

template <typename TYPE>
struct Treap {
    struct Node {
        TYPE data, sum;
        int rnd, siz, dup, son[2];
        void init(const TYPE & d) {
            data = sum = d;
            rnd = rand();
            siz = dup = 1;
            son[0] = son[1] = 0;
        }
    };
    Treap(size_t sz, bool multi):multiple(multi) {
        node.resize(sz);
        reset();
    }
    int newnode(const TYPE & d) {
        total += 1;
        node[total].init(d);
        return total;
    }
    void reset() { root = total = 0; }
    void maintain(int x) {
        node[x].siz = node[x].dup;
        node[x].sum = node[x].data * node[x].dup;
        if (node[x].son[0]) {
            node[x].siz += node[node[x].son[0]].siz;
            node[x].sum += node[node[x].son[0]].sum;
        }
        if (node[x].son[1]) {
            node[x].siz += node[node[x].son[1]].siz;
            node[x].sum += node[node[x].son[1]].sum;
        }
    }
    void rotate(int d, int &r) {
        int k = node[r].son[d^1];
        node[r].son[d^1] = node[k].son[d];
        node[k].son[d] = r;
        maintain(r);
        maintain(k);
        r = k;
    }
    void insert(const TYPE &data, int &r, bool &ans) {
        if (r) {
            if (!(data < node[r].data) && !(node[r].data < data)) {
                ans = false;
                if (multiple) {
                    node[r].dup += 1;
                    maintain(r);
                }
            } else {
                int d = data < node[r].data ? 0 : 1;
                insert(data, node[r].son[d], ans);
                if (node[node[r].son[d]].rnd > node[r].rnd) {
                    rotate(d^1, r);
                } else {
                    maintain(r);
                }
            }
        } else {
            r = newnode(data);
        }
    }
    void getkth(int k, int r, TYPE& data) {
        int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
        int y = node[r].dup;
        if (k <= x) {
            getkth(k, node[r].son[0], data);
        } else if (k <= x + y) {
            data = node[r].data;
        } else {
            getkth(k-x-y, node[r].son[1], data);
        }
    }
	TYPE getksum(int k, int r) {
        if (k <= 0 || r == 0) return 0;
		int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
		int y = node[r].dup;
        if (k <= x) return getksum(k, node[r].son[0]);
        if (k <= x+y) return node[node[r].son[0]].sum + node[r].data * (k-x);
        return node[node[r].son[0]].sum + node[r].data * y + getksum(k-x-y,node[r].son[1]);
	}
    void erase(const TYPE& data, int & r) {
        if (r == 0) return;
        int d = -1;
        if (data < node[r].data) {
            d = 0;
        } else if (node[r].data < data) {
            d = 1;
        }
        if (d == -1) {
            node[r].dup -= 1;
            if (node[r].dup > 0) {
                maintain(r);
            } else {
                if (node[r].son[0] == 0) {
                    r = node[r].son[1];
                } else if (node[r].son[1] == 0) {
                    r = node[r].son[0];
                } else {
                    int dd = node[node[r].son[0]].rnd > node[node[r].son[1]].rnd ? 1 : 0;
                    rotate(dd, r);
                    erase(data, node[r].son[dd]);
                }
            }
        } else {
            erase(data, node[r].son[d]);
        }
        if (r) maintain(r);
    }
    int ltcnt(const TYPE& data, int r) {
        if (r == 0) return 0;
        int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
        if (data < node[r].data) {
            return ltcnt(data, node[r].son[0]);
        }
        if (!(data < node[r].data) && !(node[r].data < data)) {
            return x;
        }
        return x + node[r].dup + ltcnt(data, node[r].son[1]);
    }
    int gtcnt(const TYPE& data, int r) {
        if (r == 0) return 0;
        int x = node[r].son[1] ? node[node[r].son[1]].siz : 0;
        if (data > node[r].data) {
            return gtcnt(data, node[r].son[1]);
        }
        if (!(data < node[r].data) && !(node[r].data < data)) {
            return x;
        }
        return x + node[r].dup + gtcnt(data, node[r].son[0]);
    }
    int count(const TYPE& data, int r) {
        if (r == 0) return 0;
        if (data < node[r].data) return count(data, node[r].son[0]);
        if (node[r].data < data) return count(data, node[r].son[1]);
        return node[r].dup;
    }
    void prev(const TYPE& data, int r, TYPE& result, bool& ret) {
        if (r) {
            if (node[r].data < data) {
                if (ret) {
                    result = max(result, node[r].data);
                } else {
                    result = node[r].data;
                    ret = true;
                }
                prev(data, node[r].son[1], result, ret);
            } else {
                prev(data, node[r].son[0], result, ret);
            }
        }
    }
    void next(const TYPE& data, int r, TYPE& result, bool& ret) {
        if (r) {
            if (data < node[r].data) {
                if (ret) {
                    result = min(result, node[r].data);
                } else {
                    result = node[r].data;
                    ret = true;
                }
                next(data, node[r].son[0], result, ret);
            } else {
                next(data, node[r].son[1], result, ret);
            }
        }
    }
    vector<Node> node;
    int root, total;
    bool multiple;
    bool insert(const TYPE& data) {
        bool ret = true;
        insert(data, root, ret);
        return ret;
    }
    bool kth(int k, TYPE &data) {
        if (!root || k <= 0 || k > node[root].siz)
            return false;
        getkth(k, root, data);
        return true;
    }
	TYPE ksum(int k) {
        assert(root && k>0 && k<=node[root].siz);
        return getksum(k, root);
    }
    int count(const TYPE &data) {
        return count(data, root);
    }
    int size() const {
        return root ? node[root].siz : 0;
    }
    void erase(const TYPE& data) {
        return erase(data, root);
    }
    int ltcnt(const TYPE& data) {
        return ltcnt(data, root);
    }
    int gtcnt(const TYPE& data) {
        return gtcnt(data, root);
    }
    bool prev(const TYPE& data, TYPE& result) {
        bool ret = false;
        prev(data, root, result, ret);
        return ret;
    }
    bool next(const TYPE& data, TYPE& result) {
        bool ret = false;
        next(data, root, result, ret);
        return ret;
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        Treap<long long> tp(50005, true);
        int ans = 0;
        for (auto i : nums) {
            ans += tp.gtcnt(2LL * i);
            tp.insert(i);
        }
        return ans;
    }
};

标签:node,return,int,data,son,lc493,TYPE,数目,翻转
From: https://www.cnblogs.com/chenfy27/p/18076788

相关文章

  • 代码随想录算法训练营第七天|LeetCode 344.反转字符串、541.反转字符串II、卡码网54.替
    344.反转字符串题目描述:​编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用O(1)的额外空间解决这一问题。示例一:输入:s=["h","e","l","l","o"]输出:["o","l","l......
  • 【OJ】K 个一组翻转链表
    题目基本思路:用计数+栈实现分段,K个一组地翻转链表。#include<bits/stdc++.h>#include<stack>usingnamespacestd;structlist_node{intval;structlist_node*next;};list_node*input_list(){intval,n;scanf("%d",&n);list_node*phea......
  • K 个一组翻转链表
    题目:structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}ListNode(int_val):val(_val),next(nullptr){}ListNode(int_val,ListNode*_next):val(_val),next(_next){}};classSolution{public:ListNod......
  • 郑莉cpp习题6-22 用递归算法翻转字符串s
    郑莉cpp习题6-22  用递归算法翻转字符串s#include<iostream>usingnamespacestd;#include<string>voidreverse(string&s,intleft,intright){chart;if(left<right){t=s[left];s[left]=s[right];s[right......
  • [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
    这肯定是学证明了,看这篇文章补充一下细节首先,\(m\)的范围应该是\([0,b-1]\)然后,当\(m\)取不同值的时候,\(ma\)%\(b\)一定为不同值(这个性质确实有点奇特,可以记下来)反证,如果\(m_1a\equivm_2a\:(mod\:b)\)且\(0≤m_1<m_2≤b-1\),那么就有\(b|(m_2-m_1)a\),题目给出了\(a,b\)互质,......
  • 每天一道蓝桥杯 Day2 翻转+阶乘求和
    阶乘求和 只要后9位的话,那就只考虑后9位!如何只算后9位?有一个很经典的运算:取模。回想入门c语言时做过一道题,给定三位数,要求进行数字翻转。比如给定n,n=123,要翻转成321。一个做法是令a1=n%10,a2=(n%100)/10,a3=n/100输出a1*100+a2*10+a3即可。所以遇到求一个很大的值除以某数......
  • 代码随想录 第十五天 | ● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2 感
    leetcode:102.二叉树的层序遍历-力扣(LeetCode)思路:用队列长度控制弹栈的多少,不等于空时获取root,因为传了一个根肯定是1,接下来找左右节点,将根节点弹出,获取下一次的size,一直到空。。。//102.二叉树的层序遍历classSolution{publicList<List<Integer>>resList=newA......
  • 【C++】翻转二叉树(递归、非递归)
    //使用递归翻转二叉树TreeNode*reverseTree(TreeNode*root){if(!root)returnroot;swap(root->left,root->right);reverseTree(root->left);reverseTree(root->right);returnroot;}//使用队列翻转二叉树层序遍历TreeNode*invertTree(TreeNode*root)......
  • 226. 翻转二叉树 c
    层次遍历的题目C写吐血了,缓一缓再写那种气死人的题目。/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/voidreverseroot(structTreeNode*root){if(!root)......
  • 代码随想录 第八天 | 344.反转字符串 ● 541. 反转字符串II ● 卡码网:54.替换数字 ●
    LeetCode:344.反转字符串-力扣(LeetCode)思路:双指针的想法用while循环遍历两侧指针,效率高classSolution{publicvoidreverseString(char[]s){inti=0,j=s.length-1;while(i<j){chartemp;temp=s[j];......