Hihocoder-小Hi的烦恼

解题思路：

其实题目自带的题解已经交代的比较清楚了。但是如果完全按照题目自带的解法来计算，肯定是会超时的。因为无论如何还是O(n^2)的解法，当然也可能是彩笔我比较菜只能写出这样的。

所以需要一些转换。

这个题目给的内存空间为1024M，显然我们要用空间换时间了。

就以单个科目为例吧。假设a[i]表示第i个学生在语文这个科目上的排名，index[a[i]] = i表示语文排名为a[i]的是第i个学生。这个时候，设置bitset<maxn> yuwen[maxn]，其中yuwen[i]表示在语文成绩排名为i的前面的学生集合。

所以可以O(n)得到整个yuwen集合，然后再利用前面索引出来的index，就可以整体O(n)的求出结果了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e4 + 5;

int a[maxn][5], inx[maxn][5];
bitset<maxn> bs[maxn][5], ans;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            cin >> a[i][j];
            inx[ a[i][j] ][j] = i;
        }
    }
    for ( int i = 2; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            bs[i][j] = bs[i-1][j];
            bs[i][j].set(inx[i-1][j], 1);
        }
    }
    for ( int i = 1; i <= n; ++i ) {
        ans.set();
        for ( int j = 0; j < 5; ++j ) {
            ans &= bs[ a[i][j] ][j];
        }
        cout << ans.count() << endl;
    }
    return 0;
}

顺便附一个，根据题目自带题解写的东西...最后只有80/100这样的结果= =还是超时了

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

const int maxn = 3e4 + 5;
bitset<maxn> num[5], ans;
int rak[maxn][5], inx[maxn][5];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, bef[5] = {1, 1, 1, 1, 1};
    cin >> n;
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            cin >> rak[i][j];
            inx[ rak[i][j] ][j] = i;
        }
    }
    for (int i = 0; i < 5; ++i) num[i].reset();
    for ( int i = 1; i <= n; ++i ) {
        for ( int k = 0; k < 5; ++k ) {
            if ( bef[k] < rak[i][k] ) {
                for ( int j = bef[k]; j < rak[i][k]; ++j )
                    num[k][ inx[j][k] ] = 1;
            } else {
                for ( int j = bef[k]; j >= rak[i][k]; --j )
                    num[k][ inx[j][k] ] = 0;
            }
        }
        ans.set();
        for ( int k = 0; k < 5; ++k ) {
            ans &= num[k];
            bef[k] = rak[i][k];
        }
        cout << ans.count() << endl;
    }
    return 0;
}