C. 【S】T3 分块

分块是数据结构.
分块不是数据结构.
下面是一段分块的 C++ 代码（无关部分已略去）:

void init(int n)
{
    B=sqrt(n);ans=0;
    for(int i=1;i<=n;i++)belong[i]=(i-1)/B+1;
}
void query(int l,int r)
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)++ans;
        return;
    }
    for(int i=belong[l]+1;i<belong[r];i++)++ans;
    int R=belong[l]*B,L=(belong[r]-1)*B+1;
    for(int i=L;i<=r;i++)++ans;
    for(int i=l;i<=R;i++)++ans;
}
int main()
{
    scanf("%d%d",&n,&m);init(n);
    for(int i=1,l,r;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        query(l,r);
    }
    cout<<ans<<endl;
}

会分块的同学可以跳过下面一部分.

第一行两个正整数 n, m, 含义同代码。
接下来 m 行， 每行两个正整数 l， r，含义同代码。

一行 n 个整数， 第i个整数表示块长 B = i时上述程序的运行效率（即输出的 ans 值）

【数据规模与约定】

• 对于 30% 的数据， 1 ≤ n ,m ≤ 5000
• 对于 60% 的数据， 1 ≤ n ,m ≤ 10^5
• 对于 100% 的数据， 1 ≤ n ,m ≤ 10^6