#include using namespace std; typedef long long ll; typedef unsigned long long ull; // typedef __int128 i128; typedef pair pii; const int N = 5e4 + 10, mod = 998244353; const ll inf = 1e18; template void dbg(const T &t) { cout << t << endl; } template void dbg(const Type& arg, const Types&... args) { cout << arg << ' '; dbg(args...); } namespace Loop1st { int n, Q, a[N], L, R; ll s[N], mx[17][N], mn[17][N], f[17][17][N], tmp[N], res[N], ans[N]; ll ask1(int l, int r) { int x = __lg(r - l + 1); return min(mn[x][l], mn[x][r - (1 << x) + 1]); } ll ask2(int l, int r) { int x = __lg(r - l + 1); return max(mx[x][l], mx[x][r - (1 << x) + 1]); } void solve(int l, int r) { if (r - l + 1 < L) return ; if (l == r) { ans[l] = max(ans[l], (ll)a[l]); return ; } int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r); ll mx = -inf; for (int i = max(mid - R + 2, l); i <= mid; i++) { int x = max(mid + 1, i + L - 1), y = min(r, i + R - 1); if (x > y) { ans[i] = max(ans[i], mx); continue; } mx = max(mx, ask2(x, y) - s[i - 1]); ans[i] = max(ans[i], mx); } mx = -inf; for (int i = min(r, R + mid - 1); i > mid; i--) { int x = max(l, i - R + 1), y = min(mid, i - L + 1); if (x > y) { ans[i] = max(ans[i], mx); continue; } mx = max(mx, s[i] - ask1(x - 1, y - 1)); ans[i] = max(ans[i], mx); } } void main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i]; for (int i = 1; i <= n; i++) mx[0][i] = mn[0][i] = s[i]; for (int d = 1; d < 17; d++) for (int i = 0; i <= n - (1 << d) + 1; i++) { // s[0] = 0 也要考虑 mx[d][i] = max(mx[d - 1][i], mx[d - 1][i + (1 << d - 1)]); mn[d][i] = min(mn[d - 1][i], mn[d - 1][i + (1 << d - 1)]); } for (int d = 0; d <= __lg(n) - 1; d++) { for (int i = 1; i <= n; i++) ans[i] = -inf; L = 1 << d, R = (1 << d + 1) - 1; solve(1, n); for (int i = 1; i <= n; i++) f[d][d][i] = ans[i]; } for (int d1 = 0; d1 <= __lg(n) - 1; d1++) { for (int d2 = d1 + 1; d2 <= __lg(n) - 1; d2++) { for (int i = 1; i <= n; i++) f[d1][d2][i] = max(f[d1][d2 - 1][i], f[d2][d2][i]); } } cin >> Q; while (Q--) { int l, r; ull Ans = 0; cin >> l >> r; for (int i = 1; i <= n; i++) ans[i] = res[i] = -inf; if (l * 2 > r) { L = l, R = r; solve(1, n); for (int i = 1; i <= n; i++) Ans ^= ans[i] * i; cout << Ans << '\n'; continue; } int d1 = __lg(l) + 1, d2 = __lg(r); if (d1 < d2) for (int i = 1; i <= n; i++) res[i] = f[d1][d2 - 1][i]; L = l, R = (1 << d1) - 1; solve(1, n); for (int i = 1; i <= n; i++) res[i] = max(res[i], ans[i]); L = 1 << d2, R = r; for (int i = 1; i <= n; i++) ans[i] = -inf; solve(1, n); for (int i = 1; i <= n; i++) { res[i] = max(res[i], ans[i]); Ans ^= res[i] * i; } cout << Ans << '\n'; } } } int main() { // freopen("data.in", "r", stdin); // freopen("data.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; // cin >> T; while (T--) { Loop1st::main(); } return 0; }

题库

题库

12260.序列询问(query)

题解大全 共 0 篇

测试用例

题解大全共 0 篇