Fork me on GitHub

Codeforces809D

Codeforces809D题解:

题解:

  • $dp[i]$表示长度为$i$的序列最后一个数的最小值。
  • 考虑转移时加入一段区间$[l,r]$。
  • 对于最大的满足$dp[i]<l$的位置:
  • 因为$dp[i+1]>=l$,所以转移可以变为直接赋值(一定发生)。
  • 对于最大的满足$dp[j]<r$的位置:
  • 显然$dp$数组严格单调递增,即$dp[i+1]>=dp[i]+1$,所以上述转移必定发生。
  • 所以我们可以通过一颗非旋转$treap$维护$dp$数组。
  • 每次删去$dp[j+1]$这个节点,对于$dp[i+1]-dp[j]$这段$dp$区间整体$+1$并右移,再在原来的$dp[i+1]$前加入一个新的$dp[i+1]=l$的节点。
  • 这些操作都可以通过$split,merge$较为简单地实现。

代码:

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 300009
#define inf 0x3f3f3f3f
#define rd(x) (rand()%(x))
using namespace std;
int n,l[N],r[N];
struct node
{
int size,val,key,add;
node *lson,*rson;
node(int v)
{
val=v;
key=rd(100000);
if (key<=0) key+=100000;
lson=rson=NULL;
size=1;
add=0;
}
};
typedef node * pnode;
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
void down(pnode now)
{
now->val+=now->add;
if (now->lson) now->lson->add+=now->add;
if (now->rson) now->rson->add+=now->add;
now->add=0;
}
pnode merge(pnode L,pnode R)
{
if (!L) return R;
if (!R) return L;
if (L->key>R->key)
{
down(L);
L->rson=merge(L->rson,R);
return L;
}
else
{
down(R);
R->lson=merge(L,R->lson);
return R;
}
}
void split(pnode now,int val,pnode &L,pnode &R)
{
if (!now)
{
L=R=NULL;
return;
}
down(now);
if (now->val>=val)
{
split(now->lson,val,L,now->lson);
R=now;
return;
}
else
{
split(now->rson,val,now->rson,R);
L=now;
return;
}
}
int find_begin(pnode now)
{
down(now);
if (!now->lson) return now->val;
return find_begin(now->lson);
}
int get_Ans(pnode now)
{
if (!now) return 0;
down(now);
return get_Ans(now->lson)+get_Ans(now->rson)+(now->val<inf);
}
pnode root,L,M,R,rest;
int main()
{
n=read();
for (int i=1;i<=n;i++) l[i]=read(),r[i]=read();
root=new node(0);
for (int i=1;i<=n;i++)
root=merge(root,new node(i+inf));
for (int i=1;i<=n;i++)
{
split(root,l[i],L,R);
split(R,r[i],M,R);
if (M) M->add++;
int Min=find_begin(R);
split(R,Min+1,rest,R);
root=merge(L,new node(l[i]));
root=merge(root,M);
root=merge(root,R);
}
printf("%d\n",get_Ans(root)-1);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces809D

文章作者:wzf2000

发布时间:2017年12月26日 - 12:12

最后更新:2017年12月26日 - 12:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces809D/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。