Can't find any announcement for ACL Beginner Contest, so creating this to discuss problems.

**C**

**D**

How to solve E?

I tried to make 9 segment tree for each 1 — 9 digits but couldn't find how to do update query where setting everything between l to r to zero when removing digit and to one when adding it.

You can't solve it by making 9 segment tree. In fact,one segment tree with lazy tags can perfectly solve this problem.

For D, I saw submissions and some people have just used the traditional longest subsequence approach. The only difference being they are only checking the last 100 indexes.

x=1; for(i=1;i<n;i++) { for(j=i-1;j>=0 && i-j<=100 ; j--) { if(abs(a[i]-a[j])<=k) dp[i]=max(dp[i],dp[j]+1); } x=max(x,dp[i]); } cout<<x;

why is it working???

Weak test cases.

TestcaseFor E, you can make a single segment tree, where each node holds the value of the integer % MOD. In each update, a range of leaves is changed and the rest is recomputed (the value for each node is $$$ 10^{r-(l+r)/2} \times val_{left} + val_{right}$$$ ) .

In order to make this in time, we need lazy propagation. We can only update the top-most node for which the whole range needs to be updated. The value can be calculated as a geometric sequence eg $$$ digit \times (100 + 1000 + 10000 + \dots ) $$$. The value of this sum is equal to $$$ \frac{digit \times (10^x -1 )}{9}$$$. The result for each query is the top node.

Also remember your mods and modular inverse for division by 9. My (messy) code (doesn't use ACL): here

Solution using ALC: https://atcoder.jp/contests/abl/submissions/17053342. It uses the same idea that cfalas described.

for E, I'm storing updated digits as lazy values, submission