HIHO1145 【幻想乡的日常】题解

 因为这些点在树上,因此区间数等于点数-边数

离线下来按照r排序树状数组维护l即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int nQposc[100005], ans[100005];
struct node
{
    int id;
    int l;
    int r;
    bool operator<(const node &bbconst
    {
        return r < bb.r;
    }
a[100005], b[100005];
int lowbit(int x)
{
    return x & -x;
}
void add(int xint val)
{
    while (x <= n)
    {
        c[x] += val;
        x += lowbit(x);
    }
    return;
}
int ask(int x)
{
    int num = 0;
    while (x >= 1)
    {
        num += c[x];
        x -= lowbit(x);
    }
    return num;
}
int main()
{
    scanf("%d%d", &n, &Q);
    for (int i = 1i < n; ++i)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
        if (a[i].l > a[i].r)
            swap(a[i].la[i].r);
    }
    sort(a + 1a + n);
    for (int i = 1i <= Q; ++i)
    {
        b[i].id = i;
        scanf("%d%d", &b[i].l, &b[i].r);
    }
    sort(b + 1b + Q + 1);
    for (int i = 1i <= Q; ++i)
    {
        while (pos < n - 1 && a[pos + 1].r <= b[i].r)
        {
            ++pos;
            add(a[pos].l1);
        }
        ans[b[i].id] = b[i].r - b[i].l + 1 - (ask(n) - ask(b[i].l - 1));
    }
    for (int i = 1i <= Q; ++i)
        printf("%d\n"ans[i]);
    return 0;
}

评论

此博客中的热门博文

min-max反演