H小轩

9602

oceanrivers

laosu03
2237351892

MUCK

run
jwh
OUTSTANDING

xcm

Profligate
zzlhh

H小轩
4天前

PS: 该题目正解应该是DP, 本人没想太多写了深搜, TLE, 总共4982个点, 只能过4974个

## 四. C++ 代码

typedef pair<int, int> PII;
const int N = 3e4 + 10;
#define x first
#define y second

class Solution {
public:
int h[N], e[N << 1], ne[N << 1], idx, sum;
bool st[N];
int ans;

bool check(int d, int cnt)  // 检查是否满足条件, 如果满足则提前退出DFS
{
if(d >= ans) return true;  // 最优性剪枝, 当前已知答案不比当前枚举的方案差
if(cnt == sum) return true;  // 可行性剪枝, 找到的金币已是金币总数
return false;
}

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

PII DFS(int u, int fa, vector<int>& coins, int dist, int cnt)
{
int get = 0, d = 0;

for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
if(!st[son]) get += coins[son], st[son] = true;

if(check(d + dist * 2, get + cnt)) return {get, d};  // 剪枝

for(int j = h[son]; ~j; j = ne[j])
{
int sson = e[j];
if(sson == son) continue;
if(!st[sson]) get += coins[sson], st[sson] = true;
if(check(d + dist * 2, get + cnt)) return {get, d};  // 剪枝
}
}
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
auto t = DFS(son, u, coins, dist + 1, get);
if(t.x)
{
get += t.x, d += 1 * 2 + t.y;
if(check(d + dist * 2, get + cnt)) return {get, d};  // 剪枝
}
}
return {get, d};
}

int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
memset(h, -1, sizeof h);

sum = 0; ans = 0x3f3f3f3f;
for(int i : coins) sum += i;

for(int i = 0; i < edges.size(); i ++ )
{
int a = edges[i][0], b = edges[i][1];
}

for(int i = 0; i < n;  i ++ )
{
memset(st, 0, sizeof st); st[i] = true;
auto t = DFS(i, -1, coins, 0, coins[i]);
if(coins[i]) t.x ++ ;
if(t.x == sum) ans = min(t.y, ans);
}
return ans;
}
};


H小轩
5天前
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 110, M = 1e5 + 10, NN = 20 * 100;
int n, m, v[N], cnt[N], f[M], w[NN], sum;

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

{
sum = 0;
for(int i = 1; i <= n; i ++ ) read(v[i]);
for(int i = 1; i <= n; i ++ ) read(cnt[i]);

for(int i = 1; i <= n; i ++ )
{
int s = min((m + v[i] - 1) / v[i], cnt[i]);
int k = 1;
while(s >= k)
{
w[ ++ sum] = k * v[i];
s -= k;
k <<= 1;
}
if(s) w[ ++ sum] = s * v[i];
}
memset(f, 0, sizeof f);
f[0] = 1;

for(int i = 1; i <= sum; i ++ )
for(int j = m; j >= w[i]; j -- )
{
if(f[j]) continue;
f[j] |= f[j - w[i]];
}

int ans = 0;
for(int i = 1; i <= m; i ++ )
if(f[i]) ans ++ ;
print(ans); puts("");
}

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
5天前
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 2e5 + 10;
LL n, k, a, b, q;
struct node {
int l, r;
LL val;
LL sum1L, sum1R;
LL sum2L, sum2R;
}tr[N << 2];

void pushup(int u)
{
if(tr[u].sum1L != tr[u << 1].sum1L + tr[u << 1].sum1R) tr[u].sum1L = tr[u << 1].sum1L + tr[u << 1].sum1R;
if(tr[u].sum2L != tr[u << 1].sum2L + tr[u << 1].sum2R) tr[u].sum2L = tr[u << 1].sum2L + tr[u << 1].sum2R;
if(tr[u].sum1R != tr[u << 1 | 1].sum1L + tr[u << 1 | 1].sum1R) tr[u].sum1R = tr[u << 1 | 1].sum1L + tr[u << 1 | 1].sum1R;
if(tr[u].sum2R != tr[u << 1 | 1].sum2L + tr[u << 1 | 1].sum2R) tr[u].sum2R = tr[u << 1 | 1].sum2L + tr[u << 1 | 1].sum2R;
}

void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, 0, 0, 0, 0, 0};
else
{
tr[u] = {l, r, 0, 0, 0, 0, 0};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void update(int u, int idx, LL add)
{
if (tr[u].l == idx && tr[u].r == idx)
{
tr[u].sum1L  = min(tr[u].val, a);
tr[u].sum2L  = min(tr[u].val, b);
return ;
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (idx <= mid) update(u << 1, idx, add);
else update(u << 1 | 1, idx, add);
pushup(u);
}
}

LL query1(int u, int l, int r)
{
if(l > r) return 0;
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum1L + tr[u].sum1R;
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
LL res = 0;
if (l <= mid ) res = query1(u << 1, l, r);
if (r > mid) res += query1(u << 1 | 1, l, r);
return res;
}
}

LL query2(int u, int l, int r)
{
if(l > r) return 0;
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum2L + tr[u].sum2R;
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
LL res = 0;
if (l <= mid ) res = query2(u << 1, l, r);
if (r > mid) res += query2(u << 1 | 1, l, r);
return res;
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n >> k >> a >> b >> q;
build(1, 1, n);
string line; LL op[3];
getline(cin, line);
while(q -- )
{
getline(cin, line);
stringstream ssin(line);
int cnt = 0;
while(ssin >> op[cnt]) cnt ++ ;

if(op[0] == 1)
{
update(1, (int)op[1], op[2]);
}
else
{
int l1 = 1, r1 = op[1] - 1;
int l2 = op[1] + k, r2 = n;
LL ans = 0;
ans = query1(1, l2, r2) + query2(1, l1, r1);
cout << ans << endl;
}
}
return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
5天前
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 100000 + 10, M = 400000 + 10;
int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp, scc_cnt, id[N], scc_size[N];
stack<int> stk;
bool in_stk[N];
int f[N];

void add(int h[], int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

void Tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk.push(u); in_stk[u] = true;

for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
Tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j])
low[u] = min(low[u], dfn[j]);
}

if(low[u] == dfn[u])
{
scc_cnt ++ ;
while(stk.top() != u)
{
int t = stk.top(); stk.pop(); in_stk[t] = false;
id[t] = scc_cnt, scc_size[scc_cnt] ++ ;
}
stk.pop(); in_stk[u] = false;
id[u] = scc_cnt, scc_size[scc_cnt] ++ ;
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

memset(h, -1, sizeof h); memset(hs, -1, sizeof hs);
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) add(h, 0, i, 1);
int t, a, b;
while(m -- )
{
cin >> t >> a >> b;
if(t == 1) add(h, a, b, 0), add(h, b, a, 0);
else if(t == 2) add(h, a, b, 1);
else if(t == 3) add(h, b, a, 0);
else if(t == 4) add(h, b, a, 1);
else if(t == 5) add(h, a, b, 0);
}

Tarjan(0);

for(int i = 0; i <= n; i ++ )
{
for(int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if(a == b && w[j])
{
cout << -1;
return 0;
}
if(a != b)
{
add(hs, a, b, w[j]);
}
}
}

for(int i = scc_cnt; i; i -- )
{
for(int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
f[k] = max(f[k], f[i] + w[j]);
}
}

LL ans = 0;
for(int i = scc_cnt; i; i -- )
ans += (LL)f[i] * scc_size[i];
cout << ans;

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
5天前

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 1e4 + 10, M = 2e5 + 10;
int n, m;
int p[N], w[N];

int find(int u)
{
if(u != p[u])
{
int root = find(p[u]);
if(root != p[u])
{
w[u] += w[p[u]];
p[u] = root;
}
}
return p[u];
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n >> m;
for(int i = 1; i <= n; i ++ ) p[i] = i;

int op, a, b;
while(m -- )
{
cin >> op >> a >> b;
if(op & 1)
{
a = find(a); b = find(b);
if(a != b)
{
w[a] -= w[b];
p[a] = b;
}
}
else
{
a = find(a);
w[a] += b;
}
}

for(int i = 1; i <= n; i ++ )
{
int pa =find(i), t = w[i];
if(pa != i) t += w[pa];
cout << t << " " ;
}

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



BFS 过7个点

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 1e4 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx, w[N];
bool st[N];

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void BFS(int u, int k)
{
memset(st, 0, sizeof st);
queue<int> q;
q.push(u); st[u] = true;

while(q.size())
{
auto t = q.front(); q.pop();
w[t] += k;

for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

memset(h, -1, sizeof h);
cin >> n >> m;
int op, a, b;
while(m -- )
{
cin >> op >> a >> b;
if(op & 1)
{
if(a != b) add(a, b), add(b, a);
}
else
BFS(a, b);
}

for(int i = 1; i <= n; i ++ ) cout << w[i] << " " ;

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
5天前

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 2e5 + 10;
int n, m, arr[N];
struct node {
int l, r;
}tr[N << 2];

void pushup(int u)
{
tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
}

void pushdown(int u)
{
{
auto &root = tr[u], &L = tr[u << 1], &R = tr[u << 1 | 1];
}
}

void build(int l, int r, int u)
{
tr[u] = {l, r};
if(l == r)
{
tr[u].minv = arr[l];
return ;
}

int mid = (l + r) >> 1;
build(l, mid, u << 1);
build(mid + 1, r, u << 1 | 1);
pushup(u);
}

void modify(int l, int r, LL a, int u)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].minv += a, tr[u].add += a;
return ;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if(mid >= l) modify(l, r, a, u << 1);
if(mid < r) modify(l, r, a, u << 1 | 1);
pushup(u);
}

LL query(int l, int r, int u)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].minv;
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
LL res = LLONG_MAX;
if(mid >= l) res = min(res, query(l, r, u << 1));
if(mid < r) res = min(res, query(l, r, u << 1 | 1));
return res;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> arr[i];
build(1, n, 1);

cin >> m; string line; int op[3];
getline(cin, line);
while(m -- )
{
int idx = 0;
getline(cin, line);
stringstream ssin(line);
while(ssin >> op[idx]) idx ++ ;
op[0] ++ , op[1] ++ ;
if(idx == 3)
{
if(op[0] > op[1])
{
modify(op[0], n, (LL)op[2], 1);
modify(1, op[1], (LL)op[2], 1);
}
else
modify(op[0], op[1], (LL)op[2], 1);
}
else
{
LL temp = 0;
if(op[0] > op[1])
temp = min(query(op[0], n, 1), query(1, op[1], 1));
else
temp = query(op[0], op[1], 1);
cout << temp << endl;
}
}

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
6天前

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 1e5 + 10;
int n, hs[N], arr[N];
LL ans;

struct node {
int l, r;
LL maxv;
}tr[N << 2];

void pushup(int u)
{
tr[u].maxv = max({tr[u].maxv, tr[u << 1].maxv, tr[u << 1 | 1].maxv});
}

void build(int l, int r, int u)
{
tr[u] = {l, r};
if(l == r) return ;

int mid = (l + r) >> 1;
build(l, mid, u << 1);
build(mid + 1, r, u << 1 | 1);
}

void change(int idx, LL a, int u)
{
if(tr[u].l == idx && tr[u].r == idx)
{
tr[u].maxv = max(tr[u].maxv, a);
return ;
}

int mid = (tr[u].l + tr[u].r) >> 1;
if(mid >= idx) change(idx, a, u << 1);
else change(idx, a, u << 1 | 1);
pushup(u);
}

LL query(int l, int r, int u)
{
if(r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r) {
return tr[u].maxv;
}
int mid = (tr[u].l + tr[u].r) >> 1;
LL res = 0;
if(mid >= l) res = max(res, query(l, r, u << 1));
if(r > mid) res = max(res, query(l, r, u << 1 | 1));
return res;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n;

for(int i = 1; i <= n; i ++ )
{
cin >> arr[i];
hs[i] = arr[i];
}
sort(hs + 1, hs + n + 1);
int len = unique(hs + 1, hs + n + 1) - hs - 1;
build(1, len, 1);

for(int i = 1; i <= n; i ++ )
{
int e = lower_bound(hs + 1, hs + len + 1, arr[i]) - hs;
LL temp = query(1, e - 1, 1) + arr[i];
ans = max(ans, temp);
change(e, temp, 1);
}
cout << ans;
return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
6天前
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 2e5 + 10, M = log2(N) + 5;
int n, m, f[N][M], arr[N];

void init()
{
for(int len = 0; len < M; len ++ )
for(int l = 1; l <= n; l ++ )
{
int r = l + (1 << len) - 1;
if(r > n) continue;
if(!len) f[l][len] = arr[l];
else f[l][len] = max(f[l][len - 1], f[l + (1 << len - 1)][len - 1]);
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> arr[i];
init();
cin >> m;
int a, b;
while(m -- )
{
cin >> a >> b;
int len = b - a + 1;
int k = log2(len);
cout << max(f[a][k], f[b - (1 << k) + 1][k]) << endl;
}

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
6天前
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 2e5 + 10;
struct node {
int l, r;
int maxv;
}tr[N << 4];
int n, m, P, w[N];

void pushup(int u)
{
tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int l, int r, int u)
{
if(l == r) tr[u] = {l, r, w[l]};
else
{
int mid = (l + r) >> 1;
tr[u] = {l, r};
build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);
pushup(u);
}
}

int query(int l, int r, int u)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
int res = 0;
int mid = (tr[u].l + tr[u].r) >> 1;
if(mid >= l) res = max(res, query(l, r, u << 1));
if(mid + 1 <= r) res = max(res, query(l, r, u << 1 | 1));
return res;
}

void add(int idx, int a, int u)
{
if(tr[u].l == idx && tr[u].r == idx) tr[u].maxv = a;
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(idx <= mid) add(idx, a, u << 1);
else add(idx, a, u << 1 | 1);
pushup(u);
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> m >> P;
build(1, (int)2e5, 1);
char op; int x, temp = 0;
while(m -- )
{

cin >> op >> x;
if(op == 'A')
{
x = ((LL)x + temp) % P;
add( ++ n, x, 1);
}
else
{
int l = n - x + 1, r = n;
temp = query(l, r, 1);
cout << temp << endl;
}
}

return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}



H小轩
6天前
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define x first
#define y second
#define INF 0x3f3f3f3f
#define int128 __int128
template <typename T> inline void print(T x);
template <typename T> inline void read(T &x);
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;

const int N = 1e5 + 10;
int n, m;
LL arr[N], sum[N];

bool check(int u)
{
for(int i = 1; i < n; i ++ )
{
int l = i, r = i + u - 1;
if(r > n - 1) continue;
if(sum[r] - sum[l - 1] < (m << 1)) return false;
}
return true;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6);

cin >> n >> m;
for(int i = 1; i < n; i ++ )
{
cin >> arr[i];
sum[i] = arr[i] + sum[i - 1];
}

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

cout << l ;
return 0;
}

// =========================================================================================

template <typename T> inline void read(T &x)
{
x = 0; T f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}

template <typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}