Repeated Training Instructions
National Olympiad — National round
Submission name: chess.cpp
Problem summary
There are N puzzles and Q instructions, executed once in order. Type 1 l r solves every puzzle l through r once. Type 2 l r reexecutes earlier instructions l through r, including any nested repetitions they contain. Find how many times each puzzle is solved, modulo 1000000007.
Input
N Q followed by Q triples type l r.
Output
N puzzle counts modulo 1000000007.
Constraints
1 ≤ N,Q ≤ 100000; type-1 ranges lie in [1,N]; for instruction i, type-2 ranges satisfy 1 ≤ l ≤ r < i.
Worked example
An independently prepared example for this explanation.
Input
2 3 1 1 2 2 1 1 2 1 2
Output
4 4
Solution analysis
- Process instructions backward, since repetitions only reference earlier instructions. A reverse difference array tracks extra execution multiplicity. Every instruction also has its one original execution.
- For a type-2 instruction of multiplicity w, add w to all instruction multiplicities in [l,r] using reverse range endpoints.
- For type 1, add w to a forward difference array over puzzles. Prefix-sum this array to obtain all answers.
Why it works
When processing i backward, all later instructions that can repeat i have been processed, so its multiplicity is final. Distributing that multiplicity to its referenced operations or puzzles counts exactly all recursive executions without expansion.
Watch out. Nested repetition can grow exponentially; do not execute instructions recursively. Normalize negative differences modulo the modulus.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: When processing i backward, all later instructions that can repeat i have been processed,
// so its multiplicity is final. Distributing that multiplicity to its referenced operations or puzzles
// counts exactly all recursive executions without expansion.
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<int>t(q+1),l(q+1),r(q+1);
for(int i=1;i<=q;i++){
cin>>t[i]>>l[i]>>r[i];
}
const long long P=1000000007;
vector<long long>d(q+2),a(n+2);
auto add=[&](long long&x,long long y){
x=(x+y+P)%P;
};
long long extra=0;
for(int i=q;i>=1;i--){
add(extra,d[i]);
long long w=(extra+1)%P;
if(t[i]==2){
add(d[r[i]],w);
add(d[l[i]-1],-w);
}
else{
add(a[l[i]],w);
add(a[r[i]+1],-w);
}
}
long long sum=0;
for(int i=1;i<=n;i++){
add(sum,a[i]);
cout<<sum<<(i==n?'\n':' ');
}
}