tmp

Posted by 111qqz on Wednesday, April 13, 2016

TOC

#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <algorithm>
#include <cstdio>

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

struct node
{
    int l,r;
    int id;

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


}q[N];


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

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

        if (!vis[v])
        {
            dfs(v,val+edge[u][i].second);
        }
    }
}
int main()
{

    freopen("in.txt","r",stdin);
    siz = 100;
    for ( int i = 0 ; i < 10000 ; i++)  pos[i] = i/siz;
    while (scanf("%d %d %d",&n,&k,&Q)!=EOF)
    {
        memset(vis,false,sizeof(vis));
        memset(dis,0,sizeof(dis));
        memset(sum,0,sizeof(sum));
        for ( int i = 1 ;i < n ; i++)
        {
            int u = i;
            int v = i/k;
            edge[u].push_back(make_pair(v,i));
            edge[v].push_back(make_pair(u,i));
        }

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

        sort(q+1,q+Q+1);

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