HDU 4358 Boring counting（莫队+DFS序+离散化）

时间：2023-03-08 16:10:57

Boring counting

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 2811    Accepted Submission(s): 827

Problem Description
In this problem we consider a rooted tree with N vertices. The vertices are numbered from 1 to N, and vertex 1 represents the root. There are integer weights on each vectice. Your task is to answer a list of queries, for each query, please tell us among all the vertices in the subtree rooted at vertice u, how many different kinds of weights appear exactly K times?
Input
The first line of the input contains an integer T( T<= 5 ), indicating the number of test cases.
For each test case, the first line contains two integers N and K, as described above. ( 1<= N <= 105, 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 109 )
For next N-1 lines, each line contains two vertices u and v, which is connected in the tree.
Next line is a integer Q, representing the number of queries. (1 <= Q <= 105)
For next Q lines, each with an integer u, as the root of the subtree described above.
Output
For each test case, output "Case #X:" first, X is the test number. Then output Q lines, each with a number -- the answer to each query.

Seperate each test case with an empty line.

Sample Input
1
3 1
1 2 2
1 2
1 3
3
2
1
3
Sample Output
Case #1:
1
1
1

题目链接：HDU 4358

把DFS序和莫队算法结合了起来，前两发杯具PE，如果用过DFS序配合线段树的话就大概能知道怎么做了，对于一颗子树的询问显然DFS序是很适合的，然后这样就得到了每一个点所管理的区间[L,R]，那莫队移动的时候怎么判断是否遇到了某一个原树上的节点呢？显然用先序遍历的方式来得到某一个点管理的区间，那么L这个点必定是子树树根的位置，若这个点管理的位置是[L,R]那么实际上这个子树根点的值就是arr[L]，不过由于每一个区间都是满点的，就映射成val[timeorder]=arr[u]，其中u是某次dfs时的起点。

除此之外还要判断当前减掉的数字是从k减到k-1还是k+1减到k，加上的同理，最后每一个case之间换一行，结尾不换行Orz……另外最近在玩C++11的匿名函数，在sort里随便用下玩

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=1e5+7;

struct edge

{

    int to;

    int pre;

};

struct info

{

    int l,r;

    int id,b;

};

info Q[N];

edge E[N];

int head[N],tot;

int L[N],R[N],order,val[N];

int arr[N],cnt[N],ans[N];

vector<int>vec;

void init()

{

    CLR(head,-1);

    tot=0;

    CLR(L,0);

    CLR(R,0);

    order=0;

    CLR(val,0);

    CLR(cnt,0);

    vec.clear();

}

inline void add(int s,int t)

{

    E[tot].to=t;

    E[tot].pre=head[s];

    head[s]=tot++;

}

void dfs(const int &now,const int &pre)

{

    L[now]=++order;

    val[order]=arr[now];

    for (int i=head[now]; ~i; i=E[i].pre)

    {

        int v=E[i].to;

        //if(v!=pre)

        dfs(v,now);

    }

    R[now]=order;

}

int main(void)

{

    int tcase,n,k,i,a,b,m,rt;

    scanf("%d",&tcase);

    for (int q=1; q<=tcase; ++q)

    {

        init();

        scanf("%d%d",&n,&k);

        for (i=1; i<=n; ++i)

        {

            scanf("%d",&arr[i]);

            vec.push_back(arr[i]);

        }

        sort(vec.begin(),vec.end());

        vec.erase(unique(vec.begin(),vec.end()),vec.end());

        for (i=1; i<=n; ++i)

            arr[i]=lower_bound(vec.begin(),vec.end(),arr[i])-vec.begin();

        for (i=0; i<n-1; ++i)

        {

            scanf("%d%d",&a,&b);

            add(a,b);

        }

        dfs(1,-1);

        scanf("%d",&m);

        int unit=(int)sqrt(1.0*n);

        for (i=0; i<m; ++i)

        {

            scanf("%d",&rt);

            Q[i].l=L[rt];

            Q[i].r=R[rt];

            Q[i].id=i;

            Q[i].b=Q[i].l/unit;

        }

        sort(Q,Q+m,[&](const info &x,const info &y){return (x.b==y.b&&x.r<y.r)||x.b<y.b;});

        int l=1,r=0,temp=0;

        for (i=0; i<m; ++i)

        {

            while (l<Q[i].l)

            {

                --cnt[val[l]];

                if(cnt[val[l]]==k)

                    ++temp;

                else if(cnt[val[l]]==k-1)

                    --temp;

                ++l;

            }

            while (l>Q[i].l)

            {

                --l;

                ++cnt[val[l]];

                if(cnt[val[l]]==k)

                    ++temp;

                else if(cnt[val[l]]==k+1)

                    --temp;

            }

            while (r<Q[i].r)

            {

                ++r;

                ++cnt[val[r]];

                if(cnt[val[r]]==k)

                    ++temp;

                else if(cnt[val[r]]==k+1)

                    --temp;

            }

            while (r>Q[i].r)

            {

                --cnt[val[r]];

                if(cnt[val[r]]==k-1)

                    --temp;

                else if(cnt[val[r]]==k)

                    ++temp;

                --r;

            }

            ans[Q[i].id]=temp;

        }

        printf("Case #%d:\n",q);

        for (i=0; i<m; ++i)

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

        if(q!=tcase)

            putchar('\n');

    }

    return 0;

}

相关文章