皮卡丘的梦想

电玩女神 2022-06-08 14:47 302阅读 0赞

皮卡丘的梦想  
Time Limit: 1000MS Memory Limit: 2560KB  
Submit Statistic Discuss  
Problem Description

一天，一只住在 501 的皮卡丘决定发奋学习，成为像 LeiQ 一样的巨巨，于是他向镇上的贤者金桔请教如何才能进化成一只雷丘。  
金桔告诉他需要进化石才能进化，并给了他一个地图，地图上有 n 个小镇，并且标注了每个小镇上可收集的进化石。  
但是皮卡丘拿到地图就蒙圈了，他可不知道自己到底需要哪种进化石，而且由于经费有限，他只能去某几个相邻的小镇，所以他机智地找到了善于编程的你，询问你这些镇上可收集的进化石有哪些，然后再自己决定行程。  
Input

首先输入一个整数 T (1 <= T <= 10)，代表有 T 组数据。  
每组数据的第一行输入一个整数 n (1 <= n <= 100000)，代表有 n 个小镇。  
接下来的 n 行表示第 1 个到第 n 个的小镇的信息。每行先输入一个整数 m (0 <= m <= 30)，代表这个小镇上进化石的种类数，紧接着输入 m 个整数，代表进化石的种类编号（编号从 1 开始，不超过 30）。  
之后的一行输入一个整数 q (1 <= q <= 25000)，代表皮卡丘有 q 次询问。  
接下来的 q 行每行输入两个整数 l, r (1 <= l <= r <= n)，表示他想询问从第 l 个到第 r 个小镇上可收集的进化石有哪几种。  
Output

对于每组输入，首先输出一行 “Case T:”，表示当前是第几组数据。  
接下来对于每一次询问，按编号升序输出所有可收集的进化石。如果没有进化石可收集，则输出一个小豪的百分号 “%”（不要问我为什么，出题就是这么任性）。  
Example Input

1  
3  
2 3 10  
3 1 2 4  
0  
3  
1 2  
2 3  
3 3  
Example Output

Case 1:  
1 2 3 4 10  
1 2 4  
%  
Hint

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <stack>
    using namespace std;
    
    struct node
    {
        unsigned long long val;
    }tree[400000];
    
    void bulid(int root,int left,int right)
    {
        if(right==left)
        {
            tree[root].val = 0;
            return ;
        }
        int mid = (left+right)/2;
        int lc = (root<<1) + 1;
        int rc = (root<<1) + 2;
        bulid(lc,left,mid);
        bulid(rc,mid+1,right);
    }
    
    void updata(int root,int left,int right,int pos,unsigned long long val)
    {
        if(left==right)
        {
            tree[root].val = tree[root].val | val;
            return ;
        }
        int mid = (left+right)/2;
        int lc = (root<<1) + 1;
        int rc = (root<<1) + 2;
        if(pos<=mid)
            updata(lc,left,mid,pos,val);
        else
            updata(rc,mid+1,right,pos,val);
        tree[root].val = tree[lc].val | tree[rc].val;
    }
    
    unsigned long long query(int root,int left,int right,int qleft,int qright)
    {
        unsigned long long res = 0;
        if(qleft<=left&&qright>=right)
            return tree[root].val;
        int mid = (left+right)/2;
        int lc = (root<<1) + 1;
        int rc = (root<<1) + 2;
        if(mid>=qleft)
        {
            res = res | query(lc,left,mid,qleft,qright);
        }
        if(mid<qright)
        {
            res = res | query(rc,mid+1,right,qleft,qright);
        }
        return res;
    }
    
    
    int main()
    {
        unsigned long long Y = 1;
        int t;
        scanf("%d",&t);
        for(int k = 1;k<=t;k++)
        {
            printf("Case %d:\n",k);
            int n;
            scanf("%d",&n);
            bulid(0,0,n-1);
            for(int j = 0;j<n;j++)
            {
                unsigned long long data = 0;
                int m;
                scanf("%d",&m);
                for(int i = 0;i<m;i++)
                {
                    unsigned long long each;
                    scanf("%lld",&each);
                    data = data | (Y<<(each-1));
                }
                updata(0,0,n-1,j,data);
            }
            int q;
            scanf("%d",&q);
            for(int j = 0;j<q;j++)
            {
                int x,y;
                scanf("%d %d",&x,&y);
                unsigned long long res = query(0,0,n-1,x-1,y-1);
                if(res)
                {
                    int flag = 1;
                    for(int i = 0;i<30;i++)
                    {
                        if(res&(Y<<i))
                        {
                            if(flag)
                            {
                                flag = 0;
                                printf("%d",i+1);
                            }
                            else
                                printf(" %d",i+1);
                        }
                    }
                    printf("\n");
                }
                else
                    printf("%%\n");
            }
        }
    }
    
    /*
    1
    3
    3
    1 3 5
    3
    2 4 6
    2
    1 6
    100
    */