loj541

发布时间：2020-12-16 07:19:34 所属栏目：百科来源：网络整理

导读：七曜圣贤 sol：我标算还没写过，似乎分块就可以过（因为数据是随机的），我写个set可以有70~80分 // C++ #includebits/stdc++.h using namespace std; namespace IO{ int c; unsigned int seed; unsigned int randnum() { seed ^=seed 13 ; seed ^=seed 17 ;

七曜圣贤

sol：我标算还没写过，似乎分块就可以过（因为数据是随机的），我写个set可以有70~80分

//C++
#include<bits/stdc++.h>

using namespace std;

namespace IO
{
    int c;
    unsigned int seed;
    unsigned int randnum()
    {
        seed^=seed<<13;
        seed^=seed>>17;
        seed^=seed<<5;
        return seed;
    }

    inline int read(int &x)
    {
        scanf("%d",&x);
        return x;
    }
    inline void init_case(int &m,int &a,int &b,int &d,int p[])
    {
        scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);
        for(int i=1; i<=m; i++)
        {
            if(randnum()%c==0)p[i]=-1;
            else p[i]=randnum()%b;
        }
    }

    inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no)
    {
//        cout << no << ‘ ‘ << cur_ans << endl;
        const static unsigned int mod=998244353;
        ans_sum^=(long long)no*(no+7)%mod*cur_ans%mod;
    }
}
using IO::read;
using IO::init_case;
using IO::update_ans;
/*
ò??aê???μ÷ó?read(T)?áè?êy?Y×éêyT
?ó??à′??×éêy?Y?aê?ê±??μ÷ó?init_case(m,a,b,d,p)?áè?m,p[]
??×éêy?Y?aê?ê±??ó?ò???3?ê??ˉ?a0μ?32???T·?o???D?±?á?ans_sum′?′￠′e°?￡?è?oó??óú????i￡?
ó?32???T·?o???D?±?á?cur_ans′?′￠μúi′?′e°?￡?2￠μ÷ó?update_ans(ans_sum,cur_ans,i)?üD??￡×?oóê?3?ans_sum?′?é?￡
*/

//ê?ày′ú??￡o
const int N=4000005;
int m,d;
int p[N];
bool Bo[N];
bool Used[N];
deque<int>dq;
set<int>mex;
set<int>::iterator it;
unsigned int ans_sum=0,cur_ans=0;

inline void setSolve(int i)
{
    if((p[i]==-1)&&d)
    {
        if(dq.empty()) return;
        int tmp=dq.front(); dq.pop_front(); Bo[tmp]=1;
        mex.erase(tmp);
//        it=mex.lower_bound(tmp); mex.erase(it);
    }
    else if((Bo[p[i]])&&d)
    {
        dq.push_back(p[i]); Bo[p[i]]=0;
        mex.insert(p[i]);
    }
    else if((!Bo[p[i]])&&(!Used[p[i]]))
    {
        Used[p[i]]=1; Bo[p[i]]=1;
        mex.erase(p[i]);
//        it=mex.lower_bound(p[i]); mex.erase(it);
    }
    else if(d)
    {
        if(dq.empty()) return;
        int tmp=dq.front(); dq.pop_front(); Bo[tmp]=1;
        mex.erase(tmp);
//        it=mex.lower_bound(tmp); mex.erase(it);
    }
    cur_ans=*mex.begin();
    update_ans(ans_sum,i);
}
inline void playset()
{
    int i;
    for(i=0;i<=a;i++) Bo[i]=Used[i]=1;
    mex.clear(); for(i=a+1;i<=max(b,a+1);i++) Bo[i]=Used[i]=0,mex.insert(i);
    dq.clear();
    for(i=1;i+9<=m;i+=10)
    {
        setSolve(i); setSolve(i+1); setSolve(i+2); setSolve(i+3); setSolve(i+4);
        setSolve(i+5); setSolve(i+6); setSolve(i+7); setSolve(i+8); setSolve(i+9);
    }
    for(;i<=m;i++) setSolve(i);
    printf("%un",ans_sum);
}
int main()
{
    freopen("mex.in","r",stdin);
    freopen("mex.out","w",stdout);
    int T,i;
    read(T);
    while(T--)
    {
        ans_sum=cur_ans=0;
        init_case(m,p); d^=1;
        playset();
    }
    return 0;
}
/*
input
1
100000 866153523 100000 10 2 0
output
892635735
*/

set

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!