c_Comp-Prog yukicoder No.318 学学学学学

遅延セグ木使いてーーーーーーーーーって言いながらPriorityQueueで解きました

問題

読んでください

解説

まずそれぞれの数値に対して、その数値がある左端と右端の場所しか必要ないことがわかる。

よって、まずはその値を保存する。

そして、$ \lbrack l,r)となる様にimos法の要領で数値を置いていく配列を作る。この時、同じ場所に複数個の値が入ることがあるため(最大2個)、2次元配列を用意する。

そしてこの配列を順番になめる時に、lの方の値が出てきたら追加用のPriorityQueueに追加、rの方の値が出てきたら削除用のPriorityQueueに追加する。この時、追加用と削除用のPriorityQueueのTopが同じだった場合は削除する。

そして追加用のPriorityQueueにTopに存在する値が最大値となるので、それを出力する。

この時、それぞれのPriorityQueueには1要素(正確には現れた数一つにつき1要素)につき最大2回の操作しか行われないので、計算量は$ O(NlogN)となる。(はず)

code:solve.cpp

int main(){

int n;cin>>n;

map<int,pair<int,int>> A;

for(int i = 0; n > i; i++){

int t;cin>>t;

if(!At.first)At.first = i+1;

At.second = i+1;

}

vector<int> retn+1;

for(auto x: A){

retx.second.first-1.push_back(x.first);

retx.second.second.push_back(-x.first);

}

priority_queue<int> C;

priority_queue<int> eraser;

for(int i = 0; n > i; i++){

for(int j = 0; reti.size() > j; j++){

if(retij>0)C.push(retij);

else if(retij < 0)eraser.push(-retij);

}

while(C.size() && eraser.size() && C.top() == eraser.top()){

C.pop();

eraser.pop();

}

cout << C.top();

if(i+1 != n)cout << " ";

}

cout << endl;

}

感想

こういうのが慣らし計算量って言うんでしたっけ

この後にきちんと解説見たらmax(set)で行けると書かれていた理由を完全に理解してなるほどな～～～！！！ってなりました