硬是把普及组打成STL魔法大赛

//sort.cpp
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
__gnu_pbds::tree<long long,__gnu_pbds::null_type,less<long long>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> tr;
long long n,q,a[8005];
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%lld%lld",&n,&q);
    for(long long i=1;i<=n;i++) scanf("%lld",&a[i]),tr.insert((a[i]<<15)+i);
    for(long long i=0;i<q;i++){
        long long typ;scanf("%lld",&typ);
        if(typ==1){
            long long x,y;scanf("%lld%lld",&x,&y);
            tr.erase((a[x]<<15)+x);
            tr.insert((y<<15)+x);
            a[x]=y;
        }
        else {
            long long x;scanf("%lld",&x);
            printf("%lld\n",(long long)(tr.order_of_key((a[x]<<15)+x)+1));
        }
    }
    return 0;
}

//fruit.cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
    mutable list<int> s;int type;
};
list<node> td;
list<node>::iterator it,it2;
int n,a[200005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    list<int> tmp;
    tmp.push_back(1);
    for(int i=2;i<=n;i++){
        if(a[i]!=a[i-1]){
            td.push_back((node){tmp,a[i-1]});
            tmp.clear();
        } 
        tmp.push_back(i);
    }
    td.push_back((node){tmp,a[n]});
    while(!td.empty()){
        for(it=td.begin();it!=td.end();){
            printf("%d ",it->s.front());
            it->s.pop_front();
            if(it->s.empty()) it=td.erase(it);
            else it++;
        }
        for(it=td.begin();it!=td.end();){
            it2=it;it2++;if(it2==td.end()) break;
            if(it->type==it2->type){
                it->s.merge(it2->s);
                td.erase(it2);
            }
            else it++;
        }
        printf("\n");
    }
    return 0;
}