Pacman: Sum Interval Cartesian-Tree Heights
Autumn Tournament (2023)
Submission name: pacman.cpp
Problem summary
The weights w are a permutation. For each interval whose two endpoints belong to S, repeatedly eat its maximum-weight element and keep either the part to its left or the part to its right. The interval score is the maximum possible number of eaten elements before the remaining interval is empty. Sum these scores over all endpoint pairs l<=r in S.
Input
Judge API: long long solve(const vector<int>& w, const vector<int>& S), declared in pacman.h. S contains distinct 1-based positions. The LOCAL driver reads N M, the N weights, then the M positions.
Output
Return the sum of interval scores. The LOCAL driver prints it.
Constraints
1 <= M <= N <= 500000; w is a permutation of 1..N; endpoints in S are distinct; 2 seconds; 512 MB.
Worked example
Original statement sample, using the documented local driver for grader tasks.
Input
4 3 1 4 2 3 1 2 4
Output
11
Solution analysis
- Build the maximum Cartesian tree: inorder order is the array order, and every parent has a larger weight than its descendants. Eating an interval maximum then choosing a side is exactly choosing a root-to-leaf path in its interval Cartesian tree. The interval score is therefore that tree height. A monotone stack constructs the full tree in linear time.
- Process the Cartesian tree bottom-up. For a subtree, store its full height, a multiset of heights for intervals from the subtree left boundary to a selected right endpoint, and a multiset for selected left endpoints to the subtree right boundary. Multiplicities matter: different endpoints can have the same interval height.
- At a root, take X=left-child suffix heights and Y=right-child prefix heights. If the root itself is selected, add a zero-height empty side to both multisets. Increase every height by one. Every interval crossing the root has score max(x,y), so add this quantity over X times Y. The singleton root is included exactly once. Every other interval is handled recursively within a child.
- To form the new boundary distributions, cap every X height from below at rightHeight+1, because an interval ending at the full right boundary also contains the entire right child. Similarly cap Y at leftHeight+1. The new prefix distribution is the union of the left prefixes with capped Y; the new suffix distribution is capped X union right suffixes. A lazy randomized treap supports adding one to all keys, capping a prefix to one height, and destructive multiset union.
- For the cross sum, iterate the smaller distribution. For one height x, a prefix-count/sum query in the other distribution evaluates sum_y max(x,y) = x*count(y<=x) + sum(y>x). Small-to-large merging bounds the total work. In the sample the six intervals [1,1],[1,2],[1,4],[2,2],[2,4],[4,4] have scores 1,2,3,1,3,1, summing to 11.
Why it works
Every interval has a unique maximum, so the Cartesian root partitions intervals into those wholly in a child and those crossing the root. The multiset cross product enumerates the latter exactly once and computes their height by the Cartesian-tree recurrence. Capping and union produce exactly the two boundary interval distributions required by the parent. Structural induction proves the total sum.
Complexity: Expected time O(N + M log^2 M) with randomized treaps and small-to-large cross queries; space O(N+M). Only two treap nodes are allocated per selected endpoint; capped or merged nodes are recycled logically without additional allocation. The Cartesian tree is processed iteratively to handle height N. The answer fits long long.
Watch out. S contains positions, not weights. Do not confuse tree height with interval length. Preserve multiplicities when equal heights merge. Prefix and suffix multisets must use distinct node ownership. Lazy additions must be pushed before split or comparisons. Avoid recursive traversal of a potentially linear-height Cartesian tree.
Commented C++17 solution
Submit solve with pacman.h and no main. Compile -DLOCAL for the sample. Randomization affects only treap balancing, never the computed answer.
#include<algorithm>
#include<cstdint>
#include<iostream>
#include<utility>
#include<vector>
#ifndef LOCAL
#include"pacman.h"
#endif
using namespace std;
namespace Pacman{
struct Node{
int left=0;
int right=0;
int key=0;
int frequency=0;
int count=0;
int lazy=0;
uint32_t priority=0;
long long sum=0;
};
vector<Node>nodes;
uint32_t seed;
uint32_t randomPriority(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
int create(int key){
Node node;
node.key=key;
node.frequency=1;
node.count=1;
node.priority=randomPriority();
node.sum=key;
nodes.push_back(node);
return (int)nodes.size()-1;
}
void pull(int root){
Node&node=nodes[root];
node.count=nodes[node.left].count+node.frequency+nodes[node.right].count;
node.sum=nodes[node.left].sum+1LL*node.key*node.frequency+nodes[node.right].sum;
}
void add(int root,int delta){
if(root==0){
return;
}
nodes[root].key+=delta;
nodes[root].lazy+=delta;
nodes[root].sum+=1LL*delta*nodes[root].count;
}
void push(int root){
int delta=nodes[root].lazy;
if(delta!=0){
add(nodes[root].left,delta);
add(nodes[root].right,delta);
nodes[root].lazy=0;
}
}
// Split by height, retaining multiplicities in each treap.
pair<int,int>split(int root,int key){
if(root==0){
return {0,0};
}
push(root);
if(nodes[root].key<=key){
auto parts=split(nodes[root].right,key);
nodes[root].right=parts.first;
pull(root);
return {root,parts.second};
}
auto parts=split(nodes[root].left,key);
nodes[root].left=parts.second;
pull(root);
return {parts.first,root};
}
int unite(int first,int second){
if(first==0||second==0){
return first+second;
}
if(nodes[first].priority<nodes[second].priority){
swap(first,second);
}
push(first);
auto below=split(second,nodes[first].key-1);
auto equal=split(below.second,nodes[first].key);
nodes[first].frequency+=nodes[equal.first].count;
nodes[first].left=unite(nodes[first].left,below.first);
nodes[first].right=unite(nodes[first].right,equal.second);
pull(first);
return first;
}
int raiseMinimum(int root,int height){
auto parts=split(root,height);
if(parts.first==0){
return parts.second;
}
int rootOfLow=parts.first;
int count=nodes[rootOfLow].count;
// Reuse one node for all capped heights; no new allocation is needed.
nodes[rootOfLow].left=0;
nodes[rootOfLow].right=0;
nodes[rootOfLow].lazy=0;
nodes[rootOfLow].key=height;
nodes[rootOfLow].frequency=count;
pull(rootOfLow);
return unite(rootOfLow,parts.second);
}
pair<int,long long>prefix(int root,int key){
int count=0;
long long sum=0;
while(root!=0){
push(root);
if(nodes[root].key<=key){
int left=nodes[root].left;
count+=nodes[left].count+nodes[root].frequency;
sum+=nodes[left].sum+1LL*nodes[root].key*nodes[root].frequency;
root=nodes[root].right;
}
else{
root=nodes[root].left;
}
}
return {count,sum};
}
long long sumMax(int small,int large){
if(small==0){
return 0;
}
push(small);
auto lower=prefix(large,nodes[small].key);
long long contribution=1LL*nodes[small].key*lower.first+nodes[large].sum-lower.second;
return contribution*nodes[small].frequency+sumMax(nodes[small].left,large)+
sumMax(nodes[small].right,large);
}
} // namespace Pacman
long long solve(const vector<int>&w,const vector<int>&S){
using namespace Pacman;
int n=(int)w.size();
nodes.clear();
nodes.reserve(2*S.size()+1);
nodes.push_back(Node());
seed=712367821;
vector<int>left(n,-1);
vector<int>right(n,-1);
vector<int>stack;
for(int i=0;i<n;++i){
int previous=-1;
while(!stack.empty()&&w[stack.back()]<w[i]){
previous=stack.back();
stack.pop_back();
}
if(!stack.empty()){
right[stack.back()]=i;
}
left[i]=previous;
stack.push_back(i);
}
int root=stack.front();
vector<int>order={root};
for(int i=0;i<(int)order.size();++i){
int vertex=order[i];
if(left[vertex]!=-1){
order.push_back(left[vertex]);
}
if(right[vertex]!=-1){
order.push_back(right[vertex]);
}
}
vector<bool>selected(n,false);
for(int endpoint:S){
selected[endpoint-1]=true;
}
vector<int>height(n);
vector<int>prefixes(n);
vector<int>suffixes(n);
long long answer=0;
for(int index=n-1;index>=0;--index){
int vertex=order[index];
int l=left[vertex];
int r=right[vertex];
int leftHeight=l==-1?0:height[l];
int rightHeight=r==-1?0:height[r];
int x=l==-1?0:suffixes[l];
int y=r==-1?0:prefixes[r];
if(selected[vertex]){
x=unite(x,create(0));
y=unite(y,create(0));
}
add(x,1);
add(y,1);
if(nodes[x].count<=nodes[y].count){
answer+=sumMax(x,y);
}
else{
answer+=sumMax(y,x);
}
x=raiseMinimum(x,rightHeight+1);
y=raiseMinimum(y,leftHeight+1);
prefixes[vertex]=unite(l==-1?0:prefixes[l],y);
suffixes[vertex]=unite(x,r==-1?0:suffixes[r]);
height[vertex]=1+max(leftHeight,rightHeight);
}
return answer;
}
#ifdef LOCAL
int main(){
int n;
int m;
cin>>n>>m;
vector<int>weights(n);
vector<int>endpoints(m);
for(int&value:weights){
cin>>value;
}
for(int&value:endpoints){
cin>>value;
}
cout<<solve(weights,endpoints)<<'\n';
}
#endif