Signals after Adjacent Submarine Swaps
Autumn Tournament (2011)
Submission name: submarines.cpp
Problem summary
Submarines have distinct depths and equally spaced horizontal positions. Each sends a signal to the nearest deeper submarine to its right, if one exists. Swap adjacent positions and report the largest number of signals received by one submarine.
Input
N M; N depths; M commands. Command0 requests the maximum; command i>0 swaps positions i and i+1.
Output
One maximum incoming-signal count for each command0.
Constraints
N≤1000000;M≤100000;distinct depths between1 and3000000 mm;horizontal separation5000000 mm.
Worked example
An independently prepared worked example; constructive outputs may have other valid forms.
Input
9 3 100 300 50 1000 1100 1200 500 400 600 0 1 0
Output
2 3
Solution analysis
- The vertical difference is less than3 km, whereas each horizontal gap is5 km. The first deeper submarine to the right is closer than every later deeper submarine. Each receiver is therefore precisely the next strictly greater depth to the right.
- Initialize incoming counts using a decreasing stack: when a new larger depth arrives, every popped position sends to it. A segment tree stores maximum depth, sum of incoming counts and maximum incoming count. It locates the first or last depth above a threshold and sums counts over an interval.
- When adjacent depths a<b become b,a, all signals entering either old position merge at the first position except the old signal a→b. Its count becomes count[a]+count[b]−1; the second count becomes0. The first later depth larger than a gains one signal.
- For a>b becoming b,a, find the last earlier depth greater than b. Let the intervening interval have L positions and internal incoming-count sum S. Exactly L−S signals leave that interval for b. Set the first new count to L−S and the second to oldCount[a]−(L−S)+1. The first later depth greater than b loses one signal. Other receivers are unchanged.
- In the sample, initially depths300 and1000 each receive two signals. Swapping100 and300 makes1000 receive signals from300,100 and50, so the maximum changes from2 to3.
Why it works
The next-greater characterization follows from the horizontal/vertical bounds. Signals outside the described interval keep the same first deeper receiver. Every vertex inside the split interval either sends within it or exits to one of the swapped positions, giving L−S. These local changes preserve exact incoming counts; the segment-tree maximum answers each report.
Watch out. Counts belong to positions after each swap. Search for the later receiver strictly after both swapped positions. The increasing-to-decreasing merge uses the sum of both counts minus1, not their difference.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Node{
int depth=0;
int sum=0;
int best=0;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>depth(n+1),count(n+1),stack;
for(int i=1;i<=n;i++){
cin>>depth[i];
while(!stack.empty()&&depth[stack.back()]<depth[i]){
count[i]++;
stack.pop_back();
}
stack.push_back(i);
}
int size=1;
while(size<n){
size*=2;
}
vector<Node>tree(2*size);
auto pull=[&](int p){
tree[p].depth=max(tree[2*p].depth,tree[2*p+1].depth);
tree[p].sum=tree[2*p].sum+tree[2*p+1].sum;
tree[p].best=max(tree[2*p].best,tree[2*p+1].best);
};
for(int i=1;i<=n;i++){
tree[size+i-1]={depth[i],count[i],count[i]};
}
for(int p=size-1;p>0;p--){
pull(p);
}
auto update=[&](int i){
int p=size+i-1;
tree[p]={depth[i],count[i],count[i]};
for(p/=2;p>0;p/=2){
pull(p);
}
};
auto sum=[&](int l,int r){
int result=0;
for(l+=size-1,r+=size-1;l<=r;l/=2,r/=2){
if(l%2==1){
result+=tree[l++].sum;
}
if(r%2==0){
result+=tree[r--].sum;
}
}
return result;
};
// Prune branches whose maximum cannot exceed the threshold.
auto first=[&](auto&&self,int p,int l,int r,int start,int value)->int{
if(r<start||tree[p].depth<=value){
return n+1;
}
if(l==r){
return l;
}
int mid=(l+r)/2;
int answer=self(self,2*p,l,mid,start,value);
if(answer<=n){
return answer;
}
return self(self,2*p+1,mid+1,r,start,value);
};
auto last=[&](auto&&self,int p,int l,int r,int finish,int value)->int{
if(l>finish||tree[p].depth<=value){
return 0;
}
if(l==r){
return l;
}
int mid=(l+r)/2;
int answer=self(self,2*p+1,mid+1,r,finish,value);
if(answer>0){
return answer;
}
return self(self,2*p,l,mid,finish,value);
};
while(m--){
int i;
cin>>i;
if(i==0){
cout<<tree[1].best<<'\n';
continue;
}
int small=min(depth[i],depth[i+1]);
int later=first(first,1,1,size,i+2,small);
if(depth[i]<depth[i+1]){
count[i]+=count[i+1]-1;
count[i+1]=0;
if(later<=n){
count[later]++;
}
}
else{
int earlier=last(last,1,1,size,i-1,small);
int transferred=i-earlier-1-sum(earlier+1,i-1);
int old=count[i];
count[i]=transferred;
count[i+1]=old-transferred+1;
if(later<=n){
count[later]--;
}
}
swap(depth[i],depth[i+1]);
update(i);
update(i+1);
if(later<=n){
update(later);
}
}
}