首页 > 代码库 > 第十四周 Leetcode 315. Count of Smaller Numbers After Self(HARD) 主席树
第十四周 Leetcode 315. Count of Smaller Numbers After Self(HARD) 主席树
Leetcode315
题意很简单,给定一个序列,求每一个数的右边有多少小于它的树。 O(n^2)的算法是显而易见的。
用普通的线段树可以优化到O(nlogn)
我们可以直接套用主席树的模板。
主席树的功能是什么呢? 其实就是一句话。
原序列a的子序列a[l,r]在a排序后的序列b的子序列[L,R]中的个数。
显然本题只用到了主席树的一小部分功能。
const int N = 100000 + 5; int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20]; class Solution { public: int n, k, tot, sz, ql, qr, x, q, T; vector<int>out; void Build(int& o, int l, int r){ if(l>r)return ; o = ++ tot; sum[o] = 0; if(l == r) return; int m = (l + r) >> 1; Build(ls[o], l, m); Build(rs[o], m + 1, r); } int update(int& o, int l, int r, int last, int p){ o = ++ tot; ls[o] = ls[last]; rs[o] = rs[last]; sum[o] = sum[last] + 1; if(l == r) return l; int m = (l + r) >> 1; if(p <= b[m]) return update(ls[o], l, m, ls[last], p); else return update(rs[o], m + 1, r, rs[last], p); } int query(int ss, int tt, int l, int r, int k){ if(l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]]; if(k <= cnt) return query(ls[ss], ls[tt], l, m, k); else return query(rs[ss], rs[tt], m + 1, r, k - cnt); } int sumq(int cur,int l1,int r1,int l,int r) { if(l1<0||r1<0)return 0; if(l1<=l&&r1>=r)return sum[cur]; int mid=(l+r)/2; int ans=0; if(l1<=mid)ans+= sumq(ls[cur],l1,r1,l,mid); if(r1>mid)ans+= sumq(rs[cur],l1,r1,mid+1,r); return ans; } vector<int> countSmaller(vector<int>& nums){//freopen("t.txt","r",stdin); T=1; while(T--){ for(int i = 0; i < nums.size(); i ++)b[i] = nums[i]; sort(b , b + (int)nums.size()); out.resize((int)nums.size()); sz = unique(b , b +(int)nums.size()) - (b ); sz--; tot=0; Build(rt[nums.size()],0, sz); for(int i = nums.size()-1; i >= 0; i --) { int loc=update(rt[i], 0, sz, rt[i + 1], nums[i]); out[i]=sumq(rt[i],0,loc-1,0,sz); } } return out; } };
如果对主席树有兴趣 可以看看POJ2104
第十四周 Leetcode 315. Count of Smaller Numbers After Self(HARD) 主席树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。