Inherited Ant-City Capacities
Autumn Tournament (2014)
Submission name: ants.cpp
Problem summary
City 1 has M anthill capacities. Each later city copies any earlier city and increases all capacities in an inclusive interval [L,R] by V. Immediately report the total capacity in that new city over another interval [i,j]. Input endpoints are encoded using the previous answer, so queries must be processed online.
Input
N M, then the M original capacities. Each of the next N−1 lines gives P X Y V Z T. With previous answer S (initially 0), decode L=(X+S)%M+1, R=(Y+S)%M+1, i=(Z+S)%M+1, j=(T+S)%M+1. P identifies an earlier city.
Output
Print the capacity sum of [i,j] in each new city on its own line.
Constraints
1 ≤ N,M ≤ 100000; 0 ≤ Ai,V ≤ 100000; 0 ≤ X,Y,Z,T < M. Decoded endpoints satisfy L≤R and i≤j.
Worked example
Official sample, with spaces restored from the PDF table.
Input
4 4 3 6 7 5 1 2 3 1 0 1 2 1 2 6 2 2 1 0 2 8 0 3
Output
9 12 45
Solution analysis
- Each city is a version of the same array. Copying a whole array for every city would require O(NM) work and memory. A persistent segment tree shares unchanged nodes between versions and clones only nodes touched by an update. roots[city] points to the correct version.
- Store a segment sum at every node. Its unpushed lazy increment can be recovered as (sum−left.sum−right.sum)/segmentLength; this exact difference is the contribution not yet represented by the children. A full-cover update clones one node and increases its sum. For a partial update, recover the old increment first, clone the affected children, and recompute the sum from their sums plus the preserved increment. Recovering the tag instead of storing a second 64-bit field reduces memory, while a deque avoids vector-capacity growth overhead.
- During queries, carry additions inherited from ancestors instead of pushing them. A fully covered node contributes node.sum + inherited·segmentLength. Descending adds the recovered pending increment to the inherited amount. Thus a query never changes a node shared by other cities.
- In the sample city 2 copies [3,6,7,5], adds 1 on positions 3..4, and queries positions 1..2, producing 9. City 3 copies city 2 and obtains [3,6,14,12], reporting 12. City 4 copies city 1, not city 3, and becomes [11,14,15,5], reporting 45. The changing S must be decoded before creating each version.
Why it works
By induction each node sum equals its children’s sums plus its own pending increment over the segment. Cloning preserves every older version, while the update changes exactly the requested entries in the new version. Queries add precisely the lazy values omitted from descendant sums. Therefore every decoded query reports the required city’s capacities without affecting any other city.
Watch out. Use long long: capacities can exceed 32-bit range after many generations, and sums can reach about 10^15. Never modify shared nodes. Recover the pending increment before replacing child pointers; leaves are always fully covered and need no recovered tag. Decode all endpoints with the previous answer before replacing S.
Commented C++17 solution
An independently written complete program with standard headers.
#include<deque>
#include<iostream>
#include<vector>
using namespace std;
struct Node{
int left=0,right=0;
long long sum=0;
};
deque<Node>tree(1);
int build(int left,int right,const vector<int>&initial){
int id=tree.size();
tree.push_back(Node{});
if(left==right){
tree[id].sum=initial[left];
}
else{
int middle=(left+right)/2;
int first=build(left,middle,initial);
int second=build(middle+1,right,initial);
tree[id].left=first;
tree[id].right=second;
tree[id].sum=tree[first].sum+tree[second].sum;
}
return id;
}
int update(int old,int left,int right,int from,int to,long long value){
int id=tree.size();
tree.push_back(tree[old]);
if(from<=left&&right<=to){
tree[id].sum+=value*(right-left+1);
return id;
}
// Recover this node's unpushed addition before replacing any children.
long long pending=(tree[id].sum-tree[tree[id].left].sum-tree[tree[id].right].sum);
pending/=right-left+1;
int middle=(left+right)/2;
if(from<=middle){
int child=update(tree[id].left,left,middle,from,to,value);
tree[id].left=child;
}
if(to>middle){
int child=update(tree[id].right,middle+1,right,from,to,value);
tree[id].right=child;
}
tree[id].sum=tree[tree[id].left].sum+tree[tree[id].right].sum;
tree[id].sum+=pending*(right-left+1);
return id;
}
long long query(int id,int left,int right,int from,int to,long long inherited=0){
if(from<=left&&right<=to){
return tree[id].sum+inherited*(right-left+1);
}
long long pending=(tree[id].sum-tree[tree[id].left].sum-tree[tree[id].right].sum);
inherited+=pending/(right-left+1);
int middle=(left+right)/2;
long long answer=0;
if(from<=middle){
answer+=query(tree[id].left,left,middle,from,to,inherited);
}
if(to>middle){
answer+=query(tree[id].right,middle+1,right,from,to,inherited);
}
return answer;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>initial(m+1),roots(n+1);
for(int i=1;i<=m;i++){
cin>>initial[i];
}
roots[1]=build(1,m,initial);
long long previous=0;
for(int city=2;city<=n;city++){
int parent,x,y,value,z,t;
cin>>parent>>x>>y>>value>>z>>t;
int left=(x+previous)%m+1;
int right=(y+previous)%m+1;
int from=(z+previous)%m+1;
int to=(t+previous)%m+1;
roots[city]=update(roots[parent],1,m,left,right,value);
previous=query(roots[city],1,m,from,to);
cout<<previous<<'\n';
}
}