Hello Codeforces. Our TST is in less than a week. If you follow my account here, you probably have noticed that my performance has gotten really bad last few months. I haven't solved ABCD since December. In OI I suddenly got much worse and got lower rankings locally. While in January I could've said that I'll easily make it to IOI I can't even say I have a chance now. I don't know what exactly is wrong. I just don't feel like solving problems anymore. I just don't feel like thinking and I've lost any enjoyment in solving a problem. Would you call this just a burnout (a bit long one)? Do you think there's a way to clear my mind this week to do better? I just want my performance back. If someone faced such a problem before what did you do? What do you think I should try to do? I'm really desperate. Any advice is helpful.

Sometimes I encounter a type of range queries that I don't know how to do using segment tree, so I use a merge sort tree instead. It can answer queries in $$$O(log^2 n ) $$$. I decided to share this because it can be useful to many in contests. First, we know that a node in a segment tree stores the answer for a range of length $$$2^x$$$ for some $$$x$$$, but we can also store in it all the elements in the range sorted in a vector (using merge sort algo) or set or whatever. Here I am going to give a few examples how we can use this to our advantage.

Problem 1: Static Count of Lesser Elements range queries.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has three integers $$$l_i , r_i , x_i$$$. The answer for this query is how many $$$a_j$$$ such that $$$l_i \le j \le r_i$$$ and $$$a_j < x$$$.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N];
vector<int> seg[4*N+5];
//build merge sort tree
void build(int node,int l,int r){
    //if range length is 1 there's only one element to add and no children
    if (l==r){
        seg[node].push_back(a[l]);
        return;
    }int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    int i=0,j=0;
    // use two pointers to merge the two vectors in O(r-l+1)
    while (i<seg[node*2].size() && j<seg[node*2+1].size()){
        if (seg[node*2][i]<seg[node*2+1][j]) seg[node].push_back(seg[node*2][i++]);
        else seg[node].push_back(seg[node*2+1][j++]);
    }
    while (i<seg[node*2].size()) seg[node].push_back(seg[node*2][i++]);
    while (j<seg[node*2+1].size()) seg[node].push_back(seg[node*2+1][j++]);
    return;
}
//query
int query(int node,int l,int r,int lx,int rx,int x){
    //if outside -> 0
    if (l>rx || r<lx) return 0;
    //if inside do binary search
    if (l>=lx && r<=rx){
        int L=0,R=seg[node].size()-1,mid,ans=0;
        while (L<=R){
            mid=(L+R)/2;
            if (seg[node][mid]<x){
                ans=mid+1;
                L=mid+1;
            }else R=mid-1;
        }return ans;
    }
    int mid=(l+r)/2;
    return query(node*2,l,mid,lx,rx,x)+query(node*2+1,mid+1,r,lx,rx,x);
}
int32 main(){
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while (q--){
        int l,r,x;
        cin>>l>>r>>x;
        cout<<query(1,1,n,l,r,x)<<endl;
    }
    return 0;
}

Problem 2: Dynamic Lower Bound problem.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has an integer $$$t_i$$$, describing the type of query.

• If $$$t_i = 0$$$ then you are given two other integers, $$$idx_i$$$ and $$$x_i$$$, meaning that we should make $$$a_{idx} = x_i$$$.

• If $$$t_i = 1$$$ then you are given three integers $$$l_i, r_i, x_i$$$. You should answer with the smallest value $$$v$$$ in the range $$$[l_i,r_i]$$$ such that $$$x \le v$$$. If there is none, print -1.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N];
multiset<int> seg[4*N+5];
void build(int node,int l,int r){
    if (l==r){
        seg[node].insert(a[l]);
        return;
    }int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    for (int i=l;i<=r;i++) seg[node].insert(a[i]);
    return;
}
void edit(int node,int l,int r,int idx,int val){
    if (l==r){
        seg[node].erase(a[idx]);
        seg[node].insert(val);
        return;
    }int mid=(l+r)/2;
    if (idx<=mid) edit(node*2,l,mid,idx,val);
    else edit(node*2+1,mid+1,r,idx,val);
    seg[node].erase(a[idx]);
    seg[node].insert(val);
    return;
}
int query(int node,int l,int r,int lx,int rx,int x){
    if (l>rx || r<lx) return INT_MAX;
    if (l>=lx && r<=rx){
        auto it=seg[node].lower_bound(x);
        if (it==seg[node].end()) return INT_MAX;
        return *it;
    }int mid=(l+r)/2;
    return min(query(node*2,l,mid,lx,rx,x),query(node*2+1,mid+1,r,lx,rx,x));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while (q--){
        bool t;cin>>t;
        if (!t){
            int idx,val;
            cin>>idx>>val;
            edit(1,1,n,idx,val);
            a[idx]=val;
            continue;
        }int l,r,x;cin>>l>>r>>x;
        int y=query(1,1,n,l,r,x);
        if (y==INT_MAX) cout<<-1<<endl;
        else cout<<y<<endl;
    }
    return 0;
}

Final notes

There are many other things that you can do using technique. You can even solve the dynamic version of the first problem using indexed_set. However you should use this only when you're desperate because it's really slow. Yes it's $$$O(nlog^2n)$$$ but the constant factor is very high because it's segment tree + sets. If you have intereseting problems to add to the blog, or you notice some mistake please say in the comments. Good luck everyone!

Problems

SPOJ — KQUERY

CF EDU Segment Tree Step 3 C

CF — 816B

Next contest should be 879. Please fix. Edit: fixed.

Troll accounts are nearly unescapable. No matter what restrictions are made, there will always be troll accounts, but please at least decrease spam. Look at recent actions now, it's all the same account. I think that having a time limit between blogs, like you can post another blog only 1 hour after another is good. What do you people think?

Don't use sqrt because precision issues

Also here is implementation to find floor(sqrt(x))

#define int long long
int sqrt(int x){
    int l=1,r=1e9+5,ans=0,mid;
    while (l<=r){
        mid=(l+r)/2;
        if (mid*mid<=x){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }return ans;
}

It seems std::sqrt works fine in C++17 though. Also sqrtl seems to give correct results

Hello Codeforces! So my friend Haidora thought that in problem C yesterday it asked for the number of beautiful sets of all lengths (lol) and we were talking now about a solution for this problem and came up with an $$$O(rlogr)$$$ DP solution.

Formal Statement

A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).

You are given two integers $$$l$$$ and $$$r$$$ . Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$: You have to print their number modulo $$$998244353$$$

Solution

Let $$$dp_x$$$ be the number of beautiful sets we can build such that the minimum number in these sets is $$$x$$$. Now, how do we find $$$dp_x$$$? Let's iterate through all numbers $$$i$$$ such that $$$xi \le r$$$, which means that we'll go through all multiples of $$$x$$$ as long as they are less than $$$r$$$. Now let's add their answers to our $$$dp_x$$$. Formally:

$$$dp_x = 1 + \sum_{i=2}^{xi \le r} dp_{xi} $$$ Now our answer would be summing them all up, because we want all sets, so for all possible minimums we want to know the number of sets possible using it. Formally: $$$ans = \sum_{i=l}^{i \le r} dp_{i} $$$

Note that the $$$1+$$$ is there because choosing $$$x$$$ alone in a set is also valid.

Time complexity

Why is it $$$O(rlogr)$$$? For each $$$x$$$ you are iterating through all number $$$xi \le r$$$ which is $$$r \sum_{i=l}^{i \le r} dp_{1/i} $$$ which is close to $$$O(rlogr)$$$ Thanks to NaimSS for correcting my time complexity.

Implementation

I used recursive DP:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=998244353;
int dp[N],l,r;
int rec(int x){
    if (x>r) return 0;
    if (dp[x]) return dp[x];
    dp[x]=1;
    for (int i=2;i*x<=r;i++) dp[x]=(dp[x]+rec(x*i))%M;
    return dp[x];
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>l>>r;
    int ans=0;
    for (int i=l;i<=r;i++) ans=(ans+rec(i))%M;
    cout<<ans<<endl;
    return 0;
}

This code runs less than 100ms on C++20(64) when $$$l = 1$$$ and $$$r = 10^6$$$ , and less than 2000ms when $$$l = 1$$$ and $$$r = 10^7$$$. Tried on Codeforces custom test.

Iterative DP by Farsh_LE:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=998244353;
int dp[N],l,r;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>l>>r;
    int ans=0;
    for (int x=r;x>=l;x--){
        dp[x]=1;
        for (int i=2;x*i<=r;i++) dp[x]=(dp[x]+dp[x*i])%M;
        ans=(ans+dp[x])%M;
    }cout<<ans<<endl;
    return 0;
}

Nearly same speed as recursive, a bit faster though.

Final Notes

This is my first blog of this kind, so feel free to share your opinions as it will help me and others for the future. Also, please point out any mistakes you find. And I have a few questions: Could there be a faster solution? Also if there is an iterative DP solution please share it, because I couldn't find any way to do it iteratively. Thanks!

Last year a contest was held on Valentine's Day. Why isn't is the same this year? Do you expect us to go on dates? Please give us Valentine's Day contest :(

Many people use the normal upper_bound() function, which is slow (at worst case O(n)) and get TLE. When you are using a set/multiset/map, use containername.upper_bound() This function uses Binary Search which runs at O(logn) time. Please be careful next time. This is only a reminder because I'm seeing a lot of people get TLE because of this.

Hello Codeforces. I'm trying to add my wallet in magic place but it's asking for a secret code and I don't know how to find it. I'm using tonkeeper app. If anyone knows how to find it please help me. Thanks in advance!

Hello CodeForces, I want to solve problems of Innopolis University Open Olympiad previous years, but I only found archives pre 2019. Does anyone know where I can find problems of 2020 and 2021? Thanks in advance. Update: Theo830 shared this link.

Hello everyone. So Global Rounds are made every 2 months and last one was in June, but as I can see there isn't going to be a Global Round this month. Why is that? Is it postponed to September or something?

Happy Eid Codeforces! I hope you have positive delta and a happy week