[TJOI2019] 甲苯先生的滚榜 神奇做法

· · 题解

注意到数据随机，所以考虑乱搞。

因为 vector 的常数非常的小，所以一个很显然的思路就是直接在 vector 里面去 erase、insert 和 lower_bound。

发现过不了，考虑优化。

因为在 vector 中进行前两个操作的时间与 vector 的长度有很大关系，所以容易想到减小 vector 的长度。

考虑开 n 个 vector，第 i 个记录 AC 数量为 i 是的罚时数量。

对于查询，先在 vector 中二分，然后再查询的 AC 数比自己大的就行了。

对于这个后缀和操作，容易想到用树状数组维护，在发布题解时是最优解。

考虑对于一次操作，最劣的情况肯定是将所有的数全部添加到 vector 中之后在把这些元素全部删除。

这样的操作显然只能填满 10 次 vector，而因为 vector 有 \dfrac{1}{8} 的常数，所以实际上把 10^5 个数实际操作次数的大概只有 \dfrac{10^{10}}{16} 也就是 6\times 10^8 左右。

所以最终的时间复杂度我为 O(T\times m^2)，但是有一个 \dfrac{10}{16} 的常数。

所以最终的计算次数大概只有 3\times 10^{10} 左右，考虑到时限有 10 秒所以可以通过。

然而数据是随机的，所以实际上的复杂度还会除以 2。

在最后由衷的感谢 DengDuck，ta 的帮助让我的题解蓬荜生辉，请关注 DengDuck 谢谢。

参考资料： https://www.luogu.com.cn/article/9yp9o90m

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
unsigned int n,last=7,seed;
int m,a[N],b[N];
unsigned int get(){ seed=seed*17+last;return seed%n+1; }
vector<int> v[N];
struct BIT{
    int s[N];
    int lowbit(int x){return x&-x;}
    void updata(int x,int v){for(int i=x;i>=1;i-=lowbit(i)) s[i]+=v;}
    int ask(int x){int ans=0;for(int i=x;i<N;i+=lowbit(i)) ans+=s[i];return ans;}
    void clear(){memset(s,0,n*4+5);}
}tr;
void solve(){
    cin>>n>>m>>seed,tr.clear();
    for(int i=0;i<=m;i++) v[i].clear();
    memset(a,0,n*4+5),memset(b,0,n*4+5);
    for(int i=1;i<=m;i++){
        int x=get(),y=get();
        if(a[x]) v[a[x]].erase(lower_bound(v[a[x]].begin(),v[a[x]].end(),b[x])),tr.updata(a[x],-1);
        b[x]+=y,a[x]++;
        auto it=lower_bound(v[a[x]].begin(),v[a[x]].end(),b[x]);
        cout<<(last=it-v[a[x]].begin()+tr.ask(a[x]+1))<<'\n';
        tr.updata(a[x],1),v[a[x]].insert(it,b[x]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}