# agc015E - Mr.Aoki Incubator(dp)

## Sol

\$s[i]\$为其前缀和

```#include<bits/stdc++.h>
#define Pair pair<int, int>
#define fi first
#define se second
#define MP(x, y) make_pair(x, y)
#define LL long long
using namespace std;
const int MAXN = 1e6, mod = 1e9 + 7;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, date[MAXN], L[MAXN], R[MAXN], f[MAXN];
struct Node {
int x, v, id, l, r;
bool operator < (const Node &rhs) const {
return v > rhs.v;
}
}a[MAXN];
int comp(const Node &a, const Node &b) {
return a.r == b.r ? a.l < b.l : a.r < b.r;
}
void GetL(int *op) {
vector<Pair> q;
for(int i = 1; i <= N; i++) q.push_back(MP(a[i].x, a[i].id));
sort(q.begin(), q.end());
for(int i = 1; i <= N; i++) {
while(!q.empty()) {
if(a[i].x <= q.back().fi) op[q.back().se] = i, q.pop_back();
else break;
}
}
}
void GetR(int *op) {
vector<Pair> q;
for(int i = 1; i <= N; i++) q.push_back(MP(a[i].x, a[i].id));
sort(q.begin(), q.end());
reverse(q.begin(), q.end());
for(int i = N; i >= 1; i--) {
while(!q.empty()) {
if(a[i].x >= q.back().fi) op[q.back().se] = i, q.pop_back();
else break;
}
}
}
int dp() {
for(int i = 1; i <= N; i++) a[i].r = N - L[i] + 1, a[i].l = N - R[i] + 1;
sort(a + 1, a + N + 1, comp);
//for(int i = 1; i <= N; i++) printf("%d %d\n", a[i].l, a[i].r);
static int s[MAXN], f[MAXN];//f[i]：前i只猫覆盖所有区间的方案
int ans = 0;
for(int i = 1, j = 1; i <= N; i++) {
while(a[j].r < a[i].l - 1) j++;
f[i] = (s[i - 1] + mod - s[j - 1] ) % mod;
if(a[i].l == 1) f[i]++;
if(a[i].r == N) (ans += f[i]) %= mod;
s[i] = (s[i - 1] + f[i]) % mod;
}
return ans % mod;
}
main() {
for(int i = 1; i <= N; i++) a[i].x = read(), a[i].v = read(), a[i].id = i, date[i] = a[i].v;
sort(date + 1, date + N + 1);
int num = unique(date + 1, date + N + 1) - date - 1;
for(int i = 1; i <= N; i++) a[i].v = lower_bound(date + 1, date + num + 1, a[i].v) - date;
sort(a + 1, a + N + 1);
GetL(L); GetR(R);
//for(int i = 1; i <= N; i++) printf("%d %d\n", L[i], R[i]);
printf("%d", dp() % mod);

}```

0 条评论

• ### ZROJ#397. 【18提高7】模仿游戏(爆搜)

读完题目后不难发现，每次约束的条件相当于是\(b[((x[i] + i) % N + (i / N) % N) % N] = y[i]\)

• ### SDOI 2018二轮题解(除Day2T1)

然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉，烤前感觉也没啥可复习的，就补一补去年二轮的题吧。

• ### 亚马逊面试题

如下所示的Map中，0代表海水，1代表岛屿，其中每一个岛屿与其八领域的区间的小岛能相连组成岛屿群。写代码，统计Map中岛屿个数。 /* Q1....

• ### SDOI 2018二轮题解(除Day2T1)

然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉，烤前感觉也没啥可复习的，就补一补去年二轮的题吧。

• ### Java改善性能小技巧

不管有多少经验，都会被问到一些优化建议，从代码层面到数据库层面，下面介绍一些改善性能的小技巧

• ### 快速傅里叶变换FFT& 数论变换NTT

0（000）2（010）4（100）6（110），1（001）3（011）5（101）7（111）