How to insert multiple keys in PBDS

Блог пользователя case3

Автор case3, история, 5 лет назад, По-английски

Hello. This is a CSES problem: Sliding Median. My logic is to have a sorted structure which can store multiple keys in sorted order and then I'll take middle of that data structure and then remove by index and do it again. So my time complexity analysis is: O(nlog(n))

I thought of PBDS. Inserting and sorting is find but how to have multiple keys. Using less_equals is not working for me. Is there anything I can do with PBDS or I need to think of some other logic.

My Code with PBDS I have printed the set so to analyze what was going on.

PS: Please don't tell me the logic just help me with the PBDS and this logic otherwise I'll think about something else then :)

#pbds, #multiset, #cses_sorting, #cses_searching

-9

case3
5 лет назад
17

Комментарии (15)

Показать архивные | Написать комментарий?

soumyadeep_pal_21

5 лет назад, скрыть # |

Try pbds with pairs, insert{a[i],i}.

→ Ответить

case3

5 лет назад, скрыть # ^ |

Thank you I got AC. Can you please tell me why less_equal doesn't work or speaking it like this, what is less_equal in pbds

→ Ответить

soumyadeep_pal_21

5 лет назад, скрыть # ^ |

← Rev. 3 →

I think you are asking how to find number of values less than equal to some x in pbds with pairs. s.order_of_key({x, n+1}) where n=number of elements in array. Or you can use any big value instead of n+1. s=name of pbds you initialized.

→ Ответить

case3

5 лет назад, скрыть # ^ |

Brother I was not asking this but thank you. I am saying that in the declaration of ordered_set I used less_equal instead of less. With this my set containing duplicate values and behaving like multi-set but I am not able to do the operation erase on it. Why?

→ Ответить

soumyadeep_pal_21

5 лет назад, скрыть # ^ |

In multiset we use s.erase(s.find(key)) to erase one occurrence of a value. In pbds i don't think there is such operation.

→ Ответить

case3

5 лет назад, скрыть # ^ |

Then what erase of pbds do?

→ Ответить

soumyadeep_pal_21

5 лет назад, скрыть # ^ |

What generally erase does !!!!!

→ Ответить

case3

5 лет назад, скрыть # ^ |

← Rev. 2 →

It's not doing that :))) It's just there erasing nothing but my hopes

→ Ответить

soumyadeep_pal_21

5 лет назад, скрыть # ^ |

Anyways hope is a good thing.

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

You are not just unable to do erase, you're unable to use pretty much anything else, because using less_equal is UB. God, please don't use it, use a normal solution like what palsoumyadeep suggested.

→ Ответить

case3

5 лет назад, скрыть # ^ |

Why are you so pissed off with less_equal? But the thing is, why it is the upper_bound? If I have {1,2,5,5,5,6,9} 0 based indexing, What is s.find(5) ? Just explain me this if you have a bit of time :)

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

Because the standard requires the comparator to have transitivity of less-then, greater-than and equal-to relations, along with law of trichotomy, which does not hold for $$$\le$$$ operator, which is precisely the reason why less_equal and upper_bound get swapped, and find and erase stop working.

→ Ответить

parveen1981

5 лет назад, скрыть # |

← Rev. 2 →

The mistake you doing in your code is that you are erasing elements with value instead of iterator. Use find to first find the value and then use erase on the found iterator.

My code

// C++ Program to implement the 
// above approach 
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
 
using namespace std; 
using namespace __gnu_pbds; 
 
// Policy based data structure 
typedef tree<int, null_type, 
			less_equal<int>, rb_tree_tag, 
			tree_order_statistics_node_update> 
	indexed_set; 
 
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 200100
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll> 
void sout(){
	cout<<endl;
}
template <typename T,typename... Types>
void sout(T var1,Types... var2){
	cout<<var1<<" ";
	sout(var2...);
}
/*******************************************************************/
 
 
void solve(){
	indexed_set s;
	int n,k;
	cin>>n>>k;
	int a[n];
	rep(i,0,n){
		cin>>a[i];
	}
	rep(i,0,k){
		s.insert(a[i]);
	}
	if(k%2==1){
		cout<<(*s.find_by_order(k/2))<<" ";
	} else{
		cout<<(*s.find_by_order(k/2-1))<<" ";
	}
	rep(i,k,n){
		s.erase(s.find_by_order(s.order_of_key(a[i-k])));
		s.insert(a[i]);
		if(k%2==1){
			cout<<(*s.find_by_order(k/2))<<" ";
		} else{
			cout<<(*s.find_by_order(k/2-1))<<" ";
		}
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	// cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

→ Ответить

case3

5 лет назад, скрыть # ^ |

erase also takes up a value. So if i am giving it a value directly it gives me s.end() iterator on find as I checked now. So order_by_key works and not erase(find) in using less_equal. Can you explain me why :)

→ Ответить