admin管理员组

文章数量:1516870

CF 625D 树状数组

题意：给N条线段，保证它们的右端点互不相同，对于每条线段，求它覆盖的线段的数量。 1=<N<=2e5 -1e9 ≤ li < ri ≤ 1e9

思路：用结构体存下所有线段的左端点和右端点以及下标，然后对结构体进行排序，使右端点从小到大排序，对右端点离散化（f [ i ] . r = i）。然后按左端点递减重新排序,如果两个左端点相等，则使右端点小的排在前面，最后就套用树状数组不断更新sum数组就可以了。 

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<string>#include<iostream>typedeflonglong LL;
using namespace std;int t,n,m;constint maxx=2e5+10;int sum[maxx];int ans[maxx];struct node
{int l,r,op;}f[maxx];
bool cmp(node x,node y){return x.r<y.r;}
bool cmd(node x,node y){if(x.l!=y.l)return x.l>y.l;return x.r<y.r;}intlow_bit(int x){return x &(-x);}voidupdate(int xx){while(xx<=n){
        sum[xx]++;
        xx+=low_bit(xx);}}intquery(int x){int ans =0;while(x>0){
        ans+=sum[x];
        x-=low_bit(x);}return ans ;}intmain(){scanf("%d",&n);memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++){scanf("%d%d",&f[i].l,&f[i].r);
        f[i].op=i;}sort(f+1,f+n+1,cmp);for(int i=1;i<=n;i++){
        f[i].r=i;}sort(f+1,f+n+1,cmd);for(int i=1;i<=n;i++){
        ans[f[i].op]=query(f[i].r);update(f[i].r);}for(int i=1;i<=n;i++){printf("%d\n",ans[i]);}}

好久没写树状数组了打得有点艰难，吓得我赶紧又去写了一道模板题，祝大家天天AC ^ ^

本文标签： 挑战编程排序

版权声明：本文标题：CF625D挑战：树状数组快速攻略与实战案例 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.betaflare.com/web/1770933770a3260173.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。