tmp

1#include <iostream>
2#include <vector>
3#include <cstring>
4#include <set>
5#include <algorithm>
6#include <cstdio>

1using namespace std;
2const int N=1E4+7;
3int n,k,Q;
4int siz;
5int pos[N];
6int sum[N];
7int dis[N];
8bool vis[N];
9vector < pair<int,int> > edge[N];

1struct node
2{
3    int l,r;
4    int id;

1    bool operator < (node b)const
2    {
3        if (pos[l]==pos[b.l]) return r<b.r;
4        return pos[l]<pos[b.l];
5    }

1void dfs( int u,int val)
2{
3    vis[u] = true;
4    dis[u+1] = val;

1    int Siz = edge[u].size();
2    for ( int i = 0 ; i < Siz ; i ++)
3    {
4        int v = edge[u][i].first;

1        if (!vis[v])
2        {
3            dfs(v,val+edge[u][i].second);
4        }
5    }
6}
7int main()
8{

 1    freopen("in.txt","r",stdin);
 2    siz = 100;
 3    for ( int i = 0 ; i < 10000 ; i++)  pos[i] = i/siz;
 4    while (scanf("%d %d %d",&n,&k,&Q)!=EOF)
 5    {
 6        memset(vis,false,sizeof(vis));
 7        memset(dis,0,sizeof(dis));
 8        memset(sum,0,sizeof(sum));
 9        for ( int i = 1 ;i < n ; i++)
10        {
11            int u = i;
12            int v = i/k;
13            edge[u].push_back(make_pair(v,i));
14            edge[v].push_back(make_pair(u,i));
15        }

1        for ( int i = 1 ;i <= Q ; i++)
2        {
3            scanf("%d %d",&q[i].l,&q[i].r);
4            q[i].id = i;
5        }

1        dfs(0,0);
2        for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1]+dis[i];
3    }
4}