#P3526. [Poi2014]Card

    ID: 2737 传统题 5000ms 64MiB 尝试: 424 已通过: 251 难度: 6 上传者: 标签>难度分类提高动态规划动态 DP区间 DP数据结构普通线段树枚举与搜索状态编码CF2100ByDzy

[Poi2014]Card

[POI2014] Cards

题目描述

桌上从左到右排着 nn 张卡片,每张卡片的正面和反面各写有一个数。开始时所有卡片都正面朝上。魔术师 Bajtazar 要让卡片上可见的数字从左到右不下降,为此他可以翻转任意若干张卡片。

每次有一名观众交换两张卡片的位置。他们的交换依次发生。请在每次交换后判断,当前顺序下能否通过翻转卡片使可见数字不下降。判断时可以独立选择每张卡片哪一面朝上,不能改变卡片顺序。初始顺序不必满足要求。

输入格式

第一行一个整数 nn。随后 nn 行,每行两个整数 ai,bia_i,b_i,表示初始位于第 ii 个位置的卡片正面、反面的数字。

接下来一行一个整数 mm。随后 mm 行,每行两个整数 ci,dic_i,d_i,表示交换当前位于这两个位置的卡片。位置从左到右从 11 开始编号。

输出格式

输出 mm 行。在第 ii 行,若第 ii 次交换后可以实现要求,输出 TAK。否则输出 NIE。

样例 #1

4
2 5
3 4
6 3
2 7
2
3 4
1 3
NIE
TAK

第一次交换后,从第二张卡片起可见值至少为 33,第三张只能选 77,最后一张没有大于或等于 77 的一面。第二次交换后,翻转第三张卡片即可得到 2,3,5,62,3,5,6。

数据范围

2≤n≤2×1052\le n\le2\times10^5,1≤m≤1061\le m\le10^6,0≤ai,bi≤1070\le a_i,b_i\le10^7,1≤ci,di≤n1\le c_i,d_i\le n。

原赛有 30%30\% 的分值满足每张卡片两面的数字相同,另有 38%38\% 的分值满足 n≤2000n\le2000,两类测试可重叠。

原赛公开评测用例包括 n=6,m=6n=6,m=6 的小规模测试、n=7,m=9n=7,m=9 且每张卡片两面相同的测试,以及 n=200000,m=1000000n=200000,m=1000000 且每次偶数编号交换都会还原上一次交换的测试。