yukicoder : No.2809 Sort Query

これはまぁ何とか。
https://yukicoder.me/problems/no/2809

問題

N要素の整数列Aに対し、以下のクエリに答えよ。

• 指定されたAの1要素を更新する
• Aを昇順にソートする
• 指定されたAの1要素の現在の値を答える

解法

各要素、昇順ソート後に更新されたかどうかを管理する。
更新された要素は、3番目のクエリでその値を答えればよい。

未更新の要素について、Aを座標圧縮しておいて、どの値が何個あるかをBITなどで管理しよう。
BITを二分探索することで、未更新の要素のうち指定された位置の値を求められる。

int N,Q;
ll A[303030];
int X[303030],Y[303030];
ll Z[303030];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> num,val;
set<int> U;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<ll> Vs;
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
		Vs.push_back(A[i]);
		U.insert(i);
	}
	FOR(i,Q) {
		cin>>X[i];
		if(X[i]==1) {
			cin>>Y[i]>>Z[i];
			Y[i]--;
			Vs.push_back(Z[i]);
		}
		else if(X[i]==3) {
			cin>>Y[i];
			Y[i]--;
		}
	}
	sort(ALL(Vs));
	Vs.erase(unique(ALL(Vs)),Vs.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(Vs),A[i])-Vs.begin();
	}
	FOR(i,Q) {
		if(X[i]==1) {
			x=Y[i];
			if(U.count(x)==0) {
				y=val.lower_bound(num(x));
				num.add(x,-1);
				val.add(y,-1);
				U.insert(x);
			}
			A[x]=lower_bound(ALL(Vs),Z[i])-Vs.begin();
		}
		else if(X[i]==2) {
			FORR(x,U) {
				num.add(x,1);
				val.add(A[x],1);
			}
			U.clear();
		}
		else {
			x=Y[i];
			if(U.count(x)) {
				cout<<Vs[A[x]]<<endl;
			}
			else {
				x=num(x);
				y=val.lower_bound(x);
				cout<<Vs[y]<<endl;
			}
		}
	}
}

まとめ

これいい加減ライブラリ化しようかな。