[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);
}

留下评论

您的电子邮箱地址不会被公开。