#994302 (C++23) No.2809 Sort Query

提出ソース

結果

問題	No.2809 Sort Query
ユーザー	nouka28
提出日時	2024-07-12 22:08:55
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,255 ms / 2,000 ms
コード長	18,927 bytes
コンパイル時間	7,251 ms
コンパイル使用メモリ	339,128 KB
実行使用メモリ	53,764 KB
最終ジャッジ日時	2024-07-12 22:10:26
合計ジャッジ時間	84,855 ms
ジャッジサーバーID （参考情報）	judge6 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1,056 ms 51,352 KB
testcase_02	AC	1,057 ms 51,356 KB
testcase_03	AC	974 ms 51,480 KB
testcase_04	AC	958 ms 51,488 KB
testcase_05	AC	943 ms 51,352 KB
testcase_06	AC	1,094 ms 51,364 KB
testcase_07	AC	1,131 ms 51,736 KB
testcase_08	AC	1,193 ms 51,612 KB
testcase_09	AC	1,120 ms 51,348 KB
testcase_10	AC	1,112 ms 51,480 KB
testcase_11	AC	1,060 ms 53,508 KB
testcase_12	AC	1,058 ms 53,512 KB
testcase_13	AC	1,086 ms 53,508 KB
testcase_14	AC	1,057 ms 53,632 KB
testcase_15	AC	1,057 ms 53,508 KB
testcase_16	AC	1,069 ms 53,504 KB
testcase_17	AC	1,051 ms 53,512 KB
testcase_18	AC	1,067 ms 53,504 KB
testcase_19	AC	1,069 ms 53,764 KB
testcase_20	AC	1,094 ms 53,508 KB
testcase_21	AC	1,193 ms 53,760 KB
testcase_22	AC	1,183 ms 53,764 KB
testcase_23	AC	1,197 ms 53,508 KB
testcase_24	AC	1,184 ms 53,512 KB
testcase_25	AC	1,150 ms 53,636 KB
testcase_26	AC	1,158 ms 51,220 KB
testcase_27	AC	1,140 ms 51,356 KB
testcase_28	AC	1,155 ms 51,476 KB
testcase_29	AC	1,130 ms 51,220 KB
testcase_30	AC	1,161 ms 51,480 KB
testcase_31	AC	1,055 ms 51,348 KB
testcase_32	AC	1,060 ms 51,352 KB
testcase_33	AC	1,093 ms 51,112 KB
testcase_34	AC	1,107 ms 51,348 KB
testcase_35	AC	1,097 ms 51,356 KB
testcase_36	AC	1,048 ms 53,764 KB
testcase_37	AC	1,055 ms 53,504 KB
testcase_38	AC	1,074 ms 53,508 KB
testcase_39	AC	1,066 ms 53,508 KB
testcase_40	AC	1,001 ms 53,508 KB
testcase_41	AC	1,169 ms 51,352 KB
testcase_42	AC	1,255 ms 51,348 KB
testcase_43	AC	1,188 ms 51,348 KB
testcase_44	AC	1,204 ms 51,312 KB
testcase_45	AC	1,222 ms 51,352 KB
testcase_46	AC	813 ms 51,328 KB
testcase_47	AC	841 ms 51,348 KB
testcase_48	AC	853 ms 51,352 KB
testcase_49	AC	846 ms 51,224 KB
testcase_50	AC	869 ms 51,476 KB
testcase_51	AC	766 ms 36,608 KB
testcase_52	AC	645 ms 36,608 KB
testcase_53	AC	697 ms 36,608 KB
testcase_54	AC	678 ms 36,736 KB
testcase_55	AC	648 ms 36,736 KB
testcase_56	AC	813 ms 30,604 KB
testcase_57	AC	574 ms 23,460 KB
testcase_58	AC	538 ms 26,164 KB
testcase_59	AC	540 ms 19,660 KB
testcase_60	AC	808 ms 42,656 KB
testcase_61	AC	1,064 ms 50,736 KB
testcase_62	AC	586 ms 24,524 KB
testcase_63	AC	789 ms 33,300 KB
testcase_64	AC	1,189 ms 49,756 KB
testcase_65	AC	639 ms 35,752 KB
testcase_66	AC	2 ms 6,940 KB
testcase_67	AC	2 ms 6,940 KB
testcase_68	AC	2 ms 6,940 KB
testcase_69	AC	2 ms 6,940 KB
testcase_70	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma region template
/*
	template made by nouka28
	last update 2024.7.7
*/

//include
#include<bits/stdc++.h>
using namespace std;

//atcoder
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
// using mint=atcoder::modint1000000007;
// using mint=atcoder::modint;
istream& operator>>(istream&is,mint &x){long long x_;is>>x_;x=x_;return is;}
ostream& operator<<(ostream&os,mint &x){os<<x.val();return os;}

//pragma
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

//define
// #define int long long
#define pb push_back
#define eb emplace_back
#define ep emplace
#define fi first
#define se second

#define ALL(x) begin(x),end(x)
#define LEN(x) (signed int)(x.size())
#define BIT(x,i) ((x)>>(i)&1)

//using
using u32=unsigned int;
using u64=unsigned long long;
using ull=unsigned long long;
using i32=signed int;
using i64=signed long long;
using ll=signed long long;
using f64=double;
using f80=long double;
using pi=pair<i32,i32>;
using pl=pair<i64,i64>;
using pd=pair<f80,f80>;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T>using VVV=V<V<V<T>>>;
template<class T>using VVVV=V<V<V<V<T>>>>;
template<class T>using VVVVV=V<V<V<V<V<T>>>>>;
template<class T>using pqmax=priority_queue<T>;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;


using u128=__uint128_t;
using i128=__int128_t;
//io INT128
i128 i128_parse(string &s){i128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
u128 u128_parse(string &s){u128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
istream &operator>>(istream &is,i128 &x){string s;is>>s;x=i128_parse(s);return is;}
istream &operator>>(istream &is,u128 &x){string s;is>>s;x=u128_parse(s);return is;}
ostream &operator<<(ostream &os,i128 x){
	ostream::sentry s(os);
	if(s){u128 tmp=x<0?-x:x;char buffer[128];char *d=end(buffer);
		do{--d;*d="0123456789"[tmp%10];tmp/=10;}while(tmp!=0);
		if(x<0){--d;*d='-';}
		int len=end(buffer)-d;
		if (os.rdbuf()->sputn(d,len)!=len){os.setstate(ios_base::badbit);}
	}
	return os;
}

//const
const i64 LINF=0x1fffffffffffffff;
const i32 INF=0x3fffffff;
const i64 MOD=998244353;
const i64 MOD2=1000000007;
const f80 PI=3.1415926535897932384626433832795028841971;
const f80 DINF=numeric_limits<f80>::infinity();
const f80 EPS=1e-9;
const i64 di[]={0,1,0,-1,1,-1,1,-1};
const i64 dj[]={1,0,-1,0,1,1,-1,-1};

//function
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name

#define rep1(n) for(i64 i=0;i<n;i++)
#define rep2(i,n) for(i64 i=0;i<n;i++)
#define rep3(i,a,b) for(i64 i=a;i<b;i++)
#define rep4(i,a,b,c) for(i64 i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)

#define rrep1(n) for(i64 i=n;i--;)
#define rrep2(i,n) for(i64 i=n;i--;)
#define rrep3(i,a,b) for(i64 i=b;i-->(a);)
#define rrep4(i,a,b,c) for(i64 i=(a)+((b)-(a)-1)/(c)*(c)i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define SUM(...) accumulate(ALL(__VA_ARGS__),i64(0))
#define DSUM(...) accumulate(ALL(__VA_ARGS__),f80(0))

template<class T>bool chmin(T &x,const T&y){if(x>y){x=y;return true;}return false;}
template<class T>bool chmax(T &x,const T&y){if(x<y){x=y;return true;}return false;}
template<class T>i32 lob(const V<T>&arr,const T&v){return (i32)(lower_bound(ALL(arr),v)-arr.begin());}
template<class T>i32 upb(const V<T>&arr,const T&v){return (i32)(upper_bound(ALL(arr),v)-arr.begin());}


template<class T>constexpr auto min(T a,T b,T c){return min(a,min(b,c));}
template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<class T>constexpr auto max(T a,T b,T c){return max(a,max(b,c));}
template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}

//io
struct SetUpIO{
	SetUpIO(){
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout<<fixed<<setprecision(15);
	}
}set_up_io;

//in
void scan(char &x){cin>>x;}
void scan(u32&x){cin>>x;}
void scan(u64 &x){cin>>x;}
void scan(i32 &x){cin>>x;}
void scan(i64 &x){cin>>x;}
void scan(string &x){cin>>x;}
void scan(mint &x){cin>>x;}

template<class T1,class T2>void scan(pair<T1,T2> &x){scan(x.first);scan(x.second);}
template<class T>void scan(V<T> &x){for(T &ele:x){scan(ele);}}
template<class T>void scan(deque<T> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(array<T,size> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(T (&x)[size]){for(T &ele:x){scan(ele);}}

void rd(){}
template<class Head,class... Tail>void rd(Head &head,Tail &...tail){scan(head);rd(tail...);}
#define CHR(...) char __VA_ARGS__;rd(__VA_ARGS__)
#define U32(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define U64(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define I32(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define I64(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define UINT(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define ULL(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define INT(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define LL(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;rd(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size);rd(name);
#define VVEC(type,name,size1,size2) VV<type> name(size1,V<type>(size2));rd(name)

//out
void print(){putchar(' ');}
void print(bool x){printf("%d",x);}
void print(u32 x){printf("%u",x);}
void print(u64 x){printf("%llu",x);}
void print(i32 x){printf("%d",x);}
void print(i64 x){printf("%lld",x);}
void print(char x){printf("%c",x);}
void print(f64 x){printf("%.15f",x);}
void print(f80 x){printf("%.15Lf",x);}
void print(const string &x){for(auto&&i:x)print(i);}
void print(mint x){printf("%d",x.val());}
template<class T>void print(const V<T>&);
template<class T1,class T2>void print(const pair<T1,T2>&x){print(x.first);putchar(' ');print(x.second);}
template<class T>void print(complex<T>&x){if(x.real()>=0)print('+');print(x.real());if(x.imag()>=0)print('+');print(x.imag());print('i');}
template<class T>void print(const V<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const deque<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T1,class T2>void print(map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T1,class T2>void print(unordered_map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T, size_t size> void print(const array<T, size>& x){ print(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(' '); print(*i); } }
template<class T,i32 size>void print(const T(&x)[size]){print(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ');*/print(*i);}}

template<class T>void print(const T&a){cout<<a;}
int out(){putchar('\n');return 0;}
template<class T>int out(const T&t){print(t);putchar('\n');return 0;}
template<class Head,class... Tail>int out(const Head&head,const Tail&...tail){print(head);putchar(' ');out(tail...);return 0;}

#ifdef LOCAL
void dbg(){putchar(' ');}
void dbg(bool x){printf("%d",x);}
void dbg(u32 x){printf("%u",x);}
void dbg(u64 x){printf("%llu",x);}
void dbg(i32 x){printf("%d",x);}
void dbg(i64 x){printf("%lld",x);}
void dbg(char x){printf("%c",x);}
void dbg(f64 x){printf("%.15f",x);}
void dbg(f80 x){printf("%.15Lf",x);}
void dbg(const string &x){for(auto&&i:x)dbg(i);}
void dbg(mint x){printf("%d",x.val());}
template<class T>void dbg(const V<T>&);
template<class T1,class T2>void dbg(const pair<T1,T2>&x){putchar('(');dbg(x.first);putchar(',');dbg(x.second);putchar(')');}
template<class T>void dbg(complex<T>&x){if(x.real()>=0)dbg('+');dbg(x.real());if(x.imag()>=0)dbg('+');dbg(x.imag());dbg('i');}
template<class T>void dbg(const V<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}
template<class T>void dbg(const deque<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}
template<class T>void dbg(const set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const unordered_set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const unordered_multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T1,class T2>void dbg(map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T1,class T2>void dbg(unordered_map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T, size_t size> void dbg(const array<T, size>& x){ putchar('[');dbg(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(','); dbg(*i); } putchar(']');}
template<class T,i32 size>void dbg(const T(&x)[size]){/*putchar('[');*/dbg(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ')*/;dbg(*i);}/*putchar(']');*/}

template<class T>void dbg(const T&a){cout<<a;}
int dbg2(){putchar('\n');return 0;}
template<class T>int dbg2(const T&t){dbg(t);putchar('\n');return 0;}
template<class Head,class... Tail>int dbg2(const Head&head,const Tail&...tail){dbg(head);putchar(' ');dbg2(tail...);return 0;}

#define debug(...) {dbg((string)(#__VA_ARGS__));dbg(":");dbg2(__VA_ARGS__);}
#else
#define debug(...) void(0)
#endif

//random
random_device rnd;mt19937 mt(rnd());const i64 MT_MAX=LINF;
uniform_int_distribution<i64> RAND(0,MT_MAX);
f64 randd(){return 1.0*RAND(mt)/MT_MAX;}
//random value [a,b]
i64 randint(i64 a,i64 b){return a+RAND(mt)%(b-a+1);}

//funtion2
#define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__}))
vector<vector<i64>> __MAKE_MAT__(vector<i64> v){
	if(v.empty())return vector<vector<i64>>(1,vector<i64>());
	i64 n=v.back();v.pop_back();vector<vector<i64>> ret,tmp=__MAKE_MAT__(v);
	for(auto e:tmp)for(i64 i=0;i<n;++i){ret.push_back(e);ret.back().push_back(i);}
	return ret;
}

//V',Pを返す。PはVを昇順に並べた時のidx
template<class T>
pair<vector<T>,vector<i32>> sortperm(vector<T> v){
	vector<pair<T,int>> sv;
	for(i32 i=0;i<(i32)v.size();i++){sv.push_back({v[i],i});}
	sort(sv.begin(),sv.end());vector<T> rv;vector<i32> p;
	for(auto[x,idx]:sv){rv.push_back(x);p.push_back(idx);}
	return {rv,p};
}
i64 pow(i64 a,i64 b){i64 x=1;while(b){if(b&1){x*=a;}a=a*a;b>>=1;}return x;}
bool isupper(char x){return('A'<=x&&x<='Z');}
bool islower(char x){return('a'<=x&&x<='z');}
char upper(char &x){if(isupper(x)){return x;}return x-'a'+'A';}
char lower(char &x){if(islower(x)){return x;}return x-'A'+'a';}
string upper(string s){for(auto&e:s)e=upper(e);return s;}
string lower(string s){for(auto&e:s)e=lower(e);return s;}
bool isdigit(char x){return('0'<=x&&x<='9');}
bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;}

#pragma endregion


template<class T> T SortedMultiList_default_op(T a,T b){return max(a,b);}
template<class T> T SortedMultiList_default_e(){return 0;}

template<class T,T(*op)(T,T)/*=SortedMultiList_default_op<T>*/,T(*e)()/*=SortedMultiList_default_e<T>*/>

class SortedMultiList{
    struct Node{
        T key,acc;
        int priority,cnt;
        Node *l,*r;
        Node(T key,int priority):key(key),acc(key),priority(priority),cnt(1),l(nullptr),r(nullptr){}
    }*root=nullptr;
    using Tree=Node*;
    
    int cnt(Tree t){
        return t?t->cnt:0;
    }
    
    T acc(Tree t){
        return t?t->acc:e();
    }

    void update(Tree &t){
        if(t){
            t->cnt=1+cnt(t->l)+cnt(t->r);
            t->acc=op(op(acc(t->l),t->key),acc(t->r));
        }
    }

    void split(Tree t,T key,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(key<t->key){
            split(t->l,key,l,t->l),r=t;
        }else{
            split(t->r,key,t->r,r),l=t;
        }
        update(t);
    }

    void split_by_index(Tree t,int idx,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(cnt(t->l)>=idx){
            split_by_index(t->l,idx,l,t->l),r=t;
        }else{
            split_by_index(t->r,idx-cnt(t->l)-1,t->r,r),l=t;
        }
        update(t);
    }

    void merge(Tree &t,Tree l,Tree r){
        if(!l||!r){
            t=l?l:r;
        }else if(l->priority>r->priority){
            merge(l->r,l->r,r),t=l;
        }else{
            merge(r->l,l,r->l),t=r;
        }
        update(t);
    }

    void insert(Tree &t,Tree item){
        if(!t){
            t=item;
        }else if(item->priority>t->priority){
            split(t,item->key,item->l,item->r),t=item;
            update(t);
        }else{
            insert(item->key<t->key?t->l:t->r,item);
            update(t);
        }
    }

    void erase(Tree &t,T key){
        if(!t)return;
        if(t->key==key){
            merge(t,t->l,t->r);
            update(t);
        }else{
            erase(key<t->key?t->l:t->r,key);
            update(t);
        }
    }

    bool find(Tree &t,T key){
        if(!t){
            return false;
        }else if(t->key==key){
            return true;
        }else{
            return find(key<t->key?t->l:t->r,key);
        }
    }

    T index(Tree &t,int idx){
        int siz=(t->l?t->l->cnt:0);
        if(idx==siz){
            return t->key;
        }else if(idx<siz){
            return index(t->l,idx);
        }else{
            return index(t->r,idx-siz-1);
        }
    }

    int lower_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>=key){
            return lower_bound(t->l,key);
        }else{
            return siz+1+lower_bound(t->r,key);
        }
    }

    int upper_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>key){
            return upper_bound(t->l,key);
        }else{
            return siz+1+upper_bound(t->r,key);
        }
    }

    T prod(Tree t,int l,int r){
        Tree t1,t2,t3;
        split_by_index(t,l,t1,t2);
        split_by_index(t2,r-l,t2,t3);
        T res=acc(t2);
        merge(t2,t2,t3);
        merge(t,t1,t2);
        return res;
    }

    template<class F>
    int max_right(Tree t,const F &f,T product){
        if(!f(product))return 0;
        if(f(op(product,acc(t))))return cnt(t);
        int m=max_right(t->l,f,product);
        if(m<cnt(t->l))return m;
        product=op(product,acc(t->l));
        if(!f(op(product,t->key)))return cnt(t->l);
        product=op(product,t->key);
        return cnt(t->l)+1+max_right(t->r,f,product);
    }

    template<class F>
    int min_left(Tree t,const F &f,T product){
        if(!f(product))return cnt(t);
        if(f(op(product,acc(t))))return 0;
        int m=min_left(t->r,f,product);
        if(0<m)return cnt(t->l)+1+m;
        product=op(product,acc(t->r));
        if(!f(op(product,t->key)))return cnt(t->l)+1;
        product=op(product,t->key);
        return min_left(t->l,f,product);
    }

    void to_vector(Tree t,vector<T> &vec){
        if(!t)return;
        to_vector(t->l,vec);
        vec.push_back(t->key);
        to_vector(t->r,vec);
    };

    void dump(Tree t){
        if(!t)return;
        if(t->l){
            dump(t->l);cout<<" ";
        }
        cout<<t->key;
        if(t->r){
            cout<<" ";dump(t->r);
        }
    };

    public:

    void insert(T key){
        insert(root,new Node(key,randint(0,1LL<<63)));
    }

    void erase(T key){
        erase(root,key);
    }

    bool find(T key){
        return find(root,key);
    }

    T index(int idx){
        return index(root,idx);
    }

    T operator[](int idx){
        return index(root,idx);
    }

    int lower_bound(T key){
        return lower_bound(root,key);
    }

    int upper_bound(T key){
        return upper_bound(root,key);
    }

    int count(T key){
        return upper_bound(root,key)-lower_bound(root,key);
    }

    int size(){
        return (root?root->cnt:0);
    }

    T prod(int l,int r){
        return prod(root,l,r);
    }

    template<bool(*f)(T)>int max_right(int l){
        return max_right(l,[](T x){return f(x);});
    }

    template<class F>int max_right(int l,const F& f){
        assert(l<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,l,t1,t2);
        int res=l+max_right(t2,f,product);
        merge(root,t1,t2);
        return res;
        
    }

    template<bool (*f)(T)>int min_left(int r){
        return min_left(r,[](T x){return f(x);});
    }

    template<class F>int min_left(int r,const F& f){
        assert(r<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,r,t1,t2);
        int res=min_left(t1,f,product);
        merge(root,t1,t2);
        return res;
    }

    vector<T> to_vector(){
        vector<T> vec;to_vector(root,vec);
        return vec;
    }

    void dump(){
        dump(root);
        cout<<endl;
    }

    constexpr bool operator==(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()==rhs.to_vector();
    }
    constexpr bool operator!=(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()!=rhs.to_vector();
    }
};

ll op(ll a,ll b){return max(a,b);}
ll e(){return 0;}

int main(){
	INT(n,q);
	map<int,ll> f;
	rep(i,n){
		LL(a);f[i]=a;
	}
	SortedMultiList<ll,op,e> st;
	rep(i,n)st.insert(0);
	while(q--){
		INT(t);
		if(t==1){
			LL(k,x);
			k--;
			f[k]=x;
		}
		if(t==2){
			V<int> idxs;
			for(auto&&[u,v]:f){
				idxs.pb(u);
			}
			reverse(ALL(idxs));
			for(auto&&e:idxs){
				st.erase(st[e]);
			}
			for(auto&&[u,v]:f){
				st.insert(v);
			}
			f.clear();
		}
		if(t==3){
			INT(k);k--;
			if(f.count(k)){
				out(f[k]);
			}else{
				out(st[k]);
			}
		}
	}
}

yukicoder

結果

テストケース

ソースコード