一、堆
#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue < int, vector < int >, greater < int > > heap;
signed main () {
scanf ("%d", &n);
while (n --) {
int op;
scanf ("%d", &op);
if (op == 1) {
int x;
scanf ("%d", &x);
heap.push (x);
}
else if (op == 2) {
printf ("%d\n", heap.top ());
}
else {
heap.pop ();
}
}
return 0;
}
二、负环
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, n, m, cnt, head[2005], in[2005], vis[2005], dis[2005];
struct edge {
int to, nxt, val;
} ed[6005];
inline void add_edge (int u, int v, int w) {
cnt ++;
ed[cnt].to = v;
ed[cnt].val = w;
ed[cnt].nxt = head[u];
head[u] = cnt;
}
inline bool SPFA (int s) {
for (int i = 1;i <= n; ++ i) in[i] = vis[i] = 0, dis[i] = 1e18;
queue < int > q;
q.push (s); vis[s] = 1; dis[s] = 0; in[s] ++;
if (in[s] > n) return true;
while (!q.empty ()) {
int u = q.front ();
q.pop (); vis[u] = 0;
for (int i = head[u]; i ; i = ed[i].nxt) {
int v = ed[i].to;
int w = ed[i].val;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = 1;
in[v] ++;
q.push (v);
if (in[v] > n) return true;
}
}
}
}
return false;
}
signed main () {
scanf ("%lld", &T);
while (T --) {
scanf ("%lld %lld", &n, &m);
cnt = 0;
for (int i = 1;i <= n; ++ i) head[i] = 0;
for (int i = 1;i <= m; ++ i) {
int u, v, w;
scanf ("%lld %lld %lld", &u, &v, &w);
if (w >= 0) {
add_edge (u, v, w);
add_edge (v, u, w);
}
else {
add_edge (u, v, w);
}
}
if (SPFA (1)) printf ("YES\n");
else printf ("NO\n");
}
return 0;
}
三、ST 表
#include <bits/stdc++.h>
using namespace std;
inline int read () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c ^ 48);
return x;
}
int n, m, a[100005], lg[100005], st[100005][22];
inline int query (int l, int r) {
int k = lg[r - l + 1];
return max (st[l][k], st[r - (1 << k) + 1][k]);
}
signed main () {
n = read (); m = read ();
for (int i = 1;i <= n; ++ i) a[i] = read ();
lg[0] = -1;
for (int i = 1;i <= n; ++ i) lg[i] = lg[i >> 1] + 1;
for (int i = 1;i <= n; ++ i) st[i][0] = a[i];
for (int j = 1;j <= 21; ++ j) {
for (int i = 1;i + (1 << j) - 1 <= n; ++ i) {
st[i][j] = max (st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
while (m --) {
int l, r;
l = read (); r = read ();
printf ("%d\n", query (l, r));
}
return 0;
}