20241031总结

dream

首先朴素的 \(dp\) 很好想，前缀和优化也很简单，接下来考虑如何继续优化。

我们发现反转操作相当于把一个序列变成环反转后再移动几格，于是我们只需要知道 \(1\) 位置的变换就能知道其它位置数的变换。

#include<iostream>
#define int long long

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}

const int N = 5e3 + 10, mod = 1e9 + 7;
int c, n, m, q;
int a[N], pos[N], l[N], r[N], dp[N][N];
int t[N];
void solve(){
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++) t[j] = (t[j - 1] + dp[i - 1][j]) % mod;
        for (int j = 1; j <= n; j++){
            if (j <= r[i]) dp[i][j] = (dp[i][j] + (t[r[i] - j + 1] - t[max(l[i] - j + 1, 1ll) - 1] + mod) % mod) % mod;
            if (j >= l[i] + 1) dp[i][j] = (dp[i][j] + (t[n - j + min(r[i], j - 1) + 1] - t[n - j + l[i]] + mod) % mod) % mod;
        }
    }
}

signed main(){
    freopen("dream.in", "r", stdin);
    freopen("dream.out", "w", stdout);
    c = read(), n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++) a[i] = read(), pos[a[i]] = i;
    for (int i = 1; i <= m; i++) l[i] = read(), r[i] = read();
    solve();
    while (q--){
        int p = read(), v = pos[read()];
        if (m & 1){
            cout << dp[m][((p + v - 2) % n + n) % n + 1] << '\n';
        }else{
            cout << dp[m][((p - v) % n + n) % n + 1] << '\n';
        }
    }
    return 0;
}

puppet

不会。

wind

不会。

firefly

线段树暴力 \(35pts\)。

#include<iostream>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}

const int N = 1e6 + 10;
int c, n, m, q;
struct node{
    int l, r;
}p[N];
struct tree{
    int sum, tag;
}t[N << 2];
void pushup(int now){
    t[now].sum = t[now << 1].sum + t[now << 1 | 1].sum;
}
void pushdown(int now, int l, int r){
    int mid = (l + r) >> 1;
    if (t[now].tag)
        t[now << 1].sum = (mid - l + 1), t[now << 1 | 1].sum = (r - mid), t[now << 1].tag = t[now].tag, t[now << 1 | 1].tag = t[now].tag;
}
void modify(int now, int l, int r, int x, int y, int k){
    if (x <= l && r <= y){
        t[now].sum = k * (r - l + 1);
        t[now].tag = k;
        return;
    }
    pushdown(now, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid && t[now << 1].sum < (mid - l + 1)) modify(now << 1, l, mid, x, y, k);
    if (mid + 1 <= y && t[now << 1 | 1].sum < (r - mid)) modify(now << 1 | 1, mid + 1, r, x, y, k);
    pushup(now);
}
void solve(){
    int L = read(), R = read();
    for (int i = 1; i <= m; i++)
        if (p[i].l >= L && p[i].r <= R)
            modify(1, 1, n, p[i].l, p[i].r, 1);
    cout << t[1].sum << '\n';
    for (int i = 1; i <= (n << 2); i++) t[i].sum = t[i].tag = 0;
}

int main(){
    freopen("firefly.in", "r", stdin);
    freopen("firefly.out", "w", stdout);
    c = read(), n = read(), m = read(), q = read();
    for (int i = 1; i <= m; i++) p[i].l = read(), p[i].r = read();
    while (q--) solve();
    return 0;
}