一看之下……完全不会的节奏啊……【尼玛、、、、
然后开始找规律…… 嗯。其实就是找到某条线段上有几条线段能够完全覆盖它,有点意思……
给它们拍个序,怎么排呢……尝试了一下,可以先按照y 来排,从大到小,然后按照x来排,从大到小,此时……我脑洞大开……这TM和那条stars不是一样一样的吗……只要把x按照从小到大来排……
哈哈哈哈哈……机智的我……
机智的我当然没有忘了给它离散化……
这样就可以AC了……【小错误无数啊其实……
AC Memory : 2640 KB Time : 2266 ms
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n; int c[100005]; int b[100005]; struct node { int x,y; int id; } a[100005]; bool cmp(node a,node b) { if(a.y != b.y) return a.y >b.y; else return a.x <b.x; } int lowbit(int x) { return x&(-x); } void update(int i,int val) { while(i<=n) { c[i] +=val; i+=lowbit(i); } } int sum(int i) { int s = 0; while(i>0) { s+=c[i]; i-=lowbit(i); } return s; } int main() { while(scanf("%d",&n),n) { memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int j = 0;j<n;j++) { scanf("%d%d",&a[j].x,&a[j].y); a[j].id = j; a[j].x++; a[j].y++; } sort(a,a+n,cmp); b[a[0].id] = sum(a[0].x); update(a[0].x,1); for(int j = 1;j<n;j++) { if(a[j].x==a[j-1].x&&a[j].y==a[j-1].y) b[a[j].id] = b[a[j-1].id]; else b[a[j].id] = sum(a[j].x); update(a[j].x,1); } printf("%d",b[0]); for(int j = 1;j<n;j++) { printf(" %d",b[j]); } printf("\n"); } return 0; }