#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long const int M = 3e5 + 5, mod = 998244353; int a[M]; struct dian { int l, r, lw, rw, sum; // lw表示左边连续的1的个数 // rw表示右边连续的1的个数 // sum表示区间每段连续1除2向上取整的和 } f[M << 2]; dian merge(dian x, dian y) { int c1 = x.lw, c2 = x.rw; int c3 = y.lw, c4 = y.rw; int flag1 = 0, flag2 = 0; if (c1 == x.r - x.l + 1) flag1 = 1; if (c3 == y.r - y.l + 1) flag2 = 1; int id = 0; dian ans; ans.l = x.l; ans.r = y.r; // 如果左子树全为1，右子树不为1，则将左边连续的1的个数加到右子树的左边 if (flag1 == 1 && flag2 == 0) { ans.lw = c1 + c3; ans.rw = c4; ans.sum = (c1 + c3 + 1) / 2 - (c3 + 1) / 2 + y.sum; return ans; } if (flag1 == 0 && flag2 == 1) { ans.lw = c1; ans.rw = c2 + c4; ans.sum = (c2 + c4 + 1) / 2 - (c2 + 1) / 2 + x.sum; return ans; } if (flag1 == 0 && flag2 == 0) { ans.lw = c1; ans.rw = c4; ans.sum = x.sum + y.sum - (c2 + 1) / 2 - (c3 + 1) / 2 + (c2 + c3 + 1) / 2; return ans; } ans.lw = c1 + c3; ans.rw = c2 + c4; ans.sum = (c1 + c3 + 1) / 2; return ans; } void pushup(int id) { f[id] = merge(f[id << 1], f[id << 1 | 1]); } void build(int id, int l, int r) { f[id].l = l, f[id].r = r; if (l == r) { f[id].lw = f[id].rw = a[l]; f[id].sum = a[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); pushup(id); } dian query(int id, int l, int r) { if (l <= f[id].l && f[id].r <= r) return f[id]; int mid = (f[id].l + f[id].r) >> 1; if (r <= mid) return query(id << 1, l, r); if (l > mid) return query(id << 1 | 1, l, r); dian x = query(id << 1, l, r); dian y = query(id << 1 | 1, l, r); return merge(x, y); } void solve() { int n, q; cin >> n >> q; string s; cin >> s; vector<int> sum(n + 2); for (int i = 1; i <= n; i++) { a[i] = s[i - 1] - '0'; sum[i] = sum[i - 1] + (a[i] == 0); } build(1, 1, n); while (q--) { int l, r; cin >> l >> r; dian ans = query(1, l, r); cout << ans.sum + (sum[r] - sum[l - 1]) << endl; } } signed main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) solve(); return 0; }
https://www.luogu.com.cn/problem/P3370
#include <bits/stdc++.h> using namespace std; const int base1 = 29, base2 = 131, M = 2e5 + 5, mod1 = 1e9 + 7, mod2 = 1e9 + 9; int hash1[M], hash2[M], pow1[M], pow2[M]; string s; struct Hash { public: void init(string s) { // 下标从1开始 hash1[0] = hash2[0] = 0; pow1[0] = pow2[0] = 1; int n = s.size(); for (int i = 1; i <= n; ++i) { pow1[i] = pow1[i - 1] * base1 % mod1; pow2[i] = pow2[i - 1] * base2 % mod2; } for (int i = 1; i <= n; ++i) { hash1[i] = (hash1[i - 1] * base1 + s[i]) % mod1; hash2[i] = (hash2[i - 1] * base2 + s[i]) % mod2; } } pair<int, int> gethash(string s, int l, int r) { return {(hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1, (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2}; } }; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; set<pair<int, int>> f; while (t--) { cin >> s; s = " " + s; int n = s.size(); Hash h; h.init(s); f.insert(h.gethash(s, 1, n - 1)); } cout << f.size(); return 0; }
#include <bits/stdc++.h> using namespace std; #define int long long const int M = 1e5 + 5; int dp[M][22]; signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, t; cin >> n >> t; for (int i = 1; i <= n; i++) cin >> dp[i][0]; for (int j = 1; j <= 22; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } while (t--) { int x, y; cin >> x >> y; int k = log2(y - x + 1); cout << max(dp[x][k], dp[y - (1 << k) + 1][k]) << "\n"; } return 0; }
https://www.luogu.com.cn/problem/P3383
#include <bits/stdc++.h> using namespace std; const int M = 1e8 + 10; int a[100000010], k = 0; bool f[100000010]; void fun(int n) { for (int i = 2; i <= n; i++) { if (f[i] == 0) a[++k] = i; for (int j = 1; j <= k && i * a[j] <= n; j ++) { f[i * a[j]] = 1; if (i % a[j] == 0) break; } } } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t, n, x; cin >> n >> t; fun(n); while (t--) { cin >> x; cout << a[x] << "\n"; } return 0; }
https://www.luogu.com.cn/problem/P1330
#include <bits/stdc++.h> using namespace std; const int M = 2e5 + 5; int a[M], vis[M], color[M], ans, anss; vector<int> f[M]; void dfss(int now) { vis[now] = color[now] = 0; for (auto x : f[now]) if (vis[x]) dfss(x); } bool dfs(int now) { vis[now] = 1; if (color[now]) ans++; for (auto x : f[now]) if (!vis[x]) { color[x] = 1 - color[now]; if (!dfs(x)) return 0; } else if (color[now] == color[x]) return 0; return 1; } void solve() { int n, m, x, y; cin >> n >> m; while (m--) { cin >> x >> y; f[x].push_back(y); f[y].push_back(x); } for (int i = 1; i <= n; ++i) if (!vis[i]) { int cnt = 1e9; ans = 0; if (dfs(i)) cnt = min(cnt, ans); ans = 0; dfss(i); color[i] = 1; if (dfs(i)) cnt = min(cnt, ans); if (cnt == 1e9) { cout << "Impossible"; return; } anss += cnt; } cout << anss; } signed main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 1; // cin>>t; while (t--) solve(); return 0; }
