qp
by lihaoda @ 2023-10-21 10:32:33
输入的 $l,r$ 应该加上个数，不然会越界
```cpp
#include <bits/stdc++.h>
#define N 150005
#define M 3000005
#define lowbit(x) (x & (-x))
using namespace std;
int n, dp[N], ans;
int tre[M], maxx;
struct node {
int l, r, w;
bool operator <(const node &x)const {
if (l == x.l) {
return r < x.r;
}
return l < x.l;
}
} a[N];
inline void read(int &x) {
char ch = x = 0;
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar();
}
return ;
}
inline void upd(int x, int w) {
while (x <= maxx) {
if (tre[x] < w) {
tre[x] = w;
} else {
break;
}
x += lowbit(x);
}
return ;
}
inline int que(int x) {
int res = 0;
while (x) {
res = max(res, tre[x]);
x -= lowbit(x);
}
return res;
}
int main() {
read(n);
for (int i = 1; i <= n; i++) {
read(a[i].l), read(a[i].r),a[i].l++,a[i].r++;
a[i].w = a[i].r - a[i].l + 1;
maxx = max(maxx, a[i].r);
}
sort(a + 1, a + 1 + n);
ans = dp[1] = a[1].w;
upd(a[1].r, dp[1]);
for (int i = 2; i <= n; i++) {
dp[i] = a[i].w + que(a[i].l - 1);
upd(a[i].r, dp[i]);
ans = max(ans, dp[i]);
}
printf("%d", ans);
return 0;
}
```
by XOOR @ 2023-10-24 17:27:06
因为查询的时候是 $a[i].l-1$ 数据范围从 $0$ 开始的，容易减成负数 @[WA_6X版](/user/373905)
by XOOR @ 2023-10-24 17:29:36
@[_Tyrue_](/user/450743) 原来是这样嘛？AC了，已关，谢谢大佬
by WA_6X版 @ 2023-10-25 11:36:45
@[WA_6X版](/user/373905) 因为我也这么挂了一次/cf
by XOOR @ 2023-10-25 13:44:22
@[_Tyrue_](/user/450743) 啊这
by WA_6X版 @ 2023-10-29 11:45:41