来源: Ball – CodeForces 12D – Virtual Judge
解题思路:首先按照b的顺序进行排序,然后离散化b,再按照i的顺序排序,去查找已经在树状数组里的大于b的(b+1)的里面最大的r,若查找到的r大于当前r则ans++;然后再将当前i的所有元素加入到树状数组里。
代码
#include <iostream> #include <bits/stdc++.h> using namespace std; struct node { int b,i,r; int id; }a[500050]; int c[500050]; int cnt; bool cmp(node aa,node bb) { if(aa.b==bb.b) { if(aa.i==bb.i) return aa.r<bb.r; else return aa.i<bb.i; } return aa.b<bb.b; } bool cmpp(node aa,node bb) { return aa.i>bb.i; } int lowbit(int x) { return x&(-x); } void add(int x,int d) { while(x>0) { if(c[x]<d) c[x]=d; x-=lowbit(x); } } int getmax(int x) { int s=-1; for(int i=x;i<=cnt;i+=lowbit(i)) { if(s<c[i]) s=c[i]; } return s; } int main() { ios::sync_with_stdio(false); int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i].b; } for(int i=0;i<n;i++) { cin>>a[i].i; } for(int i=0;i<n;i++) { cin>>a[i].r; } sort(a,a+n,cmp);//b< cnt=1; a[0].id=1; for(int i=1;i<n;i++) { if(a[i].b==a[i-1].b) a[i].id=cnt; else a[i].id=++cnt; } sort(a,a+n,cmpp);//i>//保证i memset(c,-1,sizeof(c)); int ans=0; for(int i=0;i<n;) { int j; for(j=i;j<n&&a[i].i==a[j].i;j++)//防止i相等 { if(getmax(a[j].id+1)>a[j].r)//+1保证b,>保证r ans++; } for(j=i;j<n&&a[i].i==a[j].i;j++) { add(a[j].id,a[j].r); } i=j; } cout<<ans<<endl; return 0; }