# 牛客编程巅峰赛S2第4场 - 钻石&王者

## A 牛牛摆玩偶

• 如果是左端点，这一个就放在这里
• 如果是右端点，这一个就放在

```#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 玩偶数
* @param m int整型 区间数
* @param intervals Interval类vector 表示区间
* @return int整型
*/
int doll(int n, int m, vector<Interval>& intervals) {
// write code here
LL L = 1, R = 1e10, mid, ans = 0;
set<pii> mp;
for(Interval x: intervals) {
mp.insert(mk(x.start, 1));
mp.insert(mk(x.end, 2));
}
auto check = [&](int mid) {
LL L = -1e11;
int cnt = 0;
while(cnt < n) {
auto p = mp.lower_bound(mk(L + mid, 0));
if(p == mp.end()) return false;
if((*p).se == 1) {
++ cnt;
L = (*p).fi;
}else if((*p).se == 2) ++ cnt, L = L + mid;
}
return cnt == n;
};
while(L <= R) {
mid = (L + R) >> 1;
if(check(mid)) ans = mid, L = mid + 1;
else R = mid - 1;
}
return (int)ans;
}
};```

## B 交叉乘

```#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 多次求交叉乘
* @param a int整型vector a1,a2,...,an
* @param query int整型vector l1,r1,l2,r2,...,lq,rq
* @return int整型vector
*/
vector<int> getSum(vector<int>& a, vector<int>& query) {
// write code here
int n = a.si***t)query.size() / 2;
vector<LL> suf(n + 1, 0), pre(n, 0), pre2(n, 0);
per(i, n - 1, 0) {
suf[i] = suf[i + 1] + a[i], suf[i] %= mod;
if(i != n - 1) pre[i] = a[i] * suf[i + 1] % mod;
}
rep(i, 1, n) pre[i] = (pre[i] + pre[i - 1]) % mod;
pre2[0] = a[0];
rep(i, 1, n) pre2[i] = (pre2[i - 1] + a[i]) % mod;
vector<int> ans, q(query);
while(m --) {
int R = q.back() - 1; q.pop_back();
int L = q.back() - 1; q.pop_back();
LL res = pre[R] - (L == 0? 0: pre[L - 1]);
res %= mod;
LL res2 = pre2[R] - (L == 0? 0: pre2[L - 1]);
res2 %= mod;
LL hou = 0;
if(R != n - 1) hou = suf[R + 1];
res = (res - res2 * hou % mod) % mod;
res = (res + mod) % mod;
ans.push_back((int)res);
}
reverse(all(ans));
return ans;
}
};```