1.lpy 的魔法农场

Description

有 n 个人在 lpy 的农场里面工作。员工从 1 到 n 编号。每一个人种一种蘑菇。刚开始每一个人在自己的田地负责自己的蘑菇，这样的话公司里面就有 n 种蘑菇。

Lpy 种变异的蘑菇，变异蘑菇需要许多普通蘑菇通过魔法合成，blong(x) 表示 x 这个人所在的部门。有以下两种合成操作：

1. 魔法合成 blong(x) 和 blong(y)。 x 和 y (1≤x,y≤n)是员工编号。如果 blong(x) 和 blong(y)是种的同一种蘑菇，那么就不操作。

1. 魔法合成 blong(x),blong(x+1),...,blong(y)，x 和 y (1≤x≤y≤n)是员工编号。

有一些查询操作，查询员工 x 和 y (1≤x,y≤n)是否种同一种蘑菇。

Input

单组测试数据。

第一行有两个整数 n 和 q (1≤n≤200000, 1≤q≤500000)表示员工的数目和操作数目。接下来 q 行，每行的格式是 type x y。type∈{1，2，3}。如果 type=1 或者 type=2，那么表示第一种或者第二种魔法合成操作。如果 type=3，表示查询员工 x 和 y 是否种同一种蘑菇。

Output

对于第三种查询，如果种同一种蘑菇输出 YES，否则输出 NO。

Example

Input

8 6

3 2 5

1 2 5

3 2 5

2 4 7

2 1 2

3 1 7

Output

NO

YES

YES

题目大整容！！！

51Nod 1525 重组公司

题目来源： CodeForces

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

 Description

单组测试数据。第一行有两个整数n 和 q (1≤n≤200000, 1≤q≤500000)表示员工的数目和操作数目。接下来q行，每行的格式是type x y。type∈{1，2，3}。如果type=1 或者 type=2，那么表示第一种或者第二种合并操作。如果type=3，表示查询员工x和y是否属于同一部门。

对于第三种查询，如果属于同一部门输出YES，否则输出NO。

样例输入18 63 2 51 2 53 2 52 4 72 1 23 1 7

NOYESYES
思路：
详解博客：

xxy开讲了

考场裸写并查集，TLE！！！

上代码：

#include<cstdio>#define M 200033using namespace std;int n,q,x,y,f[M],near[M],type;int reads() {    int x=0;    char c=getchar();    while(c<‘0‘||c>‘9‘) c=getchar();    while(c>=‘0‘&& c<=‘9‘) x=x*10+c-‘0‘,c=getchar();    return x;}inline int find(int x) {    if(f[x]!=x) f[x]=find(f[x]);    return f[x];}inline int unionn(int a,int b) {    int x1=find(a), x2=find(b);    if(x1!=x2)        f[x1]=x2;}inline void qj() {    int step,r=y;    while(r>=x && (step=near[r])>=x) {        //unionn(r,step);        f[find(step)]=f[find(r)];        near[r]=near[step];        //t在i前面，i与t合并后，i到t之间的全都合并了，i之前的第一个没合并的就是t之前的第一个没合并的        r=step;    }}int main() {    n=reads();    q=reads();    for(int i=1; i<=n; i++) f[i]=i,near[i]=i-1;    for(int i=1; i<=q; i++) {        type=reads();        x=reads();y=reads();        if(type == 1) unionn(x,y);        if(type == 2) qj();        if(type == 3) {            if(find(x) == find(y))    puts("YES\n");            else puts("NO\n");        }    }    return 0;}

2.Hkd 打 magic mouse

Description

　　hkd 最近迷上了打 magic mouse 游戏。

　　magic mouse 游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多magic mouse 来，然后等 hkd 用榔头去敲击这些 magic mouse，每个 magic mouse 被敲击后，将会增加相应的游戏分值。问题是这些 magic mouse 不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个 magic mouse 冒出后停留的时间可能是不同的，而且每个 magic mouse 被敲击后增加的游戏分值也可能是不同，为了胜出，hkd 就必须根据每个 magic mouse 的特性，有选择地尽快敲击一些 magic mouse，使得总的得分最大。

　　这个极具挑战性的游戏 hkd 特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个 magic mouse 所需要的耗时是 1 秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个 magic mouse 冒出来后停留的时间都是固定的，而且他记录了每个 magic mouse被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序地选择敲击不同的 magic mouse，保证每次得到最大的总分值。

Input

输入包含 3 行，第一行包含一个整数 n（1<=n<=100）表示有 n 个 magic mouse 从地上冒出来，第二行 n 个用空格分隔的整数表示每个 magic mouse 冒出后停留的时间，第三行 n 个用空格分隔的整数表示每个 magic mouse 被敲击后会增加的分值（<=100）。每行中第 i 个数都表示第 i 个 magic mouse 的信息。

Output

输出只有一行一个整数，表示 hkd 所能获得的最大游戏总分值。

Example

Input 

5

5 3 6 1 4

7 9 2 1 5

Output

24

题目大整容！！！

#include<iostream>#include<cstdio>#include<algorithm>#define M 200033using namespace std;int f[M],n,ans;struct Mouse{    int t,v;}mouse[M];int find(int x) {    if(f[x] != x) f[x]=find(f[x]);    return f[x];}int cmp(Mouse a,Mouse b) {    return a.v > b.v;}int main() {    scanf("%d",&n);    for(int i=1; i<=n; i++)    scanf("%d",&mouse[i].t);    for(int i=1; i<=n; i++) scanf("%d",&mouse[i].v);    sort(mouse+1,mouse+n+1,cmp);    for(int i=1; i<=100; i++) f[i]=i;    for(int i=1; i<=n; i++) {        int no = find(mouse[i].t);        if(no) {            f[no]=f[no-1];            ans+=mouse[i].v;        }    }    printf("%d",ans);    return 0;}

3.上白泽慧音

Description

　　在幻想乡，上白泽慧音是以性格怪异闻名的生物学家。他养了 N 只猴子。有一天，这些被月光刺激，发生了变异。猴子们进行了一次奇怪的活动。第一只猴子的尾巴挂在树上，剩下的 N-1 只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子。现在给出这 N 只猴子抓与被抓的信息，并且在某个时刻可能某只猴子抓累了，会放掉它其中一只手的猴子，导致某些猴子落地。上白泽慧音想知道每只猴子落地的时间。

Input

第一行两个数 N、M，表示有 N 只猴子，并且总时间为 M-1。接下来 N 行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，若果是-1，表示该猴子那只手没抓其他猴子。再接下来 M 行，按时间顺序给出了一些猴子放手的信息，第 1+N+i 行表示第 i-1 时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子编号，后者表示其放的是哪只手，1 左 2 右。

Output

共输出 N 行，第 i 行表示第 i 只猴子掉落的时刻，若第 i 只猴子岛 M-1 时刻以后还没掉落，就输出-1。

Example

Input 

3 2

-1 3

3 -1

1 2

1 2

3 1

Output

-1

1

1

Hint