We have an array of n positive integers and m quires. Each query can be one of the following two types.
[i, j][i, j] such that array elements will be like this(a[i+1],a[i],a[i+3],a[i+2],..............,a[j],a[j-1]) given that this range length will be even. where a[i] is array element at i index.
Following are the limits
2 ≤ n,m ≤ 2×10^5
1 ≤ a[i] ≤ 10^6
1≤ i ≤ j ≤n
I tried with segment trees but these are taking more than 2 secs. Can anybody suggest best data structure Or any best approach?
Here is my code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int sgtree[524288];
int data[200005];
int treeind[200005];
int constructSgTree(int start,int end,int index){
if(start==end){
sgtree[index]=data[start];
treeind[start]=index;
return data[start];
}
else{
int mid=start+(end-start)/2;
sgtree[index]=constructSgTree(start,mid,index*2+1)+constructSgTree(mid+1,end,index*2+2);
return sgtree[index];
}
}
int sumSgTree(int start,int end,int i,int j,int index){
if(i<=start&&j>=end){
return sgtree[index];
}
else if(i>end||j<start){
return 0;
}
else{
int mid=start+(end-start)/2;
return sumSgTree(start,mid,i,j,2*index+1)+sumSgTree(mid+1,end,i,j,2*index+2);
}
}
void updateSgTree(int start,int end,int i,int val,int index){
if(i<start||i>end){
return ;
}
else{
sgtree[index]+=val;
if(start!=end)
{
int mid=start+(end-start)/2;
updateSgTree(start,mid,i,val,2*index+1);
updateSgTree(mid+1,end,i,val,2*index+2);
}
}
}
int main() {
int n,i,q,op,l,r,temp,j,temp1,temp2,temp3;
cin>>n>>q;
float sum=0;
for(i=0;i<n;i++){
cin>>data[i];
//dataind[i]=i;
}
constructSgTree(0,n-1,0);
/*
for(i=0;i<n;i++){
cout<<sgtree[treeind[i]]<<" ";
}
*/
//cout<<endl;
for(i=0;i<q;i++){
cin>>op>>l>>r;
l--;
r--;
if(op==2){
j=l;
/*
sum=0.0;
while(j<=r){
/*
temp=data[j]-sgtree[treeind[j]];
if(temp!=0){
updateSgTree(0,n-1,j,temp,0);
}
sum+=data[j];
j++;
}
cout<<sum<<endl;
*/
cout<<sumSgTree(0,n-1,l,r,0)<<endl;
}
else{
while(l<=r){
//temp=data[l+1]-data[l];
if(l!=r){
temp=sgtree[treeind[l]];
sgtree[treeind[l]]=sgtree[treeind[l+1]];
sgtree[treeind[l+1]]=temp;
temp1=(treeind[l]-1)/2;
temp2=(treeind[l+1]-1)/2;
while(temp1!=temp2){
if(temp1<temp2){
sgtree[temp2]=sgtree[temp2]+data[l]-data[l+1];
temp2=(temp2-1)/2;
}
else{
sgtree[temp1]=sgtree[temp1]-data[l]+data[l+1];
temp1=(temp1-1)/2;
}
}
//updateSgTree(0,n-1,l,temp,0);
//updateSgTree(0,n-1,l+1,-temp,0);
/*
temp=data[l];
data[l]=data[l+1];
data[l+1]=temp;
*/
temp=data[l];
data[l]=data[l+1];
data[l+1]=temp;
}
l+=2;
}
}
}
return 0;
}
The time complexity of your solution is at least O(n)(maybe it is O(n log n)) per query, so it is obviously too slow.
Here is a solution that requires O(log n) time per query:
Let's build to treaps with implicit keys: the first one will contain all elements that have an even index and the second one will contain all elements that have an odd index. Both trees should keep elements sorted according to their index in the given array.
A sum query is pretty straightforward: we know the smallest and the largest odd and even index within the range, so we can run this query on the first and the second tree and return the sum.
A swap query can be processed in the following way: let's split the first tree into L1, M1, R1 parts and the second one into L2, M2, R2(where M1 and M2 is the part that lies inside the query range). Then we should swap M1 and M2 and merge trees back, that is, the first tree is the result of merging L1, M2, R1 and the second one is L2, M1, R2.
Each query requires constant number of merge and split operations, so the total time complexity is O((n + m) * log n) or O(n + m * log n)(it depends on the way we construct these treaps before answering queries).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments