tmp

 1#include <iostream>
 2#include <vector>
 3#include <cstring>
 4#include <set>
 5#include <algorithm>
 6#include <cstdio>
 7
 8using namespace std;
 9const int N=1E4+7;
10int n,k,Q;
11int siz;
12int pos[N];
13int sum[N];
14int dis[N];
15bool vis[N];
16vector < pair<int,int> > edge[N];
17
18struct node
19{
20    int l,r;
21    int id;
22
23    bool operator < (node b)const
24    {
25        if (pos[l]==pos[b.l]) return r<b.r;
26        return pos[l]<pos[b.l];
27    }
28
29
30}q[N];
31
32
33void dfs( int u,int val)
34{
35    vis[u] = true;
36    dis[u+1] = val;
37
38    int Siz = edge[u].size();
39    for ( int i = 0 ; i < Siz ; i ++)
40    {
41        int v = edge[u][i].first;
42
43        if (!vis[v])
44        {
45            dfs(v,val+edge[u][i].second);
46        }
47    }
48}
49int main()
50{
51
52    freopen("in.txt","r",stdin);
53    siz = 100;
54    for ( int i = 0 ; i < 10000 ; i++)  pos[i] = i/siz;
55    while (scanf("%d %d %d",&n,&k,&Q)!=EOF)
56    {
57        memset(vis,false,sizeof(vis));
58        memset(dis,0,sizeof(dis));
59        memset(sum,0,sizeof(sum));
60        for ( int i = 1 ;i < n ; i++)
61        {
62            int u = i;
63            int v = i/k;
64            edge[u].push_back(make_pair(v,i));
65            edge[v].push_back(make_pair(u,i));
66        }
67
68        for ( int i = 1 ;i <= Q ; i++)
69        {
70            scanf("%d %d",&q[i].l,&q[i].r);
71            q[i].id = i;
72        }
73
74        sort(q+1,q+Q+1);
75
76        dfs(0,0);
77        for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1]+dis[i];
78    }
79}