读入数据出问题
查看原帖
读入数据出问题
402384
orgn楼主2023/1/7 22:21

如题,l 和 r 读入挂了

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define MAXX 100005
#define ll long long
int n,m,seed,v_max,a[MAXX];
inline ll read();

struct node {
    ll l,r;
    mutable ll v;//表示可修改
    node(ll l,ll r=0,ll v=0) :l(l),r(r),v(v){}
    bool operator<(const node &up) const { return l<up.l; }
};
set<node> s;

set<node>::iterator split(int pos){
    auto it=s.lower_bound(node(pos));
    if(it!=s.end() && it->l==pos) return it; it--;
    if(it->r<pos) return s.end();
    ll l=it->l,r=it->r,v=it->v;
    s.erase(it),s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;//新插入点的迭代器
}
void assign(ll l,ll r,ll val){
    auto itr=split(r+1),itl=split(l);
    s.erase(itl,itr),s.insert(node(l,r,val));
}
void add(ll l,ll r,ll val){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++) it->v+=val;
}
struct Rank{
    ll num,cnt;
    bool operator<(const Rank &up) const { return num<up.num; }
    Rank(ll num,ll cnt):num(num),cnt(cnt){}
};
ll rnk(ll l,ll r,ll k){
    auto itr=split(r+1),itl=split(l);
    vector<Rank> f;
    for(auto it=itl;it!=itr;it++) f.push_back(Rank(it->v,it->r-it->l+1));
    sort(f.begin(),f.end()); int i;
    for(i=0;i<f.size();i++){
        if(k<=f[i].cnt) break;
        k-=f[i].cnt;
    } return f[i].num;
}
ll ksm(ll x,ll y,ll p){
    ll ve=1,base=x%p;
    while(y){
        if(y&1) ve=ve*base%p;
        base=base*base%p,y>>=1;
    } return ve%p;
}
ll cal(ll l,ll r,ll x,ll p){
    auto itr=split(r+1),itl=split(l);ll ans=0;
    for(auto it=itl;it!=itr;it++) ans=(ans+ksm(it->v,x,p)*(it->r-it->l+1)%p)%p;
    return ans;
}
ll rnd() { ll ret = seed; seed = (seed * 7 + 13) % mod; return ret; }
int main (){
    n=read(),m=read(),seed=read(),v_max=read();
    for(int i=1;i<=n;i++) a[i]=rnd()%v_max+1,s.insert(node(i,i,a[i]));
    for(int i=1;i<=m;i++){
        ll op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;
        if(l>r) swap(l,r); 
        //cout<<l<<" "<<r<<endl;
        if(op==3) x=rnd()%(r-l+1)+1; else x=rnd()%v_max+1;
        if(op==4) y=rnd()%v_max+1;
        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) cout<<rnk(l,r,x)<<endl;
        else if(op==4) cout<<cal(l,r,x,y)<<endl;
    }
    return 0;
}
inline ll read(){
    ll k=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9') k=k*10+ch-'0',ch=getchar();
    return k*f;
}
2023/1/7 22:21
加载中...