×

计蒜客

  1. 题库
  2. The Fake Fake Friends
  3. 问答
  • 6.67%
  • 65536K

互膜作为一种机房活动,在增进友谊、锻炼表达能力的同时,也能给蒟蒻以充分表达自己对神犇景仰之情的机会,可谓一举多得。

同时,它也是附中洗脑团队的日常。

每一天,$n$ 个 OIer 都会围成一圈,为方便起见,我们不妨按顺时针为他们编号 $1$~$n$。

每个 OIer 都有一个 01 属性,这个属性代表着他们是蒟蒻还是神犇。在这里,为了简化问题,我们并不区分日常写挂的蒟蒻和什么都不会的蒟蒻,我们也不区分数论之神和 DSM(Data Structure Master)。

从$1$号 OIer 开始,每个人都有一次机会,在环上钦定一个区间,并对这个区间进行 orz。再一次,为了简化问题,这个区间可以包含该 OIer 本身。鉴于蒟蒻的膜拜会使人变神,而神犇乱膜会使人变成蒟蒻,这个区间内被 orz 过的 OIer 属性都会变成发起 orz 的 OIer 属性xor$1$。$1$~$n$ 号OIer依次膜过人后,互膜环节便宣告结束,大家也就回到各自的位置,继续一天的 OI 生活。

S 是这些 OIer 中的一员。在这一次互膜的时候,他的编号为 $s$。S 已经预先得知了其他 $n-1$ 个 OIer 接下来要 orz 的区间,而他所想做的,就是选择一个区间,使互膜结束后神犇的数量最多,因为这表示这次互膜很成功。但他还要出题,所以希望你,OI 界的希望,帮他算一下方案。

输入格式

第一行两个正整数 $n,s$,表示 OIer 的个数和 S 的编号。

第二行 n 个整数$a_1…a_n$,表示每个OIer初始的属性。$0$ 代表蒟蒻,而 $1$ 代表神犇。

接下来 $n-1$ 行,每行 $2$ 个整数 $li,ri$,表示从 $1$ 号 OIer 开始,除了S外每个 OIer 的 orz 区间。该区间即为从 $l_i$ 顺时针转到 $r_i$(包括 $l_i,r_i$)经过的所有人。注意 $l_i$ 可以大于 $r_i$。

输出格式

第一行一个整数,表明互膜结束后最大的神犇数。

第二行两个整数 $l,r$,表明从 $l$ 顺时针转到 $r$ 为 S 的最优方案。若有多解,输出任意一组。注意 S 必须选择一个合法区间而不能不参加活动。

数据范围

对于 $10\%$ 的数据,$n \le 80$。

对于 $30\%$ 的数据,$n\le250$。

对于 $50\%$ 的数据,$n\le3000$。

另有 $10\%$ 的数据,$s=n$ 。

对于 $70\%$ 的数据,$n\le10^5$。

对于 $100\%$ 的数据,$1\le n\le2*10^6,1\le s,l_i,r_i\le n,a_i\in[0,1]$。

提示

本题输入数据规模较大,请选手使用较为快速的读入方式。

给出读入优化模板:

inline int rd() {
    int ret;
    char ch;
    for(; (ch = getchar() - '0') < 0 || ch > 9;);
    for(ret = ch; (ch = getchar() - '0') >= 0 && ch <= 9; ret=(ret << 3) + (ret << 1) + ch);
    return ret;
}

本题答案不唯一,符合要求的答案均正确

样例输入

4 3
1 1 0 1
4 1
4 4
1 2

样例输出

3
3 3

想挑战这道题吗

  • main.c