什么叫暴力碾标算？

思路:用vector替换树套树中的Splay。

小技巧：归并排序建树。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=N<<2,INF=0X3f3f3f3f;
int n,m;
int w[N];
namespace SegmentTree
{
    struct node
    {
        vector<int> s;
    }unit[M];
    #define s(x) unit[(x)].s
    #define lson(x) ((x)<<1)
    #define rson(x) ((x)<<1|1)
    #define mid (l+r>>1)
    void Print(int p)
    {
        cout<<"k = "<<p<<endl;
        for (int i = 0; i < s(p).size(); ++i)
            printf("%d ", s(p)[i]);
        putchar('\n');
        return;
    }
    void Build(int k,int l,int r) //归并排序建树.
    {
        if(l==r)
        {
            s(k).push_back(w[l]);
            return;
        }
        Build(lson(k),l,mid);
        Build(rson(k),mid+1,r);
        int i=0,j=0;
        int lenl=s(lson(k)).size(),lenr=s(rson(k)).size();
        while(i<lenl&&j<lenr)
        {
            if(s(lson(k))[i]<=s(rson(k))[j])
                s(k).push_back(s(lson(k))[i++]);
            else s(k).push_back(s(rson(k))[j++]);
        }
        while(i<lenl)
            s(k).push_back(s(lson(k))[i++]);
        while(j<lenr)
            s(k).push_back(s(rson(k))[j++]);
    }
    void Update(int k,int l,int r,int pos,int val)
    {
        s(k).erase(lower_bound(s(k).begin(),s(k).end(),w[pos]));
        s(k).insert(lower_bound(s(k).begin(),s(k).end(),val),val);
        if(l==r) return;
        if(pos<=mid) Update(lson(k),l,mid,pos,val);
        if(pos>mid) Update(rson(k),mid+1,r,pos,val);
    }
    int Query(int k,int l,int r,int L,int R,int val)
    {
        //Print(k);
        if(L<=l&&R>=r)
            return lower_bound(s(k).begin(),s(k).end(),val)-s(k).begin();
        int res=0;
        if(L<=mid) res+=Query(lson(k),l,mid,L,R,val);
        if(R>mid) res+=Query(rson(k),mid+1,r,L,R,val);
        return res;
    }
    int Get_pre(int k,int l,int r,int L,int R,int val)
    {
        //cout<<"l = "<<l<<" r = "<<r<<endl;
        //Print(k);
        if(L<=l&&R>=r)
        {
            auto it=lower_bound(s(k).begin(),s(k).end(),val);
            if(it==s(k).begin()) return -INF;  //一定要注意这里。
            return *--it;
        }
        int res=-INF;
        if(L<=mid) res=max(res,Get_pre(lson(k),l,mid,L,R,val));
        if(R>mid) res=max(res,Get_pre(rson(k),mid+1,r,L,R,val));
        return res;
    }
    int Get_suf(int k,int l,int r,int L,int R,int val)
    {
        //cout<<"l = "<<l<<" r = "<<r<<endl;
        //Print(k);
        if(L<=l&&R>=r)
        {
            auto it=upper_bound(s(k).begin(),s(k).end(),val);
            return (it==s(k).end() ? INF : *it); //一定要注意这里。
        }
        int res=INF;
        if(L<=mid) res=min(res,Get_suf(lson(k),l,mid,L,R,val));
        if(R>mid) res=min(res,Get_suf(rson(k),mid+1,r,L,R,val));
        return res;
    }
}
using namespace SegmentTree;
inline void Read()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    Build(1,1,n);
}
inline void Work()
{
    while(m--)
    {
        int a,b,x,l,r,op;
        scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d%d%d",&a,&b,&x);
                printf("%d\n",Query(1,1,n,a,b,x)+1);
                break;
            case 2:
                scanf("%d%d%d",&a,&b,&x);
                l=0,r=1e8;
                while(l<r)
                {
                    int val=l+r+1>>1;
                    if(Query(1,1,n,a,b,val)+1<=x) l=val;
                    else r=val-1;
                }
                printf("%d\n",r);
                break;
            case 3:
                scanf("%d%d",&a,&x);
                Update(1,1,n,a,x);
                w[a]=x;
                break;
            case 4:
                scanf("%d%d%d",&a,&b,&x);
                printf("%d\n",Get_pre(1,1,n,a,b,x));
                break;
            case 5:
                scanf("%d%d%d",&a,&b,&x);
                printf("%d\n",Get_suf(1,1,n,a,b,x));
                break;
        }
    }
}
int main()
{
    Read();
    Work();
    return 0;
}

ps:调vector的迭代器快调到崩溃了，一定要注意边界问题.