Gym - 101848C Object-Oriented Programming (树链剖分+线段树+动态开点)

时间:2022-01-15 23:41:00
C. Object-Oriented Programming
time limit per test

3.0 s

memory limit per test

1024 MB

input

standard input

output

standard output

Functions overriding, is a well-known concept, when we are using inheritance in Object-Oriented Programming (OOP). For those who are not familiar with OOP, I will recall a few things to perhaps refresh your memory.

  • A class has at most one parent class. When they do, they are called subclasses inheriting their parents. Subclasses also inherit all the functions declared in their parent classes, and also, all the functions inherited by parents' parents, and so on. Here, we refer to the ancestors as superclasses.
  • Subclasses can, of course, declare new functions, and also override the functions already declared in superclasses. This is called overriding.
  • When an instance of the subclass calls a function, it will first try to find the code in its own class body, and then its parent, and then its parent's parent, etc., until it reaches the root (the superclass of all classes). If the function has still not been found yet, a runtime error will be raised.

As you might have guessed, we are interested in finding out in which class the function is written when some instance of a particular class calls it.

Input

The input is in the following format:

Gym - 101848C Object-Oriented Programming (树链剖分+线段树+动态开点)

n (2 ≤ n ≤ 105) is the number of classes. Classes are numbered from 1 to npi (1 ≤ pi ≤ i - 1) is the parent class of class i. Class 1 is the root class, superclass of all classes. It has no parent.

ti denotes the number of functions written in class i, including both new functions and overriding functions. Then follows ai1, ai2, ..., aiti a list of these functions. Functions are also denoted using positive integers. It's guaranteed that every number will appear at most once in one list. 1 ≤ aij ≤ 106, 0 ≤ ti ≤ 106, Gym - 101848C Object-Oriented Programming (树链剖分+线段树+动态开点).

q (1 ≤ q ≤ 105) is the query number. Then follows q queries. uiri (1 ≤ ui ≤ n, 1 ≤ ri ≤ 106) is the i-th query, asking when an instance of class ui calls function ri, in which class is this function written?

Output

For each query, print answer. If it is illegal, that is, a "runtime error" is raised, then output  - 1.

Example
input
Copy
5
1 2 3 3
2 2 1
0
2 5 2
2 4 5
1 5
4
3 4
5 2
4 5
1 3
output
Copy
-1
3
4
-1
Note

The sample is equivalent to the following Java code.

class Class1 {
void function2() { System.out.println("1"); }
void function1() { System.out.println("1"); }
} class Class2 extends Class1 { } class Class3 extends Class2 {
void function5() { System.out.println("3"); }
void function2() { System.out.println("3"); }
} class Class4 extends Class3 {
void function4() { System.out.println("4"); }
void function5() { System.out.println("4"); }
} class Class5 extends Class3 {
void function5() { System.out.println("5"); }
} void test() {
new Class3().function4();
new Class5().function2();
new Class4().function5();
new Class1().function3();
}

Some of the tests in the raw problem package have been removed due to the "Maximal summary testset file size exceeded" error on Codeforces.

题意:

题面说的很复杂,但是我们可以将他转换成一个比较直白的模型:

给你n个点,依此输入n-1条边,形成一棵树。然后依此输入n行,依此表示1-n这几个点每个点含有哪几个值(一个点可以包含多个值,也可以不包含值,如果一条路径上,后面的点包含的值如果和前面点包含的值相同,在询问时会覆盖前面的),然后q个询问,每个询问输入两个值:u,r;询问u到根节点路径上哪个点包含r这个值(相同的值后面点覆盖前面点),输出这个点的坐标。

思路:

我们对每个值建一棵树,将包含这些值的点存进树里,点i就将树上点i标为i,然后询问u,r时,我们只要询问第r棵树上1-u上最大值就好了(用个链剖+线段树就好了),建树的话直接动态开点就行了不会超内存,这样的话这道题就很好写了。。

如果想到了思路就很好写,之前想歪了思路,debug了半天都没有得到想要的值。

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int Max = 3e7+;
const int M = 2e6+;
const int MM = 2e6;
int ls[Max],rs[Max],sum[Max],root[Max],idx,ed[Max];
struct node{
int to,next;
}e[M];
int cnt,cnt1,n;
int son[M],siz[M],head[M],fa[M],top[M],dep[M],tid[M],mx[M],rk[M];
void add(int u,int v){
e[++cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
} void dfs1(int u,int faz,int deep){
dep[u] = deep;
fa[u] = faz;
siz[u] = ;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v == faz) continue;
dfs1(v,u,deep+);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]||son[u] == -)
son[u] = v;
}
} void dfs2(int u,int t){
top[u] = t;
mx[u] = cnt1;
tid[u] = cnt1;
rk[cnt1] = u;
cnt1++;
if(son[u] == -) return ;
dfs2(son[u],t),mx[u] = max(mx[u],mx[son[u]]);
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v != fa[u]&&v != son[u])
dfs2(v,v),mx[u] = max(mx[u],mx[v]);
}
} void update(int &k,int l,int r,int p,int num){
if(!k){
k = ++idx;
sum[k] = num;
}
sum[k] = max(sum[k],num);
if(l == r)
return ;
int m = (l + r) >> ;
if(p <= m) update(ls[k],l,m,p,num);
else update(rs[k],m+,r,p,num);
} int query(int k,int L,int R,int l,int r){
if(!k) return ;
if(L <= l&&R >= r){
return sum[k];
}
int m = (l + r) >> ;
int ans = ;
if(L <= m) ans = max(ans,query(ls[k],L,R,l,m));
if(R > m) ans = max(ans,query(rs[k],L,R,m+,r));
return ans;
} int solve(int x,int y,int rt){
int fx = top[x],fy = top[y];
int ans = ;
while(fx != fy){
if(dep[fx] < dep[fy]) swap(x,y),swap(fx,fy);
ans = max(ans,query(root[rt],tid[fx],tid[x],,MM));
x = fa[fx]; fx = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
ans = max(ans,query(root[rt],tid[x],tid[y],,MM));
return ans;
} int main()
{
int x,k,q,t,n;
idx = ;
cnt1 = ; cnt = ;
root[] = ,sum[] = ;
scanf("%d",&n);
memset(son,-,sizeof(son));
for(int i = ;i <= n;i ++){
scanf("%d",&x);
add(x,i); add(i,x);
}
dfs1(,,); dfs2(,);
for(int i = ;i <= n;i ++){
scanf("%d",&t);
for(int j = ;j <= t;j ++){
scanf("%d",&x);
update(root[x],,MM,tid[i],i);
}
}
scanf("%d",&q);
while(q--){
scanf("%d %d",&k,&x);
//cout<<"kk: "<<k<<" "<<root[k]<<endl;
int num = solve(,k,x);
if(num == ) num = -;
printf("%d\n",num);
}
return ;
}

Gym - 101848C Object-Oriented Programming (树链剖分+线段树+动态开点)的更多相关文章

  1. 【BZOJ-2325】道馆之战 树链剖分 &plus; 线段树

    2325: [ZJOI2011]道馆之战 Time Limit: 40 Sec  Memory Limit: 256 MBSubmit: 1153  Solved: 421[Submit][Statu ...

  2. 【BZOJ2243】&lbrack;SDOI2011&rsqb;染色 树链剖分&plus;线段树

    [BZOJ2243][SDOI2011]染色 Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的 ...

  3. BZOJ2243 &lpar;树链剖分&plus;线段树)

    Problem 染色(BZOJ2243) 题目大意 给定一颗树,每个节点上有一种颜色. 要求支持两种操作: 操作1:将a->b上所有点染成一种颜色. 操作2:询问a->b上的颜色段数量. ...

  4. POJ3237 &lpar;树链剖分&plus;线段树)

    Problem Tree (POJ3237) 题目大意 给定一颗树,有边权. 要求支持三种操作: 操作一:更改某条边的权值. 操作二:将某条路径上的边权取反. 操作三:询问某条路径上的最大权值. 解题 ...

  5. bzoj4034 (树链剖分&plus;线段树)

    Problem T2 (bzoj4034 HAOI2015) 题目大意 给定一颗树,1为根节点,要求支持三种操作. 操作 1 :把某个节点 x 的点权增加 a . 操作 2 :把某个节点 x 为根的子 ...

  6. HDU4897 (树链剖分&plus;线段树)

    Problem Little Devil I (HDU4897) 题目大意 给定一棵树,每条边的颜色为黑或白,起始时均为白. 支持3种操作: 操作1:将a->b的路径中的所有边的颜色翻转. 操作 ...

  7. Aizu&Tab;2450 Do use segment tree 树链剖分&plus;线段树

    Do use segment tree Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.bnuoj.com/v3/problem_show ...

  8. 【POJ3237】Tree(树链剖分&plus;线段树)

    Description You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edg ...

  9. HDU 2460 Network(双连通&plus;树链剖分&plus;线段树)

    HDU 2460 Network 题目链接 题意:给定一个无向图,问每次增加一条边,问个图中还剩多少桥 思路:先双连通缩点,然后形成一棵树,每次增加一条边,相当于询问这两点路径上有多少条边,这个用树链 ...

  10. bzoj2243&lbrack;SDOI2011&rsqb;染色 树链剖分&plus;线段树

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 9012  Solved: 3375[Submit][Status ...

随机推荐

  1. 使用 python 获取 Linux 系统信息&lpar;通过dmidecode命令&rpar;

    通过 dmidecode 命令可以获取到 Linux 系统的包括 BIOS. CPU.内存等系统的硬件信息,这里使用 python 代码来通过调用 dmidecode 命令来获取 Linux 必要的系 ...

  2. HDU 3966 Aragorn&&num;39&semi;s Story 树链剖分&plus;树状数组 或 树链剖分&plus;线段树

    HDU 3966 Aragorn's Story 先把树剖成链,然后用树状数组维护: 讲真,研究了好久,还是没明白 树状数组这样实现"区间更新+单点查询"的原理... 神奇... ...

  3. SQL Server中的锁的简单学习

    简介 在SQL Server中,每一个查询都会找到最短路径实现自己的目标.如果数据库只接受一个连接一次只执行一个查询.那么查询当然是要多快好省的完成工作.但对于大多数数据库来说是需要同时处理多个查询的 ...

  4. POJ1637 Sightseeing tour(判定混合图欧拉回路)

    有向连通图存在欧拉回路的充要条件是所有点入度=出度. 首先随便给定所有无向边一个方向(不妨直接是u->v方向),记录所有点的度(记:度=入度-出度). 这时如果有点的度不等于0,那么就不存在欧拉 ...

  5. ionic 实现自动升级APP

    最近做移动商城开发,需要一个自动升级APP的功能,在网上搜罗很多,发现有的是下载APK,有的在我这服务无法实现,由于时间原因,都被PASS了,最后找到了一个热更新插件,经过半天的调试,可以使用,很欣喜 ...

  6. C&plus;&plus;求1&excl;到n&excl;的和

    题目内容:求1!+2!+3!+4!+……+n!的结果. 输入描述:输入不多于50个正整数的数据n(1<=n<=12). 输出描述:对于每个n,输出计算结果.每个计算结果应单独占一行. 参考 ...

  7. android基本的数据库创建和使用

    android的四大组件中就有Content Provider,对其他应用,提供自己的数据,所以,一般情况下,android应用不需要提供content provider. 1.  简单的数据库表单字 ...

  8. POJ2031Building a Space Station &lpar;最小生成树之prim&rpar;

    Problem Description You are a member of the space station engineering team, and are assigned a task ...

  9. Cobbler批量部署CentOS

    简介 Cobbler是一个快速网络安装linux的服务,而且在经过调整也可以支持网络安装windows.该工具使用python开发,小巧轻便(才15k行python代码),使用简单的命令即可完成PXE ...

  10. 文件锁FileLock

    1.文件锁的定义 FileLock是文件锁,进程锁,用于进程间并发,控制不同程序(JVM)对同一文件的并发访问. FileLock是java 1.4 版本后出现的一个类,它可以通过对一个可写文件(w) ...