[SSLOJ1362 指纹]各种猥琐预处理+树状数组

【题目大意】
有N个程序，每个数据有4个测试项。
给出每个程序在这4个测试项里的排名，(排名保证取遍1..N的每个数)，排名越前越牛X。
然后假设对于某一条程序，存在另外一条程序在4项中，有>=3项比它优，那么它就成为了SB程序。
问有多少个SB程序。
【算法分析】
先枚举地移走某一项，然后剩下的三项一起弄。（移走的那项暂时忽略，因为只需>=3个比它优）
这三项又可以按某一项排序，然后问题就变成了将给出N个二元对(Ai,Bi)，然后对于每个二元对，判断有没有出现在它之前的，且满足Ai然后我们可以以Ai为key值作树状数组的下标，然后就可以在lgN的复杂度内维护Ai<=K的点中，Bi最小是多少。然后再标记一下，问题就可以解决了。
【CODE】
#include #include #include const int N=100005;
int n;
int a[N][5],d[N][5],Q[N];
bool bad[N];

inline int cmp(const void *x,const void *y){return ((int *)x)[0]-((int *)y)[0];}

void solve(){
memcpy(d,a,sizeof(int)*5*(n+1));
qsort(d+1,n,sizeof(int)*5,cmp);
memset(Q,50,sizeof(int)*(n+1));
int i,res,j;
for (i=1;i<=n;i++){
res=0x7FFFFFFF;
j=d[i][1]-1;
while (j){
res j-=j&-j;
}
if (res j=d[i][1];
while (j<=n){
Q[j] j+=j&-j;
}
}
}

int main(){
scanf("%d",&n);
int i,j,k,tmp;
for (i=1;i<=n;i++){
a[i][4]=i;
for (j=0;j<4;j++)
scanf("%d",&a[i][j]);
}
for (k=0;k<4;k++){
for (i=1;i<=n;i++){
tmp=a[i][k]; a[i][k]=a[i][3]; a[i][3]=tmp;
}
solve();
for (int i=1;i<=n;i++){
tmp=a[i][k]; a[i][k]=a[i][3]; a[i][3]=tmp;
}
}
int ans=0;
for (int i=1;i<=n;i++)
if (bad[i]) ans++;
printf("%dn",ans);
for (int i=1;i<=n;i++)
if (bad[i]) printf("%dn",i);
}