Given array of integers as arr, We have two kind of queries
type 1: given value,update array elements less than value to value;
type 2: given index and value, update index of array to value
E,g arr=[1,2,3,4,5];
query type 1:value=3 now arr =[3,3,3,4,5];
query type 2:idx=2 and value=1 now arr=[3,3,1,4,5];
query type 1: value=2 now arr=[3,3,2,4,5]
so final arr will be [3,3,2,4,5]…Anyone have any idea how to solve this type of questions,…I think this can be link to any standard algorithm.!!
This problem can be solved using a data structure such as a Fenwick tree or Segment tree, which are used to perform range updates and single element queries efficiently. The Fenwick tree has an advantage of lower space complexity than the Segment tree, but the Segment tree has better performance for range queries.
You can use 2-Level Linked List with vEB Tree to solve this problem in \Theta(n\log\log n) instead of \Theta(n\log n) with Segment Tree.
First, we use a linked list to represent all the different numbers in the array and store them in ascending order. For example, [3,3,2,5,2] is stored in the linked list as [2,3,5]. This is a 1-level linked list.
Then, use a linked list array and store the positions of all corresponding value elements in the array of corresponding numbers. For example, [3,3,2,5,2], then List [2]=\{3,5\} means a[3]=2 and a[5]=2. This is a 2-Level linked list.
unordered_map<int,list> or read in all operations first and then discretize.Consider operation 1, which in the worst case increases the length of the 1-Level linked list by 1.
Consider operation 2, which changes all values less than x to x, which on a linked list means that all linked lists less than x are linked to the end of x. In addition, you need to create an array that maintains the specific address of the pointer to the 2-Level Linked List where the corresponding idx is located. This will be used to perform the deletion.
Since each 1 operation increases the length of the Level-1 Linked List by at most 1, and each Linked List linked by operation 2 decreases the length of the Level-1 Linked List by 1. So here we can use brute force on operation 2, and although a single operation may take O(n), the total time is guaranteed to be O(n).
And for operations on 1-to-1-Level Linked Lists, you can use vEB Tree instead of Linked List. it’s \Theta(n\log\log n), or use heap in \Theta(n\log n).
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
struct node{node *next,*pred;int value;};
pair<node*,node*> mem[2000001];
pair<node*,node*> uel;
node* pos[2000001];
int n,m,a[2000001];
pair<int,int> opt[2000001];
vector<int> dis;
void discretize() {
for(int i=1;i<=n;++i)
dis.push_back(a[i]);
for(int i=1;i<=m;++i)
dis.push_back(opt[i].second);
sort(dis.begin(),dis.end());
dis.resize(unique(dis.begin(),dis.end())-dis.begin());
for(int i=1;i<=n;++i)
a[i]=lower_bound(dis.begin(),dis.end(),a[i])-dis.begin()+1;
for(int i=1;i<=m;++i)
opt[i].second=lower_bound(dis.begin(),dis.end(),opt[i].second)-dis.begin()+1;
}
void init(pair<node*,node*> &a) {
a.first=new node;
a.second=new node;
a.first->next=a.second;
a.second->pred=a.first;
a.first->pred=nullptr;
a.second->next=nullptr;
a.first->value=-1;
a.second->value=-1;
}
void del(node* &temp) {
temp->next->pred=temp->pred;
temp->pred->next=temp->next;
}
void add_node(pair<node*,node*> &a,node* &temp) {
temp->next=a.second;
temp->pred=a.second->pred;
temp->pred->next=temp;
temp->next->pred=temp;
}
void add_value(pair<node*,node*> &a,int value) {
node* temp=new node;
temp->value=value;
add_node(a,temp);
}
void merge(pair<node*,node*> &a,pair<node*,node*> &b) {
if(b.first->next==b.second) return;
if(a.first->next==a.second) {swap(a,b);return;}
b.first->next->pred=a.second->pred;
a.second->pred->next=b.first->next;
b.second->pred->next=a.second;
a.second->pred=b.second->pred;
b.first->next=b.second;
b.second->pred=b.first;
}
signed main() {
cin >> n >> m;
for(int i=1;i<=n;++i)
cin >> a[i];
for(int i=1,o;i<=m;++i) {
cin >> o;
opt[i].first=-1;
if(o==1)
cin >> opt[i].second;
else
cin >> opt[i].first >> opt[i].second;
}
discretize();
for(int i=1;i<=n+m;++i) init(mem[i]);
vector<char> vis(n+m+1);
set<int> uel;
for(int i=1;i<=n;++i) {
pos[i]=new node;
pos[i]->value=i;
add_node(mem[a[i]],pos[i]);
if(!vis[a[i]])
uel.insert(a[i]);
vis[a[i]]=true;
}
for(int i=1;i<=m;++i)
if(opt[i].first==-1) {
while(*uel.begin()<opt[i].second&&!uel.empty()) {
merge(mem[opt[i].second],mem[*uel.begin()]);
uel.erase(uel.begin());
uel.insert(opt[i].second);
}
} else {
uel.insert(opt[i].second);
del(pos[opt[i].first]);
add_node(mem[opt[i].second],pos[opt[i].first]);
}
for(int i:uel)
for(node* temp=mem[i].first->next;temp!=mem[i].second;temp=temp->next)
a[temp->value]=dis[i-1];
for(int i=1;i<=n;++i)
cout << a[i] << ' ';
}
If you want to reach \Theta(n\log\log n), use vEB and hash instead of set and discretize in the code.