1906

yxᴄ
yxc的小迷妹

White55kai

zwling

miraitowazzr
SugarT
X-7D1C11010

Olivia_

### 一个点的贡献值为其作为最大值的左边界和右边界 对应的所有子数组的乘积

class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
模拟 确实妙
// int n = nums.size();
// int ans = 0, m0 = -1, m1 = -1;
// for(int i = 0; i < n; i ++){
//     if(nums[i] > right) m0 = i;
//     if(nums[i] >= left) m1 = i;
//     ans += m1 - m0;
// }
// return ans;
stack<int> stk;
int n = nums.size();
vector<int> l(n, -1), r(n, n);
for(int i = 0; i < n; i ++){
while(stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
if(stk.size()) l[i] = stk.top();
stk.push(i);
}
while(stk.size()) stk.pop();
for(int i = n - 1; i >= 0; i --){
while(stk.size() && nums[stk.top()] < nums[i]) stk.pop();
if(stk.size()) r[i] = stk.top();
stk.push(i);
}
int ans = 0;
for(int i = 0; i < n; i ++){
if(nums[i] >= left && nums[i] <= right)
ans += (i - l[i]) * (r[i] - i);
}
return ans;
}
};


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N][N];
int m, n;
int dis[N];
int level[N];
bool st[N];

int D(int down, int up){
memset(dis, 0x3f, sizeof dis);
memset(st, 0, sizeof st);
dis[0] = 0;
for(int i = 1; i <= n + 1; i ++){
int t = -1;
for(int j = 0; j <= n; j ++){
if(!st[j] && (t == -1 || dis[t] > dis[j]))
t = j;
}
st[t] = true;
for(int j = 0; j <= n; j ++){
if(!st[j] && level[j] >= down && level[j] <= up)
dis[j] = min(dis[j], dis[t] + w[t][j]);
}
}
return dis[1];
}
int main (){
scanf("%d%d", &m, &n);
memset(w, 0x3f, sizeof w);
for(int i = 0; i <= n; i ++) w[i][i] = 0;
for(int i = 1; i <= n; i ++){
int price, lev, cnt;
scanf("%d%d%d", &price, &lev, &cnt);
level[i] = lev;
w[0][i] = min(w[0][i], price);
while(cnt --){
int id, cost;
scanf("%d%d", &id, &cost);
w[id][i] = min(w[id][i], cost);
}
}
int res = 0x3f3f3f3f;
for(int i = level[1] - m; i <= level[1]; i ++) res = min(res, D(i, i + m));

cout << res << endl;
return 0;
}


1 <= n <= 10^9
2 <= a, b <= 4 * 10 ^ 4

### 其中能整除 a 和 b 的个数可能发生重复计算 需要去除的个数为 n / lcm(a, b);

class Solution {
public:
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int nthMagicalNumber(int n, int a, int b) {
long long l = min(a, b), r = (long long)min(a, b) * n;
int mod = 1e9 + 7;
int lcm = a * b / gcd(a, b);
while(l < r)
{
long long mid =  (l + r) / 2;
if(mid / a + mid / b - mid / lcm >= n ) r = mid;
else l = mid + 1;
}
return l % mod;
}
};


- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。

class Solution {
public:
long long ans;
int h[100010], ne[200010], e[200010], idx;
int d;
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa){
int s = 1;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa) continue;
int t = dfs(j, u);
ans += (t + d - 1) / d; // 向下取整
s += t;
}
return s;
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
d = seats;
memset(h, -1, sizeof h);
}
dfs(0, -1);
return ans;
}
};


4721 排队

n 个小朋友排成一排，从左到右依次编号为 1∼n。

6
10 8 5 3 50 45

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int,int> PII;

const int N = 100010;
int f[N], h[N];

int main ()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> h[i];

f[n + 1] = 2e9;
for(int i = n; i >= 1; i --) f[i] = min(f[i + 1], h[i]);

for(int i = 1; i <= n; i ++){
int l = i, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(h[i] > f[mid]) l = mid;
else r = mid - 1;
}
printf("%d ", r - i - 1);
}
return 0;
}
//树状数组 + 离散化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
vector<int> alls;
int w[N];
int n;
int ans[N];
int tr[N];

int find(int x){
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
void update(int x, int c){
for(int i = x; i <= alls.size(); i += i & -i)  tr[i] = max(tr[i], c);
}
int query(int x){
int mx= 0;
for(int i = x; i >= 1; i -= i & -i) mx = max(tr[i], mx);

return mx;
}
int main (){
cin >> n;
for(int i = 1; i <= n; i ++){
scanf("%d", &w[i]);
alls.push_back(w[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for(int i = n; i >= 1; i --){
int x = find(w[i]);
update(x, i);
x = query(x - 1);
if(x < i) ans[i] = -1;
else ans[i] = x - i - 1;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';

return 0;
}

//stack
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int w[N];
int n;
int stk[N];
int ans[N];

int main (){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];

int top = 0;
for(int i = n; i >= 1; i --){
if(!top || w[i] <= w[stk[top]]) ans[i] = -1;

else{
int l = 1, r = top;
while(l < r){
int mid = l + r >> 1;
if(w[stk[mid]] < w[i]) r = mid;
else l = mid + 1;
}
ans[i] = stk[l] - i - 1;
}
if(!top || w[i] < w[stk[top]]) stk[++top] = i;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';

return 0;
}


#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int,int> PII;

const int N = 510;
bool g[N][N];
int dis[N];
int q[N];
int m, n;
int stop[N];

void bfs(){
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
int hh = 0, tt = -1;
q[++tt] = 1;
while(hh <= tt){
int t = q[hh ++];
for(int i = 1; i <= n; i ++){
if(g[t][i] && dis[i] > dis[t] + 1){
dis[i] = dis[t] + 1;
q[++tt] = i;
}
}
}
}
int main ()
{
cin >> m >> n;
string s;
getline(cin, s);
while(m --){
getline(cin, s);
stringstream ssin;
ssin << s;
int cnt = 0, p;
while(ssin >> p) stop[cnt ++] = p;
for(int i = 0; i < cnt; i ++){
for(int j = i + 1; j < cnt; j ++){
g[stop[i]][stop[j]] = true;
}
}
}
bfs();
if(dis[n] == 0x3f3f3f3f) puts("NO");
else cout << max(dis[n] - 1, 0) << endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;
int n, t;
int w[N];
int f[N];
int q[N];

bool check(int mid){
int hh = 0, tt = 0;
memset(f, 0, sizeof f);
memset(q, 0, sizeof q);
for(int i = 1; i <= n; i ++){
if(hh <= tt && i - mid  > q[hh]) hh ++;
f[i] = f[q[hh]] + w[i];
while(hh <= tt && f[q[tt]] >= f[i]) tt --;
q[++tt] = i;
}
int res = 2e9;
for(int i = n - mid + 1; i <= n; i ++) res = min(res, f[i]);
return res <= t;
}
int main (){
cin >> n >> t;
for(int i = 1; i <= n; i ++) cin >> w[i];

int l = 0, r = n;
while(l < r){
int mid = l + r >> 1;
if(check(mid + 1)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}


/*
f[i] = min(f[j]) + w[i],    i - k  <= j <= i - 1    区间长度为 k
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
int n, k;
int w[N];
int f[N];
int q[N];

int main (){
cin >> n >> k;
for(int i = 1; i <= n; i ++){
cin >> w[i];
}
int hh = 0, tt = 0;
for(int i = 1; i <= n; i ++){
if(i - k > q[hh]) hh ++;
f[i] = f[q[hh]] + w[i];
while(hh <= tt && f[q[tt]] >= f[i]) tt --;
q[++tt] = i;
}
int res = 2e9;
for(int i = n - k + 1; i <= n; i ++) res = min(res, f[i]);
cout << res << endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;
LL f[N];
LL s[N];
int q[N];
int n, m;

LL g(int x){
if(x == 0) return 0;
return f[x - 1] - s[x];
}
int main (){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
s[i] += s[i - 1];
}
int hh = 0, tt = 0;
for(int i = 1; i <= n; i ++){
if(i - m > q[hh]) hh ++;
f[i] = max(f[i - 1], g(q[hh]) + s[i]);
while(hh <= tt && g(q[tt]) <= g(i)) tt --;
q[++tt] = i;
}
cout << f[n] << endl;
return 0;
}


#### 最为最小值的贡献值为3 34 35 345 4种

class Solution {
public:
const int mod = 1e9 + 7;
long long qmi(long long a, int b){
long long res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
int sumSubseqWidths(vector<int>& nums) {
int n = nums.size();
long long res = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i ++){
res = (res + qmi(2, i) * nums[i] - qmi(2, n - i - 1) * nums[i]);
}
return (res % mod + mod) % mod;
}
};