BZOJ 3526 Card

发表于 | 更新于

Link

为什么这么简单的做法还是想不出来

Solution

先考虑暴力： 修改一个位置之后，从这个数字开始向后递推能否构成单调数列。每次是O(n)O(n)的，但是可以看出，做了很多无用功，因为每次转移的行为都是一样的，只要知道起点的值后面的值就都知道了。 考虑一下每个单调数列的来源，是i−1i-1的单调数列加上一个满足不降且最小的数字。修改了一个位置之后，不能O(1)O(1)知道对于它后面的某个数字，它所转移过来的那个位置还是不是合法，也就是说，不能知道 的传递路径是否被阻断，也不能知道是否还有别的路径。 但是可以发现，对于一段整体的数列，开头的两个数字是否合法就直接决定了后面所有点是否合法，即知道了 的起始点，就能固定 的路径。 这样就可以看出子结构了，进一步想一下，发现可以用线段树维护。

Tips

根据暴力的无用功，寻找问题子结构，寻找合法的状态和转移，从而套数据结构维护。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include "lucida"
using std::swap;
using std::pair;
const int MAXN=200000+11;
namespace _SegTree_ {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		pair<int,int> st,ed;
		Node(pair<int,int> v):st(v),ed(v) {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
			return Me++;
		}
		void Modify(pair<int,int> v) {
			st=ed=v;
		}
		void Up() {
			st=son[0]->st;
			if(son[0]->ed.first<=son[1]->st.first)
				ed.first=son[1]->ed.first;
			else if(son[0]->ed.first<=son[1]->st.second)
				ed.first=son[1]->ed.second;
			else
				ed.first=INT_MAX;
			if(son[0]->ed.second<=son[1]->st.first)
				ed.second=son[1]->ed.first;
			else if(son[0]->ed.second<=son[1]->st.second)
				ed.second=son[1]->ed.second;
			else
				ed.second=INT_MAX;
		}
	};
	struct SegTree {
	//private:
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R,pair<int,int> arr[]) {
			pos=new Node(arr[L]);
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,arr);
				Build(pos->son[1],Mid+1,R,arr);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,pair<int,int> v) {
			if(L==R)
				pos->Modify(v);//st=pos->ed=v;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal,v);
				else 
					Edit(pos->son[1],Mid+1,R,goal,v);
				pos->Up();
			}
		}
	//public:
		SegTree(int L,int R,pair<int,int> arr[]):L(L),R(R) {
			Build(root,L,R,arr);
		}
		Node *&operator ->() {
			return root;
		}
		void Modify(int pos,pair<int,int> v) {
			Edit(root,L,R,pos,v);
		}
	};
}using _SegTree_::SegTree;
int main() {
//	freopen("input","r",stdin);
	static pair<int,int> cd[MAXN];
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		is>>cd[i].first>>cd[i].second;
		if(cd[i].first>cd[i].second)
			swap(cd[i].first,cd[i].second);
	}
	SegTree seg(1,n,cd);
	int m;is>>m;
	for(int i=1;i<=m;++i) {
		int x,y;
		is>>x>>y;
		swap(cd[x],cd[y]);
		seg.Modify(x,cd[x]);
		seg.Modify(y,cd[y]);
		os<<((seg->ed.first!=INT_MAX || seg->ed.second!=INT_MAX)?"TAK":"NIE")<<'\n';
	}
	return 0;
}