题解：P14617 [2019 KAIST RUN Fall] Hilbert' s Hotel

· · 题解

Solution

首先考虑前两问。由于保证了点一定在定义域内，于是不需要再额外维护定义域。

线段树维护单点插入，单点查询，区间乘，区间加一次函数即可。

对于第三问，将旅馆分块，把相邻有限的团体合并成一个块。考虑从后往前枚举，若当前位于无限团体，但是该房间不是奇数，就说明该房间并不位于该团体中，那么忽略掉这个团体。由于在此之前的团体位置都进行了 \times 2，于是还原只需要让当前位置 x\larr\frac x2 即可。有限团体是好处理的，套个二分即可。
容易发现这只会跳 \mathcal O(\log x) 次，于是就能在 \mathcal O(q\log V) 的时间内通过了。

赛时线段树写丑了。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=3e5+10,mod=1e9+7;
typedef pair<int,int> pii;
typedef long long ll;
/*

*/
int C,T=1;
struct node {
    struct func{int k,b;}; int tp,ts; func f;
    int operator [](const int &u)const{return (f.k*u+f.b)%mod;}
}tr[N<<2];
int idx,pw[N],G[N];
void rem(node&u,int v) {u.f.b=u.f.b*pw[v]%mod,u.ts=u.ts*pw[v]%mod,u.tp=(u.tp+v)%mod,u.f.k=u.f.k*pw[v]%mod;}
void rev(node&u,int v) {u.f.b=(u.f.b+v)%mod,u.ts=(u.ts+v)%mod;}
void pd(int u){
    int &p=tr[u].tp,&s=tr[u].ts;
    if(p) rem(tr[u<<1],p),rem(tr[u<<1|1],p),p=0;
    if(s) rev(tr[u<<1],s),rev(tr[u<<1|1],s),s=0;
}
void upd(int pl,int pr,int v,int u=1,int l=0,int r=N){
    if(pl<=l&&r<=pr) return v?rev(tr[u],v):rem(tr[u],1);
    if(pr<pl) return; int mid=(l+r)>>1; pd(u);
    if(pl<=mid) upd(pl,pr,v,u<<1,l,mid);
    if(mid<pr) upd(pl,pr,v,u<<1|1,mid+1,r);
}
void ins(int p,int v,int k=2,int b=1,int u=1,int l=0,int r=N){
    if(l==r) return v?tr[u]={0,0,{1,0}}:tr[u]={0,0,{k,b}},void();
    int mid=(l+r)>>1; pd(u);
    if(p<=mid) ins(p,v,k,b,u<<1,l,mid);
    else ins(p,v,k,b,u<<1|1,mid+1,r);
}
node qry(int p,int u=1,int l=0,int r=N){
    if(l==r) return tr[u];
    int mid=(l+r)>>1; pd(u);
    if(p<=mid) return qry(p,u<<1,l,mid);
    else return qry(p,u<<1|1,mid+1,r);
}
int lst,pre[N],nxt[N],pp[N],len[N],col[N],W[N],cnt;
void fnd(int u,int v){
    int l=pre[u],r=nxt[u],res=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(W[nxt[u]]-W[mid-1]>v) res=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<res<<"\n";
}
void all_restart(int n){
    pw[0]=1; ins(0,0,1,0);
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
}
void Lain(){
    int opt,u,v; cin>>opt>>u;
    if(opt==1) return upd(0,idx,u),ins(++idx,u),G[idx]=u,void();
    if(opt==2) return cin>>v,cout<<qry(u)[v-1]<<"\n",void();

    while(lst!=idx){ v=G[++lst];
        if(!G[lst]||!G[lst-1]) ++cnt,pre[cnt]=lst,pp[cnt]=cnt;
        len[cnt]+=v; W[lst]+=W[nxt[cnt]],W[lst]+=v,nxt[cnt]=lst;  
        if(!v) pp[cnt]=pp[cnt-1];
    }
    int nw=cnt;
    while(u){ 
        if(!nw) return cout<<"0\n",void();
        if(!len[nw]) {if(u&1) return cout<<pre[nw]<<"\n",void();}
        if(u<len[nw]) return fnd(nw,u);
        if(!len[nw]) u>>=1;
        else u-=len[nw]; --nw;
    }
    cout<<nxt[pp[nw]]<<"\n";
    return;
}
signed main(){ 
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>T,all_restart(T);
    while(T--) Lain();
    return 0;
}