BZOJ3526 - [Poi2014]Card

BZOJ3526 - Click Here

  

Description

  有n张卡片在桌上一字排开,每张卡片上有两个数,第i张卡片上,正面的数为a[i],反面的数为b[i]。现在,有m个熊孩子来破坏你的卡片了!

  第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。

  每个熊孩子捣乱后,你都需要判断,通过任意翻转卡片(把正面变为反面或把反面变成正面,但不能改变卡片的位置),能否让卡片正面上的数从左到右单调不降。

  

Input

  第一行一个n。

  接下来n行,每行两个数a[i],b[i]。

  接下来一行一个m。

  接下来m行,每行两个数c[i],d[i]。

  n≤200000,m≤1000000,0≤a[i],b[i]≤10000000,1≤c[i],d[i]≤n.

  

Output

  m行,每行对应一个答案。如果能成功,输出TAK,否则输出NIE。

  

Solution

  这么明显的线段树分治我居然没看出来QAQ。

  

  对于一个区间$[L,R]$,如果$[L,mid]$能够升序排列,$[mid,R]$也能够升序排列,那么$[L,R]$能够升序排列。

  因此,若没有交换操作,是能够利用分治思想判断能否升序排列的(当然贪心也可以,但不能扩展)。

  

  现在考虑交换卡牌$x$和卡牌$y$,此时包含$x$或包含$y$的区间内信息被更新了,其余区间则不受影响。换言之,需要使用某种数据结构,能够实现存储和更新,这个显然是线段树的作用。

  具体做法就是对每个节点存储4个信息,分别表示左端点换与不换/右端点换与不换的信息,然后线段树分治更新答案。

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang