P1383 高级打字机

这题用红黑树实现的可持久化数据结构可以很轻松的AC，码量非常小，自行百度。

MyCode:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
typedef unsigned long long ull;
struct node {
    int lt,rt;
    char s;
} t[maxn*10];
int tot,len[maxn],rt[maxn];
char ch,op;
void modify(int &x,int l,int r,int pos) {
    t[++tot]=t[x];
    x=tot;
    if(l==r) return t[x].s=ch,void();
    int mid=l+r>>1;
    if(pos<=mid) modify(t[x].lt,l,mid,pos);
    else modify(t[x].rt,mid+1,r,pos);
}
char query(int x,int l,int r,int pos) {
    if(l==r) return t[x].s;
    int mid=l+r>>1;
    if(pos<=mid) return query(t[x].lt,l,mid,pos);
    else return query(t[x].rt,mid+1,r,pos);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,cnt(0);
    cin>>n;
    for(int i=1,x; i<=n; ++i) {
        cin>>op;
        if(op=='T') {
            ++cnt;
            cin>>ch;
            len[cnt]=len[cnt-1]+1;
            modify(rt[cnt]=rt[cnt-1],1,n,len[cnt]);
        } else if(op=='U') {
            cin>>x;
            ++cnt;
            rt[cnt]=rt[cnt-x-1];
            len[cnt]=len[cnt-x-1];
        } else {
            cin>>x;
            cout<<query(rt[cnt],1,n,x)<<'\n';
        }
    }
    return 0;
}

P2839 [国家集训队]middle

找中位数通过二分答案是第几大的数，然后判断一下。比二分值小的赋值为-1，大于等于二分值的赋值为1，因为如果n是偶数，这题中位数取的是中间偏大的那个数，所以判断答案是否可行的条件是最大连续区间和大于等于0 。其它的不多讲。主席树在这里的作用是，第i个版本维护的是升序中大的数赋值为-1、第大的数赋值为1的线段树。
MyCode：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e4+11;
struct node{
    int lt,rt,lm,s,rm;
}t[maxn*30];
int tot,n,ans,a[maxn],id[maxn],rt[maxn],q[4];
void pushup(int x,int l,int r) {
    t[x].s=t[l].s+t[r].s;
    t[x].lm=max(t[l].lm,t[l].s+t[r].lm);
    t[x].rm=max(t[r].rm,t[r].s+t[l].rm);
}
void build(int &x,int l,int r) {
    x=++tot;
    if(l==r) return t[x].lm=t[x].s=t[x].rm=1,void();
    int mid=(l+r)>>1;
    build(t[x].lt,l,mid);
    build(t[x].rt,mid+1,r);
    pushup(x,t[x].lt,t[x].rt);
}
void modify(int &x,int l,int r,int p) {
    t[++tot]=t[x];
    x=tot;
    if(l==r) return t[x].lm=t[x].s=t[x].rm=-1,void();
    int mid=(l+r)>>1;
    if(mid>=p) modify(t[x].lt,l,mid,p);
    else modify(t[x].rt,mid+1,r,p);
    pushup(x,t[x].lt,t[x].rt);
}
struct pd{
    int s,lm,rm;
    pd operator+(const pd &d)const {
        return pd{s+d.s,max(lm,s+d.lm),max(d.rm,d.s+rm)};
    }
};
int qs(int x,int l,int r,int lm,int rm) {
    if(l<=lm&&rm<=r) return t[x].s;
    int mid=(lm+rm)>>1;
    if(l<=mid&&r>mid) return qs(t[x].lt,l,r,lm,mid)+qs(t[x].rt,l,r,mid+1,rm);
    else if(l<=mid) return qs(t[x].lt,l,r,lm,mid);
    else return qs(t[x].rt,l,r,mid+1,rm);
}
pd query(int x,int l,int r,int lm,int rm) {
    if(l<=lm&&rm<=r) return pd{t[x].s,t[x].lm,t[x].rm};
    int mid=(lm+rm)>>1;
    if(l<=mid&&r>mid) return query(t[x].lt,l,r,lm,mid)+query(t[x].rt,l,r,mid+1,rm);
    else if(l<=mid) return query(t[x].lt,l,r,lm,mid);
    else return query(t[x].rt,l,r,mid+1,rm);
} 
inline void solve() {
    int A,B,C,D,sum,mid;
    for(int i=0;i<4;++i) cin>>q[i];
    q[0]=(q[0]+ans)%n+1;
    q[1]=(q[1]+ans)%n+1;
    q[2]=(q[2]+ans)%n+1;
    q[3]=(q[3]+ans)%n+1;
    sort(q,q+4);
    A=q[0],B=q[1],C=q[2],D=q[3];
    int l=1,r=n;
    while(l<=r) {
        mid=l+r>>1,sum=0;
        if(B+1<=C-1) sum=qs(rt[mid],B+1,C-1,1,n);
        sum+=query(rt[mid],A,B,1,n).rm+query(rt[mid],C,D,1,n).lm;
        if(sum>=0) l=mid+1;
        else r=mid-1;
    }
    ans=a[id[l-1]];
    cout<<ans<<'\n';
}
bool cmp(int &x,int &y) {
    return a[x]<a[y];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],id[i]=i;
    sort(id+1,id+1+n,cmp);
    build(rt[1],1,n);
    for(int i=2;i<=n;++i) modify(rt[i]=rt[i-1],1,n,id[i-1]);
    int Q; cin>>Q; while(Q--) solve();
}