Description

Input

第一行一个正整数。

之后行描述集合。第一个数表示集合中元素的个数，之后给出集合中的元素。

之后一行一个正整数。

之后行每行描述一个询问。格式与之前相同。

Output

对于每个询问，在单独的一行内输出答案。

Sample Input

7

0

1 1

1 1

1 2

2 2 3

0

2 2 6

3

2 2 3

2 3 5

2 4 5

Sample Output

3

3

4

HINT

 

对于100% 的数据，1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

 

Source

 

题解：

　　Violet 0的题果然不水，好题啊。

 

　　我们观察A集合，如果把Ai中的数考虑为i的父亲的话（后缀也可以，看个人喜好），那么我们可以发现这张图是一个DAG，且Bi这个集合里面的数都是i在图中的灾难点，也就是说Bi是i的灾难点的集合。于是我们可以把灾难树建出来，然后对于每个询问就变成了求一些点的灾难点的集合的并的大小。我们把询问离线之后可以利用dfs序的先后关系处理掉可能重复的情况。

 

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6   7 using namespace std;  8   9 const int maxn=200010; 10  11 int q,en,n,depth[maxn],f[maxn][25],last_q[maxn],ans[maxn]; 12  13 vector
            
              query[maxn],ed[maxn],set_a[maxn]; 14 15 const int BUF_SIZE = 1000; 16 char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; 17 18 #define PTR_NEXT() \ 19 { \ 20 buf_s ++; \ 21 if (buf_s == buf_t) \ 22 { \ 23 buf_s = buf; \ 24 buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \ 25 } \ 26 } 27 28 #define readint(_n_) \ 29 { \ 30 while (*buf_s != '-' && !isdigit(*buf_s)) \ 31 PTR_NEXT(); \ 32 bool register _nega_ = false; \ 33 if (*buf_s == '-') \ 34 { \ 35 _nega_ = true; \ 36 PTR_NEXT(); \ 37 } \ 38 int register _x_ = 0; \ 39 while (isdigit(*buf_s)) \ 40 { \ 41 _x_ = _x_ * 10 + *buf_s - '0'; \ 42 PTR_NEXT(); \ 43 } \ 44 if (_nega_) \ 45 _x_ = -_x_; \ 46 (_n_) = (_x_); \ 47 } 48 49 50 void add_edge(int s,int e) 51 { 52 ed[s].push_back(e); 53 } 54 55 inline int get_lca(int p1,int p2) 56 { 57 if (depth[p1]
             
              >=1; 64 now++; 65 } 66 now=0; 67 while (p1!=p2) 68 { 69 if (f[p1][now]!=f[p2][now] || (f[p1][now]==f[p2][now] && now==0)) 70 { 71 p1=f[p1][now]; 72 p2=f[p2][now]; 73 now++; 74 } 75 else now--; 76 } 77 return p1; 78 } 79 80 void dfs(int now) 81 { 82 int sz=query[now].size(); 83 for (int a=0;a