题解：P13981 数列分块入门 6

kilees · 2025-09-07 23:56:41 · 题解

P13981 数列分块入门 6

本题虽是分块练习，但因为我写调分块的时间比写调线段树所用的时间还要长，所以给一种线段树做法。

思路

对于向序列第 i 个位置前添数，可以看做是将所添数在序列中的位置下标从无改为 i，并将 i 后面的数在序列中的位置下标增加 1。把无当做负无穷，那不就相当于单点修，区间修嘛，直接就是一个线段树。

在第 t 个查询，线段树上点 i 的值表示在将所有点都插入完后的序列上第 i 个点在如今序列上的下标（没有就是负无穷）。那么修改操作直接按照上面来，查询操作则在线段树上二分出值为 c 的点的位置，看那个点为代表的数为多少就行了。

现在还有一个问题，如何求将所有点都插入完后的序列?

还是线段树。

在第 i 个添加询问 l,r 完成后的序列中，序列第 l 个位置一定为 r。设 m 为最终区间长度，最后一个添加询问 l,r 完毕后，最终序列中 l 位置的值一定是 r。那么之后删去这个数，剩下的序列就为进行完倒数第二个添加后的序列，可以重复此操作。

那么在第 t 个查询 l,r，线段树上点 i 值的意义与上面相同。那么修改操作变为将值为 l 的点的值变为负无穷，再将后面点都减一，第 i 个查询在最终序列上的下标就是那个点在线段树上所代表的下标。

对于原序列，可看做从一开始不停向序列中第 1 个位置前添加的操作。

至此本题结束。

code

// Problem: P13981 数列分块入门 6
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P13981
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#include<queue>
#define endl "\n"
#define ll long long
// #define int long long
#define db long double
#define ft first
#define sd second
#define lp p<<1
#define rp p<<1|1
#define pb push_back
#define mp make_pair
#define pe(j) (1ll<<(j))
#define foe(n) for(int i=1;i<=n;i++)
using namespace std;
inline void write(ll x);
inline ll read();
const ll N=6e5+5,INF=0x3f3f3f3f3f3f3f3f,mod=998244353;
ll n,k,m,ans,T;
ll a[N/2];
struct Q{
    ll op,l,r,c;
}q[N];
ll bo[N],pos[N],pre[N],cnt;

struct dat{
    ll l,r,lc,rc,bo;
}t[N*4];
void pu(ll p){
    if(t[lp].lc>0) t[p].lc=t[lp].lc;
    else t[p].lc=t[rp].lc;
    if(t[rp].rc>0) t[p].rc=t[rp].rc;
    else t[p].rc=t[lp].rc;
}
void add(ll p,ll x){
    t[p].lc+=x;t[p].rc+=x;
    if(t[p].lc==0)t[p].lc++;
    t[p].bo+=x;
}
void pd(ll p){
    if(t[p].bo){
        add(lp,t[p].bo),
        add(rp,t[p].bo),
        t[p].bo=0;
    }
}
void csh(ll p,ll l,ll r){
    t[p]={l,r,0,0,0};
    if(l==r){
        t[p].lc=t[p].rc=pre[l];
        return;
    }
    ll mid=(l+r)>>1;
    csh(lp,l,mid),csh(rp,mid+1,r);
    pu(p);
}
void xg(ll p,ll x,ll sum){
    if(t[p].l==t[p].r){
        t[p].lc=t[p].rc=sum;
        return;
    }
    pd(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(x<=mid)xg(lp,x,sum);
    else xg(rp,x,sum);
    pu(p);
}
void qj(ll p,ll l,ll r,ll x){
    if(t[p].l>=l&&t[p].r<=r){
        add(p,x);
        return;
    }
    pd(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)qj(lp,l,r,x);
    if(r>mid) qj(rp,l,r,x);
    pu(p);
}
ll ef(ll p,ll x){
    if(t[p].l==t[p].r) return t[p].l;
    pd(p);
    if(x<=t[lp].rc) return ef(lp,x);
    else return ef(rp,x);
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n+1;i<=2*n;i++){
        cin>>q[i].op;
        if(q[i].op)cin>>q[i].r;
        else cin>>q[i].l>>q[i].r,cnt++;
    }
    cnt+=n;
    for(int i=1;i<=cnt;i++)pre[i]=i;
    csh(1,1,cnt);

    for(int i=n*2;i>=n+1;i--){
        if(!q[i].op){
            pos[i]=ef(1,q[i].l);
            bo[pos[i]]=q[i].r;
            xg(1,pos[i],-INF);
            qj(1,pos[i]+1,cnt,-1);
        }
    }
    for(int i=1;i<=n;i++){
        pos[i]=ef(1,1);
        bo[pos[i]]=a[i];
        xg(1,pos[i],-INF);
        qj(1,pos[i]+1,cnt,-1);
    }

    for(int i=1;i<=cnt;i++)pre[i]=-INF;
    csh(1,1,cnt);
    for(int i=1;i<=n;i++)xg(1,pos[i],i);
    for(int i=n+1;i<=2*n;i++){
        if(q[i].op)
            cout<<bo[ef(1,q[i].r)]<<endl;
        else{
            xg(1,pos[i],q[i].l);
            qj(1,pos[i]+1,cnt,1);
        }
    }
    return 0;
}

//------------------------------------------------------------------------------------------
//read&write
inline ll read(){
    ll x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}
    return x*w;
}
inline void write(ll x){
  static ll sta[35];
  ll top=0;
  do{sta[top++] = x % 10, x /= 10;}while (x);
  while(top) putchar(sta[--top]+48);
}