40 分球调

sto_5k_orz @ 2023-08-03 22:42:14

#include<bits/stdc++.h>
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void ssrand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
const int N = 2e7 + 10;
int dp[N / 500 + 5][16], le[N / 500 + 5], ri[N / 500 + 5], in[N], a[N], mx[N / 500 + 5], tot, pre[N], suf[N];
int ask(int l, int r) {
    if(l > r) return 0; int k = __lg(r - l + 1);
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
signed main() {
    int n, q, s; cin >> n >> q >> s; ssrand(s); unsigned long long ans = 0;
    for(int i = 1; i <= n; i++) a[i] = read(); int B = 500;
    for(int i = 1; i <= n; i++) in[i] = (i + B - 1) / B;
    for(int i = 1; i <= n; i++) {
        int M = a[i];
        int j = i + 1; while(j <= n && in[j] == in[i]) j++, M = max(M, a[j]);
        ++tot; le[tot] = i, ri[tot] = j - 1; mx[tot] = M; suf[ri[tot]] = a[ri[tot]]; pre[le[tot]] = a[le[tot]];
        for(int k = le[tot] + 1; k <= ri[tot]; k++) pre[k] = max(pre[k - 1], a[k]);
        for(int k = ri[tot] - 1; k >= le[tot]; k--) suf[k] = max(suf[k + 1], a[k]);
        i = j - 1;
    }
    for(int i = 1; i <= tot; i++) dp[i][0] = mx[i];
    for(int j = 1; j < 16; j++) for(int i = 1; i + (1 << j) - 1 <= tot; i++) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
    while(q--) {
        int l = read() % n + 1, r = read() % n + 1; if(l > r) swap(l, r);
        if(in[l] == in[r]) {int mx = 0; for(int i = l; i <= r; i++) mx = max(mx, a[i]); ans += mx; continue;}
        ans += max(ask(in[l] + 1, in[r] - 1), max(suf[l], pre[r]));
    }
    cout << ans; 
    return 0;
}

by sto_5k_orz @ 2023-08-04 12:06:06

@5k_sync_closer

by sto_5k_orz @ 2023-08-04 14:18:18

@5k_sync_closer

by 5k_sync_closer @ 2023-08-04 14:22:20

@Stitch0711 考虑 l,r 在相邻块的情况

by sto_5k_orz @ 2023-08-04 14:25:00

@5k_sync_closer 考虑了

by sto_5k_orz @ 2023-08-04 14:26:28

ask 里面 l>r 就是在相邻块的吧

by sto_5k_orz @ 2023-08-04 14:38:44

@5k_sync_closer 但是如果没有考虑的话直接保龄了捏

by 5k_sync_closer @ 2023-08-04 15:13:50

@Stitch0711 过了

#include<bits/stdc++.h>
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void ssrand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
const int N = 2e7 + 10;
int dp[N / 500 + 5][16], le[N / 500 + 5], ri[N / 500 + 5], in[N], a[N], mx[N / 500 + 5], tot, pre[N], suf[N];
int ask(int l, int r) {
    if(l > r) return 0; int k = __lg(r - l + 1);
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
signed main() {
    int n, q, s; cin >> n >> q >> s; ssrand(s); unsigned long long ans = 0;
    for(int i = 1; i <= n; i++) a[i] = read(); int B = 500;
    for(int i = 1; i <= n; i++) in[i] = (i + B - 1) / B;
    for(int i = 1; i <= n; i++) {
        int M = a[i];
        int j = i; while(j < n && in[j + 1] == in[i]) j++, M = max(M, a[j]);
        ++tot; le[tot] = i, ri[tot] = j; mx[tot] = M; suf[ri[tot]] = a[ri[tot]]; pre[le[tot]] = a[le[tot]];
        for(int k = le[tot] + 1; k <= ri[tot]; k++) pre[k] = max(pre[k - 1], a[k]);
        for(int k = ri[tot] - 1; k >= le[tot]; k--) suf[k] = max(suf[k + 1], a[k]);
        i = j;
    }
    for(int i = 1; i <= tot; i++) dp[i][0] = mx[i];
    for(int j = 1; j < 16; j++) for(int i = 1; i + (1 << j) - 1 <= tot; i++) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
    while(q--) {
        int l = read() % n + 1, r = read() % n + 1; if(l > r) swap(l, r);
        if(in[l] == in[r]) {int mx = 0; for(int i = l; i <= r; i++) mx = max(mx, a[i]); ans += mx; continue;}
        ans += max(ask(in[l] + 1, in[r] - 1), max(suf[l], pre[r]));
    }
    cout << ans;
    return 0;
}

by sto_5k_orz @ 2023-08-04 15:23:40

@5k_sync_closer 是不是就改了个 i=j

by sto_5k_orz @ 2023-08-04 15:24:15

% 5k