【LOJ3009】【BZOJ2090】【POI2010】Monotonicity 2

Author Avatar
q234rty 2月 10, 2019

DP+树状数组"即可"。

相信很多人看到这道题的第一反应和窝一样：这不是水题吗，只要记 f(i) 表示下标以 i 结尾的最长合法子序列长度，转移树状数组优化一下就行了。

还有一些人可能觉得这道题需要在状态中记录长度 \bmod k ，于是得到了优秀的 O(nk\log n) 或 O(nk) 做法。

第一反应觉得这道题是水题之后可能会觉得不对劲，DP需要最优子结构，而这个DP看起来并不满足呀。

然而，这个DP确实是满足最优子结构的，为什么呢？

（网上的题解大都没写证明，neither_nor写了证明但窝看不懂毒瘤jcy，于是窝决定写一下用谷歌翻译看波兰文官方题解（在P152）的成果）

就是要证下标以 i 结尾的最长合法子序列，一定可以由某个下标以 j<i 结尾的最长合法子序列接上 i 得到。

不失一般性，设下标以 n 结尾的最长合法子序列第一个不满足这个条件，再设 m 为这个子序列的上一个下标。

设 b_1,b_2,\cdots,b_{f(m)} 为下标以 m 结尾的最长合法子序列对应的下标序列，显然 b_{f(m)}=m ，设 k=f(n) 。

因为 n 继承的不是 m 的最优解，所以 k-1<f(m) ，即 f(m)\geq k 。

讨论：

  • a_m=a_n ，这时 b_1,b_2,\cdots,b_{f(m)-1},n 长度为 f(m) \geq k ，显然为一个不会更劣的解。
  • a_m<a_n ，这就是说 s_{k-1}=``<" ，继续讨论：
    • a_{b_{k-1}}<a_n ，那么 b_1,b_2,\cdots,b_{k-1},n 长度为 k ，不会更劣。
    • a_{b_{k-1}}\geq a_n ，我们有 a_{b_{k-1}}<a_{b_k} ，但是 a_{b_{k-1}}\geq a_n>a_m ，也即一定存在一个 w\geq k 满足 a_{b_w}>a_{b_{w+1}} ，也即 s_{w}=``>" ，我们取第一个这样的 w ，于是 \forall i \in [k,w), a_{b_i}\leq a_{b_{i+1}} ，又 a_{b_{k-1}}<a_{b_k} ，于是 a_{b_w}>a_{b_{k-1}}\geq a_n ，于是 b_1,b_2,\cdots,b_{w},n 长度为 w+1>k ，更优。
  • a_m>a_n ，同理得证。

这样就证完啦。

使用两个树状数组分别维护下一个是大于和小于的情况，等于直接用数组维护。

时间复杂度 O(n\log n)

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int,int> pii;
  5. const int MAXSIZE=10000020;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. 	#ifdef LOCAL
  11. 		freopen("3009.txt","r",stdin);
  12. 	#endif
  13. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. 	bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. 	bool isneg;
  19. 	int val=0;
  20. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. 	bufpos+=(isneg=buf[bufpos]=='-');
  22. 	for(;isdigit(buf[bufpos]);bufpos++)
  23. 		val=val*10+buf[bufpos]-'0';
  24. 	return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. 	int val=0;
  29. 	for(;!isdigit(buf[bufpos]);bufpos++);
  30. 	for(;isdigit(buf[bufpos]);bufpos++)
  31. 		val=val*10+buf[bufpos]-'0';
  32. 	return val;
  33. }
  34. #endif
  35. char readchar(){
  36. 	for(;isspace(buf[bufpos]);bufpos++);
  37. 	return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. 	int cur=0;
  41. 	for(;isspace(buf[bufpos]);bufpos++);
  42. 	for(;!isspace(buf[bufpos]);bufpos++)
  43. 		s[cur++]=buf[bufpos];
  44. 	s[cur]='\0';
  45. 	return cur;
  46. }
  47. const int maxn=1000002;
  48. inline void tense(pii &x,pii y){
  49. 	if (x<y)
  50. 		x=y;
  51. }
  52. struct bit{
  53. 	int n;
  54. 	pii t[maxn];
  55. 	void add(int p,pii v){
  56. 		for(;p<=n;p+=p&-p)
  57. 			tense(t[p],v);
  58. 	}
  59. 	pii query(int p){
  60. 		pii ans;
  61. 		for(;p;p-=p&-p)
  62. 			tense(ans,t[p]);
  63. 		return ans;
  64. 	}
  65. }b1;
  66. struct tib{
  67. 	int n;
  68. 	pii t[maxn];
  69. 	void add(int p,pii v){
  70. 		for(;p;p-=p&-p)
  71. 			tense(t[p],v);
  72. 	}
  73. 	pii query(int p){
  74. 		pii ans;
  75. 		for(;p<=n;p+=p&-p)
  76. 			tense(ans,t[p]);
  77. 		return ans;
  78. 	}
  79. }b2;
  80. inline pii inc(pii x){
  81. 	x.first++;
  82. 	return x;
  83. }
  84. int a[maxn],dp[maxn],lst[maxn],stk[maxn];
  85. pii qwq[maxn];
  86. char s[maxn];
  87. int main(){
  88. 	init();
  89. 	int n=readint(),k=readint();
  90. 	for(int i=1;i<=n;i++)
  91. 		a[i]=readint();
  92. 	for(int i=1;i<=k;i++)
  93. 		s[i]=readchar();
  94. 	b1.n=b2.n=maxn-1;
  95. 	int ans=0;
  96. 	for(int i=1;i<=n;i++){
  97. 		pii lol;
  98. 		tense(lol,inc(b1.query(a[i]-1)));
  99. 		tense(lol,inc(b2.query(a[i]+1)));
  100. 		tense(lol,inc(qwq[a[i]]));
  101. 		dp[i]=lol.first,lst[i]=lol.second;
  102. 		// printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
  103. 		lol.second=i;
  104. 		char now=s[(dp[i]-1)%k+1];
  105. 		if (now=='=')
  106. 			tense(qwq[a[i]],lol);
  107. 		else if (now=='<')
  108. 			b1.add(a[i],lol);
  109. 		else b2.add(a[i],lol);
  110. 		// printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
  111. 		if (dp[i]>dp[ans])
  112. 			ans=i;
  113. 	}
  114. 	printf("%d\n",dp[ans]);
  115. 	int cur=0;
  116. 	while(ans){
  117. 		stk[++cur]=ans;
  118. 		ans=lst[ans];
  119. 	}
  120. 	for(int i=cur;i;i--)
  121. 		printf("%d ",a[stk[i]]);
  122. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2019/02/10/loj3009/

隐藏