MENU

飘雪圣域

20181106A.pdf

因为是树,所以联通块数量=未被覆盖点数-未被覆盖边数。求边数即二维偏序,求所有边中两端点均在区间内的有多少,一维排序一维树状数组。

莫队被卡成50分,真惨 (xiao si)

#include<cstdio>
#include<utility>
#include<algorithm>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("O2")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
using namespace std;
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("icekingdom.in", "r", stdin), freopen("icekingdom.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), q = ip.rd<int>(), c[200001], ans[200001];
struct abcd { int u, v, idx; }e[200001], query[200001];
inline bool operator<(const abcd&a, const abcd&b) { return a.v < b.v; }
inline void assign(int x, int v) {
    for (; x <= n; x += x & -x)c[x] += v;
}
inline int find(int x) {
    int ret = 0;
    for (; x; x -= x & -x)ret += c[x];
    return ret;
}
int main() {
    for (int i = 1; i < n; ++i) {
        e[i].u = ip.rd<int>(), e[i].v = ip.rd<int>(), e[i].idx = i;
        if (e[i].u > e[i].v)swap(e[i].u, e[i].v);
    }
    sort(e + 1, e + n);
    for (int i = 1; i <= q; ++i)query[i].u = ip.rd<int>(), query[i].v = ip.rd<int>(), query[i].idx = i;
    sort(query + 1, query + q + 1);
    for (int i = 1, j = 1; i <= q; ++i) {
        while (query[i].v >= e[j].v && j < n)assign(e[j++].u, 1);
        ans[query[i].idx] = query[i].v - query[i].u + 1 - find(query[i].v) + find(query[i].u - 1);
    }
    for (int i = 1; i <= q; ++i)ip.print(ans[i]), ip.putc('\n');
}
Leave a Comment

captcha
请输入验证码