Luogu

BZOJ

LOJ

分析

平衡树板子题。

如果用 pb_ds 的话,要注意一个问题:会有两者都相同的情况。此时可以再加一维下标,查询的时候就把那一维设为 $0$ 查询。

另外那个 $1500000$ 似乎是假的,罚时要开 long long

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
using namespace __gnu_pbds;
typedef unsigned int uint;
typedef long long ll;

template<typename T>
inline void read(T& X) {
    X=0; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
}

const int N=1000000+10;

struct node { int ac; ll tim; int id; } a[N];
bool operator <(node a,node b) {
    if (a.ac!=b.ac) return a.ac>b.ac;
    else if (a.tim!=b.tim) return a.tim<b.tim;
    else return a.id<b.id;
}

tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;

int m,n;
uint seed,last=7;

inline uint randNum() {
    seed=(uint)seed*17+last;
    return seed%m+1;
}

int main() {
    int Cases; read(Cases);
    while (Cases--) {
        read(m),read(n),read(seed);
        T.clear();
        for (re int i=1;i<=m;++i) a[i].ac=0,a[i].tim=0,a[i].id=i;
        for (re int i=1;i<=m;++i) T.insert(a[i]);
        while (n--) {
            int ria=randNum(),rib=randNum();
            T.erase(a[ria]);
            ++a[ria].ac,a[ria].tim+=rib;
            T.insert(a[ria]);
            last=T.order_of_key((node){a[ria].ac,a[ria].tim,0});
            printf("%d\n",last);
        }
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 43 PM