社区讨论

求大佬解答

BBrilliant11001
学术版参与者 5已保存回复 12

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mhkdyu5r
此快照首次捕获于
2025/11/04 17:48
4 个月前
此快照最后确认于
2025/11/05 00:00
4 个月前
查看原帖

关于封装数据结构

如下代码：
CPP
#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;

const int N = 1000010;

typedef long long ll;
typedef pair<int, int> PII;

int n, k, q, type;
ll suma[N], sumb[N];
PII dp[21][N];
int log_2[N];

void init_log_2() {
    log_2[1] = 0;
    for(int i = 2; i <= n; i++)
        log_2[i] = log_2[i / 2] + 1;
}

inline PII cmp(PII a, PII b) {
    if(!a.x && !a.y) return b;
    if((ll)a.x * b.y < (ll)b.x * a.y) return b;
    return a;
}

ll gcd(ll a, ll b) {
    if(!b) return a;
    return gcd(b, a % b);
}
struct ST_table{
	PII f[21][N];
	void init() {
	    for(int j = 1; j <= log_2[n]; j++)
	        for(int i = 1; i + (1 << j) - 1 <= n; i++)
	            f[j][i] = cmp(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
	}
	inline PII query(int l, int r) {
	    int t = log_2[r - l + 1];
	    return cmp(f[t][l], f[t][r - (1 << t) + 1]);
	}
}st;

int main() {
    scanf("%d%d%d%d", &n, &k, &q, &type);
    init_log_2();
    for(int i = 1; i <= n; i++) {
        scanf("%d", &suma[i]);
        suma[i] += suma[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &sumb[i]);
        sumb[i] += sumb[i - 1];
    }
    for(int len = k; len <= k * 2; len++)
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            int sa = suma[r] - suma[l - 1];
            int sb = sumb[r] - sumb[l - 1];
            PII tmp = {sa, sb};
            if(len > k) dp[len - k][l] = cmp(cmp(dp[len - k - 1][l], dp[len - k - 1][l + 1]), tmp);
            else dp[len - k][l] = tmp;
        }
    for(int i = 1; i <= n - k + 1; i++)
        for(int j = i + k - 1; j <= min(i + k * 2 - 1, n); j++)
            st.f[0][i] = cmp(st.f[0][i], {suma[j] - suma[i - 1], sumb[j] - sumb[i - 1]});
    st.init();
    int l, r, lasans = 0;
    while(q--) {
        scanf("%d%d", &l, &r);
        l = (l ^ (lasans * type)) % n + 1, r = (r ^ (lasans * type)) % n + 1;
        if(l > r) swap(l, r);
        if(r - l + 1 < k) {
            printf("0/1\n");
            lasans = 0;
            continue;
        }
        PII ans = {0, 0};
        int limit = r - 2 * k + 1;
        if(limit >= l) ans = st.query(l, limit);
        else limit = l - 1;
        ans = cmp(ans, dp[r - limit - k][limit + 1]);
        int d = gcd(ans.x, ans.y);
        ans.x /= d, ans.y /= d;
        printf("%d/%d\n", ans.x, ans.y);
        lasans = ans.x;
    }
    return 0;
}
在 DEV 上编译会显示 out of memory allocating 8392703 bytes\texttt{out of memory allocating 8392703 bytes}，但好像能够正常运行，在 Vscode 和洛谷在线 IDE 上都能过编，在做题的 OJ 上反而会直接不过编。
但若不封装 ST 表：
CPP
#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;

const int N = 1000010;

typedef long long ll;
typedef pair<int, int> PII;

int n, k, q, type;
ll suma[N], sumb[N];
PII dp[21][N];
int log_2[N];

void init_log_2() {
    log_2[1] = 0;
    for(int i = 2; i <= n; i++)
        log_2[i] = log_2[i / 2] + 1;
}

inline PII cmp(PII a, PII b) {
    if(!a.x && !a.y) return b;
    if((ll)a.x * b.y < (ll)b.x * a.y) return b;
    return a;
}

ll gcd(ll a, ll b) {
    if(!b) return a;
    return gcd(b, a % b);
}

PII f[21][N];

void init() {
    for(int j = 1; j <= log_2[n]; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            f[j][i] = cmp(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
}

inline PII query(int l, int r) {
    int t = log_2[r - l + 1];
    return cmp(f[t][l], f[t][r - (1 << t) + 1]);
}

int main() {
    scanf("%d%d%d%d", &n, &k, &q, &type);
    init_log_2();
    for(int i = 1; i <= n; i++) {
        scanf("%d", &suma[i]);
        suma[i] += suma[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &sumb[i]);
        sumb[i] += sumb[i - 1];
    }
    for(int len = k; len <= k * 2; len++)
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            int sa = suma[r] - suma[l - 1];
            int sb = sumb[r] - sumb[l - 1];
            PII tmp = {sa, sb};
            if(len > k) dp[len - k][l] = cmp(cmp(dp[len - k - 1][l], dp[len - k - 1][l + 1]), tmp);
            else dp[len - k][l] = tmp;
        }
    for(int i = 1; i <= n - k + 1; i++)
        for(int j = i + k - 1; j <= min(i + k * 2 - 1, n); j++)
            f[0][i] = cmp(f[0][i], {suma[j] - suma[i - 1], sumb[j] - sumb[i - 1]});
    init();
    int l, r, lasans = 0;
    while(q--) {
        scanf("%d%d", &l, &r);
        l = (l ^ (lasans * type)) % n + 1, r = (r ^ (lasans * type)) % n + 1;
        if(l > r) swap(l, r);
        if(r - l + 1 < k) {
            printf("0/1\n");
            lasans = 0;
            continue;
        }
        PII ans = {0, 0};
        int limit = r - 2 * k + 1;
        if(limit >= l) ans = query(l, limit);
        else limit = l - 1;
        ans = cmp(ans, dp[r - limit - k][limit + 1]);
        int d = gcd(ans.x, ans.y);
        ans.x /= d, ans.y /= d;
        printf("%d/%d\n", ans.x, ans.y);
        lasans = ans.x;
    }
    return 0;
}
就能正常运行了，报错也消失了。
请问这是为什么？

回复

共 12 条回复，欢迎继续交流。

正在加载回复...