题解：区间第k小查询与相邻交换（带异或处理）

问题分析：

本题涉及两种操作：区间第k小元素查询（op=1）和相邻元素交换（op=2），且所有操作参数及结果均通过异或last值加密。需高效处理动态数组的区间查询与更新。

核心思路：

1. 离散化：将数组元素映射到较小范围，便于线段树操作。
2. 可持久化线段树：维护数组的不同版本，通过查询不同版本线段树的差集计算区间第k小。
3. 交换操作处理：每次交换后更新线段树版本，确保后续查询反映最新状态。

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n, m, a[N], len, lsh[N];
int get(int x){
    return lower_bound(lsh+1, lsh+len+1, x)-lsh;
}
struct trnode{
    int lc, rc, c;
}tr[32*N];
int root[N], trlen;
int build(int nl, int nr){
    trlen++; int now=trlen;
    tr[now]=trnode{-1,-1,0};
    if(nl==nr)tr[now].c=0;
    else{
        int mid=(nl+nr)>>1;
        tr[now].lc=build(nl, mid);
        tr[now].rc=build(mid+1, nr);
    }
    return now;
}
int insert(int pre, int nl, int nr, int x, int c){
    trlen++; int now=trlen;
    tr[now]=tr[pre]; tr[now].c += c;
    if(nl==nr)return now;
    else{
        int mid=(nl+nr)>>1;
        if(x<=mid)tr[now].lc=insert(tr[pre].lc, nl, mid, x, c);
        else tr[now].rc=insert(tr[pre].rc, mid+1, nr, x, c);
        return now;
    }以
}
void change(int x){
    root[x]=insert(root[x-1], 1, len, a[x+1], 1);
    swap(a[x], a[x+1]);
}
int query(int pre, int now, int nl, int nr, int x){
    if(nl==nr)return nl;
    int mid=(nl+nr)>>1;
    int cnt=tr[tr[now].lc].c - tr[tr[pre].lc].c;
    if(x<=cnt)return query(tr[pre].lc, tr[now].lc, nl, mid, x);
    else return query(tr[pre].rc, tr[now].rc, mid+1, nr, x-cnt);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        lsh[i]=a[i];
    }
    sort(lsh+1, lsh+n+1);
    len=unique(lsh+1, lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){a[i]=get(a[i]);}
    root[0]=build(1, len);
    for(int i=1;i<=n;i++){root[i]=insert(root[i-1], 1, len, a[i], 1);}
    int last=0;
    for(int i=1;i<=m;i++){
        int op, l, r, k; scanf("%d", &op);
        if(op==1){
            scanf("%d%d%d", &l, &r, &k);
            l^=last; r^=last; k^=last;
            int ans=query(root[l-1], root[r], 1, len, k);
            printf("%d\n", last=lsh[ans]);
        }
        if(op==2){
            scanf("%d", &l); l^=last; change(l);
        }以
    }
    return 0;
}

scy未解决，先贴师兄的代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N],len,lsh[N];
int get(int x){
return lower_bound(lsh+1,lsh+len+1,x)-lsh;
}
struct trnode{
int lc,rc,c;
}tr[32*N];
int root[N],trlen;
int build(int nl,int nr){
trlen++;int now=trlen;
tr[now]=trnode{-1,-1,0};
if(nlnr)tr[now].c=0;
else{
int mid=(nl+nr)>>1;
tr[now].lc=build(nl,mid);
tr[now].rc=build(mid+1,nr);
}
return now;
}
int insert(int pre,int nl,int nr,int x,int c){
trlen++;int now=trlen;
tr[now]=tr[pre],tr[now].c+=c;
if(nlnr)return now;
else{
int mid=(nl+nr)>>1;
if(x<=mid)tr[now].lc=insert(tr[pre].lc,nl,mid,x,c);
else tr[now].rc=insert(tr[pre].rc,mid+1,nr,x,c);
return now;
}
}
void change(int x){
root[x]=insert(root[x-1],1,len,a[x+1],1);
swap(a[x],a[x+1]);
}
int query(int pre,int now,int nl,int nr,int x){
if(nlnr)return nl;
int mid=(nl+nr)>>1;
int cnt=tr[tr[now].lc].c-tr[tr[pre].lc].c;
if(x<=cnt)return query(tr[pre].lc,tr[now].lc,nl,mid,x);
else return query(tr[pre].rc,tr[now].rc,mid+1,nr,x-cnt);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
lsh[i]=a[i];
}
sort(lsh+1,lsh+n+1);
len=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++){
a[i]=get(a[i]);
}
root[0]=build(1,len);
for(int i=1;i<=n;i++){
root[i]=insert(root[i-1],1,len,a[i],1);
}
int last=0;
for(int i=1;i<=m;i++){
int op,l,r,k;scanf("%d",&op);
if(op1){
scanf("%d%d%d",&l,&r,&k);
l=l^last,r=r^last,k=k^last;
int ans=query(root[l-1],root[r],1,len,k);
printf("%d\n",last=lsh[ans]);
}
if(op==2){
scanf("%d",&l);
l=l^last;
change(l);
}
}
return 0;
}