本文共 1292 字,大约阅读时间需要 4 分钟。
从8月初就看到了这题,今天猛然想起来,然后把补上了
感觉是道好题啊,strong对应的是 s[i]<=s[j] && e[i]>=e[j],那么按照s从小到大排序,e从大到小排序就找到了二位偏序。
然后随便搞一搞就行了,如果s和e相同的话那就看上一个cow有多少cow比它强就行。算是树状数组比较经典的一种题吧
#include #include #include #include #include #include #include #include #include #define INF 2e9#define maxnode 100000#define ll long long#define lowbit(x) (x&(-x))int dx[4]={ 0,0,1,-1};int dy[4]={ 1,-1,0,0};using namespace std;int c[100010];void update(int index,int dx){ for(;index<=100005;index+=lowbit(index)){ c[index]+=dx; }}int getSum(int n){ int ans=0; for(;n>0;n-=lowbit(n)) ans+=c[n]; return ans;}struct node{ int x,y,id; node(int x1=0,int y1=0,int i1=0): x(x1),y(y1),id(i1) {} bool operator < (const node &n1)const{ if( x==n1.x ) return y>n1.y; return x >n; if(n==0) break; for(int i=1;i<=n;i++){ int s,e; cin>>s>>e; cow[i]=node(s,e,i); } sort(cow+1,cow+1+n); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++){ if( (cow[i].x==cow[i-1].x) && (cow[i].y==cow[i-1].y) ) { ans[ cow[i].id ] = ans[ cow[i-1].id ]; update(cow[i].y,1); } else{ ans[ cow[i].id ] = getSum(100005)-getSum( cow[i].y-1 ); update(cow[i].y,1); } } for(int i=1;i<=n;i++) cout< <<" "; cout<
转载于:https://www.cnblogs.com/ZhenghangHu/p/9757772.html