hiho#1145 : 幻想乡的日常

描述

幻想乡一共有n处居所，编号从1到n。这些居所被n-1条边连起来，形成了一个树形的结构。

每处居所都居住着一个小精灵。每天小精灵们都会选出一个区间[l,r]，居所编号在这个区间内的小精灵一起来完成一项任务。

特别的，居所相邻的(有边相连的)两个小精灵会自发的组成一队，并且如果a和b相邻b和c相邻，那么a和c也在同一队里面。每天的任务完成之后，队伍就会解散；第二天再根据新的区间组成新的队伍。

给出每天小精灵们选出的区间，你知道每天组成的队伍数量吗？

输入

第一行两个数n和Q(1 <= n, Q <= 100000)，表示居所的数目和组队的天数。

接下来n-1行，每行两个数a和b，表示居所a和b之间有一条边。

接下来Q行，每行两个数l和r，满足1<=l<=r<=n，为该天小精灵选出的区间。

输出

输出Q行，每行一个整数表示该天队伍的数量。

样例输入

3 1

1 2

2 3

1 3

样例输出

1

草草看完题，妈妈我不会做啊。再看一遍，原来是一颗树！
那么一个区间[l,r]的答案就是r-l+1-满足l<=ui<=r&&l<=vi<=r的边的数目。
那么这就是一个二维偏序模型，离线用个Fenwich什么的就行了。

#include<cstdio>

#include<cctype>

#include<queue>

#include<stack>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int n,q,u[maxn],v[maxn],ans[maxn],e[maxn];

struct Query {

    int x,l,r,id,tp;

    bool operator < (const Query& ths) const {return x<ths.x;}

}Q[maxn];

int cmp(int x,int y) {return u[x]<u[y];}

int sumv[maxn];

int sum(int x) {

    int res=;

    for(;x;x-=x&-x) res+=sumv[x];

    return res;

}

void add(int x) {for(;x<=n;x+=x&-x) sumv[x]++;}

int main() {

    n=read();q=read();

    rep(i,,n-) u[i]=read(),v[i]=read(),e[i]=i;

    rep(i,,q) {

        int l=read(),r=read();

        Q[i*-]=(Query){r,l,r,i,};

        Q[i*]=(Query){l-,l,r,i,-};

        ans[i]=r-l+;

    }

    q<<=;int cur=;

    sort(Q+,Q+q+);sort(e+,e+n,cmp);

    rep(i,,q) {

        while(cur<n-&&u[e[cur+]]<=Q[i].x) add(v[e[++cur]]);

        ans[Q[i].id]-=Q[i].tp*(sum(Q[i].r)-sum(Q[i].l-));

    }

    rep(i,,q>>) printf("%d\n",ans[i]);

    return ;

}