$O(\log N)$

1. 逗号出现规则：

   • 数字位数小于4：没有逗号
   • 数字位数4-6：有1个逗号
   • 数字位数7-9：有2个逗号
   • 以此类推，每增加3位，逗号数加1

2. 数学建模：

   • 将数字按位数分组处理
   • 对于每组数字，计算该组内每个数字的逗号数
   • 累加所有数字的逗号数

3. 分组处理：

   • 第1组：1-999（无逗号）
   • 第2组：1000-999999（每个数1个逗号）
   • 第3组：1000000-999999999（每个数2个逗号）
   • 第k组：$10^{3(k-1)}$ 到 $10^{3k}-1$（每个数k-1个逗号）

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    long long power = 1000; // 从四位数开始有逗号
    int cnt = 1; // 四位数到六位数有1个逗号
    
    // 计算每个范围的数字贡献的逗号数量
    while (n >= power) {
        long long lower = power; // 当前范围的下限
        long long upper = power * 1000 - 1; // 当前范围的上限
        
        // 如果上限超过n，则取n作为实际上限
        if (upper > n) {
            upper = n;
        }
        
        // 该范围内的数字个数乘以每个数字的逗号数
        ans += (upper - lower + 1) * cnt;
        
        // 进入下一个范围（多三位数字，多一个逗号）
        power *= 1000;
        cnt++;
    }
    
    cout << ans;
    return 0;
}