「YNOI2016」自己的发明

不换根

基本的莫队吧...

子树直接转到dfs序上。

其余部分可以见「SNOI2017」一个简单的询问。

换根

根root，查询x，分3种：

root不在x子树内，按照原来dfs序区间即可
root在x子树内且root！=x，那么就是整个序列除掉H（root的祖先，且为x儿子）对应的dfs序区间
root=x

直接将序列扩展就可以了，常数共\(8 \sqrt 2\)。

优化

若H对应区间为\([l,r]\)时，那么答案为\(cnt[1,l-1] + cnt[r+1,n]=(cnt[1,n]-cnt[l,r])\)，再乘上另一个区间。

那么可以预处理出\([1,x]\)与\([1,n]\)的答案。

这样每个询问只需要做一次\([l,r]\)和\([l1,r1]\)的查询了，常数4。

但是，实际上不没有快多少...

对2e6个询问排序，复杂度极高。

因此，可以用vector存每个左端点块对应询问，再排序。

效果明显（！

倍增过程可以去掉，每个点用vector存儿子dfn序，若将子树中某点跳到该点的某个儿子，可以在该点直接二分一下。

只快了一点...

#include <bits/stdc++.h>

#define rep(q, a, b) for (int q = a, q##_end_ = b; q <= q##_end_; ++q)

#define dep(q, a, b) for (int q = a, q##_end_ = b; q >= q##_end_; --q)

#define mem(a, b) memset(a, b, sizeof a)

#define debug(a) cerr << #a << ' ' << a << "___" << endl

using namespace std;

bool cur1;

char buf[10000000], *p1 = buf, *p2 = buf;

#define Getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++

void in(int &r) {

    static char c;

    r = 0;

    while (c = Getchar(), c < 48)

        ;

    do

        r = (r << 1) + (r << 3) + (c ^ 48);

    while (c = Getchar(), c > 47);

}

const int mn = 100005;

const int mm = 500005;

int K, n, m, vl[mn], val[mn];

int head[mn], ne[mn << 1], to[mn << 1], cnt2;

#define link(a, b) link_edge(a, b), link_edge(b, a)

#define link_edge(a, b) to[++cnt2] = b, ne[cnt2] = head[a], head[a] = cnt2

#define travel(x) for (int q(head[x]); q; q = ne[q])

int ind, dfn_l[mn], dfn_r[mn];

vector<int> son[mn];

int mp[mn];

void dfs(int f, int x) {

    ++ind, mp[ind]=x,val[ind] = vl[x], dfn_l[x] = ind;

    travel(x) if (to[q] != f) dfs(x, to[q]),son[x].push_back(dfn_l[to[q]]);

    dfn_r[x] = ind;

}

int get_high(int x, int v) {

    int l=0,r=(int)son[x].size()-1,ans=0;

    while(l<=r){

    	int mid=l+r>>1;

		if(son[x][mid]>v)r=mid-1;

		else l=mid+1,ans=mid;

	}

	return mp[son[x][ans]];

}

long long ans[mm];

struct node {

    int l, r, id;

    inline bool operator<(const node &A) const { return r < A.r; }

};

inline bool cmp(node a, node b) { return a.r > b.r; }

vector<node> an[800];

int cnt[mn], cnt1[mn];

bool mark[mm];

long long mid_ans, mid[mn];

void init() {

    dfs(0, 1);

    sort(mid + 1, mid + n + 1);

    rep(q, 1, n) val[q] = lower_bound(mid + 1, mid + n + 1, val[q]) - mid;

    rep(q, 1, n)++ cnt[val[q]];

    rep(q, 1, n) mid[q] = mid[q - 1] + cnt[val[q]];

    rep(q, 1, n)-- cnt[val[q]];

}

int find(int rt, int x) {

    if (dfn_l[rt] >= dfn_l[x] && dfn_l[rt] <= dfn_r[x])

        return get_high(x, dfn_l[rt]);

    return 0;

}

bool cur2;

int main() {

    //	cerr<<(&cur2-&cur1)/1024.0/1024<<endl;

    int td, l, r, l1, r1;

    in(n), in(m);

    rep(q, 1, n) in(vl[q]), mid[q] = vl[q];

    rep(q, 2, n) in(l), in(r), link(l, r);

    init();

    K = n / sqrt(m)*1.2 + 1;

    int rt = 1;

    rep(q, 1, m) {

        in(td);

        if (td == 1)

            in(rt);

        else {

            mark[q] = 1;

            in(l), in(l1);

            if (rt == l || rt == l1) {

                if (rt == l1)

                    swap(l, l1);

                if (rt == l1)

                    ans[q] = mid[n];

                else {

                    int at = find(rt, l1);

                    if (at)

                        ans[q] = mid[n] - (mid[dfn_r[at]] - mid[dfn_l[at] - 1]);

                    else

                        ans[q] = mid[dfn_r[l1]] - mid[dfn_l[l1] - 1];

                }

            } else {

                int at = find(rt, l), at1 = find(rt, l1);

                if (!at)

                    swap(at, at1), swap(l, l1);

                td = 1;

                if (at && !at1)

                    ans[q] = mid[dfn_r[l1]] - mid[dfn_l[l1] - 1], td = -1, l = at;

                else if (at1)

                    ans[q] = mid[n] - (mid[dfn_r[at]] - mid[dfn_l[at] - 1]) -

                             (mid[dfn_r[at1]] - mid[dfn_l[at1] - 1]),

                    l = at, l1 = at1;

                r = dfn_r[l], l = dfn_l[l];

                r1 = dfn_r[l1], l1 = dfn_l[l1];

                an[r / K].push_back({ r, r1, q * td });

                if (l > 1) {

                    an[min(r1, l - 1) / K].push_back({ min(r1, (l - 1)), max(r1, (l - 1)), -q * td });

                    if (l1 > 1)

                        an[min(l - 1, l1 - 1) / K].push_back(

                            { min(l - 1, l1 - 1), max(l - 1, l1 - 1), q * td });

                }

                if (l1 > 1)

                    an[min(r, l1 - 1) / K].push_back({ min(r, l1 - 1), max(r, l1 - 1), -q * td });

            }

        }

    }

    l = 0, r = 0;

    rep(q, 0, n / K) {

        if (q & 1)

            sort(an[q].begin(), an[q].end(), cmp);

        else

            sort(an[q].begin(), an[q].end());

        rep(w, 0, (int)an[q].size() - 1) {

            l1 = an[q][w].l, r1 = an[q][w].r;

            while (l > l1) mid_ans -= cnt1[val[l]], --cnt[val[l--]];

            while (r < r1) mid_ans += cnt[val[++r]], ++cnt1[val[r]];

            while (l < l1) mid_ans += cnt1[val[++l]], ++cnt[val[l]];

            while (r > r1) mid_ans -= cnt[val[r]], --cnt1[val[r--]];

            an[q][w].id < 0 ? ans[-an[q][w].id] -= mid_ans : ans[an[q][w].id] += mid_ans;

        }

    }

    rep(q, 1, m) if (mark[q]) printf("%lld\n", ans[q]);

    return 0;

}

巴特西

「YNOI2016」自己的发明

「YNOI2016」自己的发明

不换根

换根

优化

最新文章

热门文章