给一篇 FHQ 的做法，模板指路： https://blog.csdn.net/tenkuo/article/details/150611855

1.题意理解

有m个队伍，n次提交。每次提交包含队伍编号和罚时。 队伍排名规则：通过题数多的排名靠前，通过题数相同则罚时少的排名靠前。 每次提交后，需要输出该队伍当前的排名。

2.数据结构选择

使用Treap（树堆）维护所有队伍的状态。 每个节点存储一个队伍的(tm, fs)二元组，表示该队伍的通过题数和总罚时。 需要支持的操作：

• 插入：当队伍状态发生变化时，插入新状态
• 删除：当队伍状态发生变化时，删除旧状态
• 查询排名：计算某个状态在所有状态中的排名

3.比较函数设计

由于排名规则是：tm大的排前面，tm相同则fs小的排前面。 为了在Treap中方便地实现分裂和合并，我们定义比较函数jd：

• 当tm不同时，tm小的排在"前面"（这样在Treap中从左到右是tm递增）
• 当tm相同时，fs大的排在"前面"

这样在Treap中从左到右遍历，得到的队伍排名是：tm小的在前，tm相同则fs大的在前。

即排名在后面的队伍才是真正排名靠前的队伍。

4.排名计算

在getrnk函数中，通过split将树分成x和y两部分，其中x中所有节点都"排在"v前面， y中所有节点都"排在"v后面。根据比较函数的设计，y中的节点才是真正排名比v靠前的队伍。 因此返回tr[y].siz，即排在v前面的队伍数量。

5.时间复杂度

每次操作O(log n)，n为操作次数。 总时间复杂度O(n log n)，空间复杂度O(n)。

6. 技巧点

使用rand()作为随机优先级，保证Treap平衡 删除时通过构造一个 fs+1 的边界值，配合两次split实现精确删除

使用unsigned int处理随机数及其所有相关内容，题目需要自然溢出

注意last变量的更新

#include<bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls   // 左孩子宏定义
#define rc(p) tr[p].rs   // 右孩子宏定义

typedef unsigned int ui ;  // 无符号整型，用于处理随机数
typedef long long LL;

const int N = 1e5 + 10;    // 最大操作次数
 
/* 
   结构体tp：表示每个队伍的状态
   tm：该队伍获得的题目通过数（即时间戳次数）
   fs：该队伍的总罚时
   通过 tm 和 fs 共同决定队伍在排名中的位置
*/
struct tp {
	ui tm, fs;
	tp () {
		tm = fs = 0;
	}
};

/*
   判断函数：用于比较两个队伍在排行榜中的先后顺序
   返回true表示na排在nb前面
   按照题目要求：先比较通过题数（tm），通过数多的排名靠前
   如果通过数相同，则罚时（fs）少的排名靠前
   注意：这里写成 na.tm < nb.tm 表示 tm 小的排在前面，但实际要反着理解
   在Treap中，我们通过调整比较逻辑，让更大的tm排在前面
*/
bool jd(tp na, tp nb) {
	if (na.tm != nb.tm) {
		return na.tm < nb.tm;    // tm小的排在前面（在Treap中实际是作为排序键值）
	}
	else {
		return na.fs >= nb.fs;   // fs大的排在前面（同样是为了调整排序顺序）
	}
}
 
/*
   Treap节点结构
   ls, rs: 左右孩子
   val: 该节点对应的队伍状态
   siz: 子树大小，用于计算排名
   rnd: 随机优先级，保证Treap的平衡性
*/
struct node {
	int ls, rs;
	tp val;
	int siz;
	int rnd;
} tr[N << 4];   // 开4倍空间，因为每次插入和删除会产生新节点
 
int rt, trlen;  // rt: Treap根节点，trlen: 节点分配器

// 创建新节点
int newd(tp v) {
	trlen++;
	tr[trlen] = {0, 0, v, 1, rand()};
	return trlen;
}

// 更新节点子树大小
void pushup(int p) {
	tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz + 1;
}
 
/*
   Treap分裂操作：将以p为根的树分成x和y两棵子树
   使得x中所有节点的val都排在v前面（根据jd函数），y中所有节点排在v后面
   这里的分裂逻辑与普通Treap不同，因为比较函数jd不是简单的<关系
*/
void split(int p, tp v, int &x, int &y) {
	if (p == 0) {
		x = y = 0;
		return ;
	}
	if (jd(tr[p].val, v)) {   // 当前节点排在v前面，分到左子树
		x = p;
		split(rc(p), v, rc(x), y);
	}
	else {                    // 当前节点排在v后面或相等，分到右子树
		y = p;
		split(lc(p), v, x, lc(y));
	}
	pushup(p);
}
 
/*
   Treap合并操作：将以x和y为根的两棵树合并
   保证x中所有节点都排在y中所有节点前面
   通过随机优先级维持堆性质
*/
int merge(int x, int y) {
	if ( (!x) || (!y) ) {
		return x + y;
	}
	if (tr[x].rnd < tr[y].rnd) {
		rc(x) = merge(rc(x), y);
		pushup(x);
		return x;
	}
	else {
		lc(y) = merge(x, lc(y));
		pushup(y);
		return y;
	}
}
 
// 插入一个队伍状态
void ins(tp v) {
	int x, y;
	split(rt, v, x, y);
	rt = merge( merge( x, newd(v) ), y );
}
 
/*
   删除一个队伍状态
   注意：这里利用了一个技巧，通过构造一个比v略微"大"的键值来删除
   因为可能存在多个相同状态，我们需要删除其中一个
*/
void del(tp v) {
	int x, y, z;
	tp t;
	t.tm = v.tm;
	t.fs = v.fs + 1;      // 构造一个罚时+1的状态，用于分裂出所有<=v的状态
	split(rt, t, x, y);    // x中所有节点都在v前面（或等于v），y中所有节点在v后面
	split(y, v, y, z);     // 将y分裂，y中得到所有等于v的节点（因为v排在<=t且>=v的位置）
	rt = merge( merge( x, merge( lc(y), rc(y) ) ), z );  // 删除y节点本身，合并其左右子树
}
 
/*
   获取某个队伍的排名
   返回排在该队伍后面的队伍数量 +1
   注意：这里的排名计算方式，返回值是 tr[y].siz
   表示在Treap中排在v后面的节点数量
*/
int getrnk(tp v) {
	int x, y;
	split(rt, v, x, y);
	int res = tr[y].siz;   // y中所有节点排在 v 后面
	rt = merge(x, y);
	return res;
}

ui randNum( ui& seed , ui last , const ui m){ 
    seed = seed * 17 + last ; return seed % m + 1; 
}

ui Tm[N], Fs[N];   // Tm[i]表示队伍i的通过题数，Fs[i]表示队伍i的总罚时

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int T;
	cin >> T;
	ui last = 7; 
	while (T --) {
		int n; 
		ui m, seed;
		cin >> m >> n >> seed;  
		
		rt = trlen = 0;
		// 清空数组，重新初始化
		memset(Tm, 0, sizeof(Tm));
		memset(Fs, 0, sizeof(Fs));
        
        // 清空Treap节点信息
        for (int i = 0; i <= (N << 4) - 40; i ++) {
            tr[i].ls = tr[i].rs = tr[i].siz = 0;
            tr[i].val.tm = tr[i].val.fs = 0;
            tr[i].rnd = rand();
        }
		
		for (int i = 1; i <= n; i ++) {
			ui ria = randNum(seed, last, m);   // 队伍编号
			ui rib = randNum(seed, last, m);   // 本次罚时
			Tm[ria] ++;               // 该队伍通过题数+1
			Fs[ria] += rib;           // 该队伍总罚时增加
			 
			tp t;                     // 当前队伍的新状态
			t.tm = Tm[ria];
			t.fs = Fs[ria];
			tp tt;                    // 当前队伍的旧状态
			tt.tm = Tm[ria] - 1;
			tt.fs = Fs[ria] - rib;
			
			if (Tm[ria] != 1) {       // 如果不是第一次通过，需要删除旧状态
				del(tt);
			}
			ins(t);                   // 插入新状态
			last = getrnk(t);         // 获取该队伍的排名
			cout << last << "\n";
		}
	}
	
	return 0;
}

动态开点线段树

#include<bits/stdc++.h>
#define lc(p) ls[p]
#define rc(p) rs[p]
using namespace std;
typedef long long ll;
unsigned int rd(unsigned int &seed,unsigned int last,unsigned int m){
    seed = seed * 17 + last ; return seed % m + 1; 
}
multiset<pair<unsigned int,unsigned int>> s;
unsigned int c[100010],w[100010],n;
int tr[10000010],rt[1000010],id,ls[10000010],rs[10000010];
void change(int &p,int l,int r,int x,int v){
	if(!p){
		tr[p=++id]=0;
	}
	tr[p]+=v;
	if(l==r)return ; 
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x,v);
	else change(rc(p),mid+1,r,x,v);
}
int find(int p,int l,int r,int x,int y){
	if(!p)return 0;
	if(l>=x&&r<=y)return tr[p];
	int mid=(l+r)>>1;
	if(y<=mid)return find(lc(p),l,mid,x,y);
	if(x>mid)return find(rc(p),mid+1,r,x,y);
	return find(lc(p),l,mid,x,y)+find(rc(p),mid+1,r,x,y);
}
int bit[1000010];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int v){
	x++;
	if(x==0)return ;
	for(int i=x;i<=n+1;i+=lowbit(i)){
		bit[i]+=v;
	}
}
int find(int x){
	x++;
	if(x==0)return 0;
	int ans=0;
	for(int i=x;i;i-=lowbit(i)){
		ans+=bit[i];
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	unsigned int m,seed,last=7;
	cin>>t;
	while(t--){
		cin>>m>>n>>seed;
		for(int i=1;i<=id;i++)tr[i]=ls[i]=rs[i]=0;
		id=0;
		for(int i=0;i<=n+1;i++){
			bit[i]=rt[i]=0;
		}
		for(int i=1;i<=m;i++){
			c[i]=w[i]=0;
		}
		change(rt[0],1,1.5e6,0,m);
		add(0,m);
		for(int _=1;_<=n;_++){
			unsigned int a=rd(seed,last,m);
			unsigned int b=rd(seed,last,m);
			change(rt[c[a]],1,1.5e6,w[a],-1);
			add(c[a],-1);
			c[a]++;w[a]+=b;
			change(rt[c[a]],1,1.5e6,w[a],1);
			add(c[a],1);
			int ans=m-(find(c[a]-1)+find(rt[c[a]],1,1.5e6,w[a],1.5e6));
			cout<<ans<<'\n';
			last=ans;
		}
	}
	return 0;
}

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

因为 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;
}

#include<bits/stdc++.h>
#define int unsigned int
using namespace std;
constexpr int N=1e6+10;

// n: 当前测试用例的AC次数
// last: 上一次输出的结果，用于生成随机数（初始值为7）
// seed: 随机数种子
int n, last=7, seed;

// m: 参赛总人数
// a[i]: 第i个人通过的题目数量
// b[i]: 第i个人的总罚时
int m, a[N], b[N];

// v[s]: 存储通过题目数量为s的所有人的罚时列表（保持有序）
// 用于快速查询在相同题数下，有多少人的罚时更少
vector<int> v[N];
/**
 * 生成随机数的函数
 * 根据题目给定的公式：seed = seed * 17 + last; return seed % m + 1;
 * 返回 [1, m] 范围内的随机数
 */
inline int randNum(){
    seed = seed * 17 + last;
    return seed % m + 1;
}

/**
 * lowbit函数：获取x的二进制表示中最低位的1所对应的值
 * 例如：6 = (0110)2，lowbit(6) = 2
 *       8 = (1000)2，lowbit(8) = 8
 * 
 * 原理：-x 是 x 的补码，x & -x 可以提取出最低位的1
 */
inline int lowbit(int x){
    return x & -x;
}

/**
 * 树状数组（Fenwick Tree / Binary Indexed Tree）结构
 * 用于维护"通过题目数量"维度上的前缀和
 * 
 * s[i]: 树状数组的内部存储
 * 
 * 核心思想：
 * - 树状数组通常用于求前缀和，但这里做了反向处理
 * - updata: 从位置x向前更新（i -= lowbit(i)）
 * - ask: 从位置x向后查询（i += lowbit(i)）
 * - 这样 ask(x) 实际上查询的是 [x, N) 范围内的人数总和
 *   即：通过题目数量 >= x 的人数
 */
struct node{
    int s[N];
    
    /**
     * 更新操作：在位置x处增加v
     * 注意：这里是向前更新（i -= lowbit(i)），与常规树状数组相反
     * 目的是让 ask(x) 能够查询到 >= x 的所有位置的和
     */
    inline void updata(int x, int v){
        for(int i = x; i >= 1; i -= lowbit(i))
            s[i] += v;
    }
    
    /**
     * 查询操作：查询位置x及之后所有位置的和
     * 即查询通过题目数量 >= x 的总人数
     * 注意：这里是向后查询（i += lowbit(i)），与常规树状数组相反
     */
    inline int ask(int x){
        int ans = 0;
        for(int i = x; i < N; i += lowbit(i))
            ans += s[i];
        return ans;
    }
} tr;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int T;
    cin >> T;
    
    while(T--){
        cin >> m >> n >> seed;
        memset(tr.s, 0, sizeof tr.s);
        memset(v, 0, sizeof v);
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        
        // 处理n次AC提交
        for(int i = 1; i <= n; i++){
            // 生成随机数据：x表示AC的人编号，y表示本次AC的罚时
            int x = randNum(), y = randNum();
            
            // 如果这个人之前已经AC过题目，需要先从数据结构中移除旧的状态
            if(a[x]){
                // 从对应题数的罚时列表中删除旧的罚时记录
                // lower_bound找到第一个 >= b[x] 的位置，然后删除该位置的元素
                v[a[x]].erase(lower_bound(v[a[x]].begin(), v[a[x]].end(), b[x]));
                
                // 在树状数组中将原题数的人数减1
                tr.updata(a[x], -1);
            }
            
            // 更新这个人的状态：解题数+1，罚时+y
            b[x] += y;
            a[x]++;
            
            // 计算排名在该人前面的人数
            // 排名规则：先按解题数降序，再按罚时升序
            
            // 步骤1：在当前解题数a[x]的罚时列表中，找到b[x]应该插入的位置
            // lower_bound返回第一个 >= b[x] 的迭代器
            auto it = lower_bound(v[a[x]].begin(), v[a[x]].end(), b[x]);
            
            // 步骤2：计算排名更靠前的人数 = 两部分之和
            // 第一部分：it - v[a[x]].begin() 
            //   表示在相同解题数a[x]的情况下，罚时严格小于b[x]的人数
            // 第二部分：tr.ask(a[x] + 1)
            //   表示解题数 >= a[x]+1 的人数（即解题数严格大于a[x]的人数）
            //   这些人无论罚时多少，排名都在当前人前面
            last = it - v[a[x]].begin() + tr.ask(a[x] + 1);
            
            // 输出结果
            cout << last << "\n";
            
            // 步骤3：将新的状态加入数据结构
            // 在树状数组中将新题数的人数加1
            tr.updata(a[x], 1);
            
            // 在对应题数的罚时列表中插入新的罚时记录
            // 在之前找到的位置it处插入，保持向量有序
            v[a[x]].insert(it, b[x]);
        }
    }
    
    return 0;
}