首页 > 代码库 > 【bzoj 3333】排队计划（线段树）
【bzoj 3333】排队计划（线段树）
n个数，求一次逆序对。接着有m次修改操作，把每次输入的位置p的数之后<=它的数取出来，从小到大排序后再放回空位里，求逆序对。（N,M<=500,000 , Ai<=10^9）
思路：
1.往后修改就存后缀，而不是一般的前缀。存数 i 之后<=它的数的个数为s[i]，用于后续求逆序对。
2.修改时选出的数排序后，它们的 s[] 都清零了，也可以“删掉”它们了——更改其值为INF。
实现：
1.用树状数组（或线段树）求出初始的逆序对数 sum。
2.每次操作用线段树在p到n的区间内找到所有<=数p 的数，通过一次次找最小的数，sum减去它的 s[] 值，更改其值为INF来进行“删除”。
3.线段树中权值存最小的数的编号，这样方便直接找到它。一个个删点也不用担心超时，因为“删”了之后就不会找到它了，为O(n)，找最小的数为O(log n)，整个程序为O(n log n)的时间复杂度。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 typedef long long LL; 8 9 const LL N=500010,INF=(LL)1e9+100; 10 LL n,m; 11 LL b[N],s[N],c[N]; 12 struct node{LL l,r,lc,rc,id;}a[N*2]; 13 LL len=0; 14 struct hp{LL x,t;}e[N]; 15 16 LL mmin(LL x,LL y) 17 { return x<y?x:y; } 18 LL cp(LL x,LL y) 19 { return b[x]<b[y]?x:y; } 20 21 void bt(LL l,LL r) 22 { 23 LL x=++len; 24 a[x].l=l,a[x].r=r; 25 a[x].lc=a[x].rc=-1; 26 if (l==r) a[x].id=l; 27 else a[x].id=0; 28 if (l<r) 29 { 30 LL mid=(l+r)/2; 31 a[x].lc=len+1,bt(l,mid); 32 a[x].rc=len+1,bt(mid+1,r); 33 34 LL lc=a[x].lc,rc=a[x].rc; 35 a[x].id=cp(a[lc].id,a[rc].id); 36 } 37 } 38 void change(LL x,LL p,LL id) 39 { 40 if (a[x].l==a[x].r) {a[x].id=n+1;return;} 41 LL lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)/2; 42 if (p<=mid) change(lc,p,id); 43 else change(rc,p,id); 44 a[x].id=cp(a[lc].id,a[rc].id); 45 } 46 LL getmin(LL x,LL l,LL r) 47 { 48 if (a[x].l==l&&a[x].r==r) return a[x].id; 49 LL lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)/2; 50 if (r<=mid) return getmin(lc,l,r); 51 if (l>mid) return getmin(rc,l,r); 52 return cp(getmin(lc,l,mid),getmin(rc,mid+1,r)); 53 } 54 55 bool cmp(hp u,hp v) 56 { return u.x<v.x; } 57 58 LL lowbit(LL x) {return x&-x;} 59 LL S(LL x) 60 { 61 LL h=0; 62 for (LL i=x;i>=1;i-=lowbit(i)) 63 h+=c[i]; 64 return h; 65 } 66 void C(LL x) 67 { for (LL i=x;i<=n;i+=lowbit(i)) c[i]++; } 68 69 int main() 70 { 71 scanf("%I64d%I64d",&n,&m); 72 for (LL i=1;i<=n;i++) 73 scanf("%I64d",&e[i].x),e[i].t=i; 74 sort(e+1,e+1+n,cmp); 75 LL x=0; 76 e[0].x=INF; 77 for (LL i=1;i<=n;i++) 78 { 79 if (e[i].x!=e[i-1].x) x++; 80 b[e[i].t]=x; 81 } 82 b[n+1]=INF; 83 LL sum=0; 84 memset(c,0,sizeof(c)); 85 for (LL i=n;i>=1;i--) 86 { 87 s[i]=S(b[i]-1); 88 sum+=s[i]; 89 C(b[i]); 90 } 91 printf("%I64d\n",sum); 92 bt(1,n); 93 while (m--) 94 { 95 LL p; 96 scanf("%I64d",&p); 97 LL t=b[p],k=getmin(1,p,n),h=0; 98 while (b[k]<=t) 99 {100 h+=s[k];//101 change(1,k,n+1);102 k=getmin(1,p,n);103 }104 sum-=h;105 printf("%I64d\n",sum);106 }107 return 0;108 }
【bzoj 3333】排队计划（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。