Hdu 6873 Game —— FHQ Treap兩種split同時使用

This way

題意：

有n個位置，每個位置上都有一些方塊。每次有兩種操作：

1 x 詢問位置x有多少個方塊

2 x y 将位置x y的方塊向左移一格，并問你有多少個方塊被推動

所有方塊受力學的影響

題解：

為了這道題特意去學了FHQ Treap

很明顯首先這道題是按照位置建樹的，然後我們又需要支援以下操作：找到第x個位置左邊的位置l使得min(a[l]~a[r])>=y

那麼我們就要先将樹分成x左右邊兩個部分，然後再找到左邊的樹的最後小于y的位置并且将樹分成兩部分。這裡就需要兩個split

然後的話對于移動，也就是a[l-1]加上a[l]-y+1,然後a[l]等于y-1，然後将l和l+1~r交換一下位置。那麼就重新merge一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int ch[N][2];// 0左孩子 1右孩子
ll val[N];// 每一個點的權值
int pri[N];// 随機生成的附件權值
int siz[N];// 以i為節點的樹的節點數量
int tot;// 總結點的數量
int f[N];//翻轉标記
ll sum[N];//權值和
ll mi[N];//最小值
mt19937 rnd(time(NULL));
void update(int x){
    siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
    mi[x]=val[x];
    if(ch[x][0])mi[x]=min(mi[x],mi[ch[x][0]]);
    if(ch[x][1])mi[x]=min(mi[x],mi[ch[x][1]]);
    sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
unordered_map<int,int>fa;
int finds(int x){return fa.count(x)?fa[x]=finds(fa[x]):x;}
int newnode(ll v){
    siz[++tot]=1;// 新開辟一個節點
    val[tot]=mi[tot]=sum[tot]=v;
    pri[tot]=finds(rnd());
    fa[pri[tot]]=finds(pri[tot]+1);
    return tot;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(pri[x]<pri[y]){
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x;
    }
    else {
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y;
    }
}
void split_siz(int rt,int k,int &x,int &y){
    if(!rt)x=y=0;
    else {
        if(siz[ch[rt][0]]+1<=k)
            x=rt,split_siz(ch[rt][1],k-siz[ch[rt][0]]-1,ch[rt][1],y);
        else
            y=rt,split_siz(ch[rt][0],k,x,ch[rt][0]);
        update(rt);
    }
}
void split_mi(int rt,int k,int &x,int &y){
    if(!rt)x=y=0;
    else {
        if(mi[ch[rt][1]]<k||val[rt]<k)
            x=rt,split_mi(ch[rt][1],k,ch[rt][1],y);
        else
            y=rt,split_mi(ch[rt][0],k,x,ch[rt][0]);
        update(rt);
    }
}
int kth(int rt,int k){
    while(1){
        if(k<=siz[ch[rt][0]])
            rt=ch[rt][0];
        else if(k==siz[ch[rt][0]]+1)
            return rt;
        else
            k-=siz[ch[rt][0]]+1,rt=ch[rt][1];
    }
}
ll get_v(int rt,int x){
    return val[kth(rt,x)];
}
ll get_sum(int &rt,int x,int y){
    if(get_v(rt,x)<y)return 0;
    int t1,t2,t3,t4,t5;
    split_siz(rt,x,t1,t2);
    if(mi[t1]>=y){
        rt=merge(t1,t2);
        return 0;
    }
    split_mi(t1,y,t1,t3);
    ll ans=sum[t3]-1ll*(y-1)*siz[t3];
    //printf("sum: %lld,ans: %lld\n",sum[t3],ans);
    split_siz(t1,siz[t1]-1,t1,t4);
    split_siz(t3,1,t3,t5);
    val[t4]+=val[t3]-y+1;
    mi[t4]=sum[t4]=val[t4];
    mi[t3]=sum[t3]=val[t3]=y-1;
    rt=merge(merge(merge(merge(t1,t4),t5),t3),t2);
    return ans;
}
int num,n,m;
void dfs(int rt){
    //if(f[rt])push_down(rt);
    if(ch[rt][0])dfs(ch[rt][0]);
    num++;
    printf("%lld%c",val[rt]," \n"[num==n]);
    if(ch[rt][1])dfs(ch[rt][1]);
}
ll a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        tot=0;
        fa.clear();
        memset(ch,0,sizeof(ch));
        //mi[0]=2e9;
        int rt=0;
        num=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)mi[i]=2e9;
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]),rt=merge(rt,newnode(a[i]));
        //dfs(rt);
        //printf("\n");
        while(m--){
            int op,x,y;
            scanf("%d%d",&op,&x);
            if(op-1){
                printf("%lld\n",get_v(rt,x));
            }
            else {
                scanf("%d",&y);
                printf("%lld\n",get_sum(rt,x,y));
            }
        }
        dfs(rt);
        //printf("\n");
    }
    return 0;
}