跳转至

251224 模拟赛

T1

稍微观察性质后 dp 即可。

T2

给定一个长度为 \(n\) 的序列，有 \(q\) 次查询，每次给定区间 \([l,r]\) 和数字 \(x\)，问最少进行以下操作多少次可以把区间内所有数都变成 \(x\)。

\(n\le 2\times 10^5\)

答案肯定是将区间内的数字排好序去重后，再插入 \(x\)，相邻两项差的最大值，再拿 \(m\) 减一下。相邻两项是环上的相邻。

首先想到删除-撤销回滚莫队，因为这样答案不会变小。发现插入 \(x\) 不好做，因此先不管它，考虑维护只有区间中数字时的答案。这玩意显然直接用链表维护。考虑插入 \(x\)，如果 \(x\) 没有插入到最大值所在的区间，那么也是好做的。否则我们需要记录次大值，并同时拿 \(x\) 和最大值区间的距离更新。

然而这样做会有问题，因为删除一个点形如把两个区间合并成一个区间，即删除两个区间，再插入一个区间。如果删除的区间恰好是最大值或者次大值会有问题。但感觉这样不会有问题，如果只删除了最大值，那么显然直接更新最大值即可；如果只更新了次大值，那么显然也直接更新次大值即可；如果同时删除了最大值和次大值，那么最大值的贡献一定非严格超过第三小的贡献，因为前者至少是后者的二倍，此时直接删去次大值，更新最大值即可。

赛时因为讨论的乱七八糟，导致虽然想到了关键点但是认为自己假了。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
const int B = 450;

int n, nq, m;

struct myPair {
    int l, r, val;
    inline myPair() : l(), r(), val() {}
    inline myPair(int _l, int _r) : l(_l), r(_r), val((r - l + m - 1) % m + 1) {}
    inline bool operator<(const myPair &b) const {
        return val < b.val;
    }
    inline bool operator>(const myPair &b) const {
        return val > b.val;
    }
};

int blo[N], blen;
struct Qr {
    int l, r, v, id;
    inline bool operator<(const Qr &b) const {
        if(blo[l] != blo[b.l]) return blo[l] < blo[b.l];
        return r > b.r;
    }
} q[N];

struct rollback_tp {
    myPair mx, mx2;
    int v;
};

int a[N], ans[N];
int num[N], nn;

void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int cnt[N], pre[N], nxt[N];
int c_l, c_r; myPair c_mx, c_mx2;
rollback_tp sta[N]; int top;

void del(int p) {
    int v = a[p];
    cnt[v]--;
    sta[++top] = {c_mx, c_mx2, v};
    if(cnt[v] == 0) {
        int p = pre[v], s = nxt[v];
        myPair cur(num[p], num[s]);
        if(c_mx.l == num[v] || c_mx.r == num[v]) swap(c_mx, c_mx2);
        if(cur > c_mx) c_mx2 = c_mx, c_mx = cur;
        else if(cur > c_mx2) c_mx2 = cur;
        if(c_mx2.l == num[v] || c_mx2.r == num[v]) c_mx2 = (myPair){};
        nxt[p] = s, pre[s] = p;
    }
}

void roll_back() {
    c_mx = sta[top].mx, c_mx2 = sta[top].mx2;
    nxt[pre[sta[top].v]] = sta[top].v;
    pre[nxt[sta[top].v]] = sta[top].v;
    ++cnt[sta[top].v];
    --top;
}

void clear_buf() { top = 0; }

int get_ans(int v) {
    if(c_mx.l == c_mx.r) {
        return m - min((v - c_mx.l + m) % m, (c_mx.r - v + m) % m);
    }
    if(c_mx.l < v && v < c_mx.r || (c_mx.r < c_mx.l && (c_mx.l < v || v < c_mx.r)) || c_mx.l == c_mx.r) {
        return max(c_mx2.val, max((v - c_mx.l + m) % m, (c_mx.r - v + m) % m));
    }
    return c_mx.val;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> nq >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(m == 1) {
        for(int i = 1; i <= nq; i++) {
            int l, r, v; cin >> l >> r >> v;
            cout << 0 << '\n';
        }
        return 0;
    }
    for(int i = 1; i <= nq; i++) cin >> q[i].l >> q[i].r >> q[i].v, q[i].id = i;

    lisanhua();
    blen = sqrt(n);
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    sort(q + 1, q + 1 + nq);

    for(int i = 1; i <= n; i++) cnt[a[i]]++;
    for(int i = 1; i < nn; i++) {
        nxt[i] = i + 1, pre[i + 1] = i;
        myPair cur(num[i], num[i + 1]);
        if(cur > c_mx) c_mx2 = c_mx, c_mx = cur;
        else if(cur > c_mx2) c_mx2 = cur;
    }
    {
        nxt[nn] = 1, pre[1] = nn;
        myPair cur(num[nn], num[1]);
        if(cur > c_mx) c_mx2 = c_mx, c_mx = cur;
        else if(cur > c_mx2) c_mx2 = cur;
    }

    c_l = 1, c_r = n;
    for(int i = 1; i <= nq; i++) {
        int l = q[i].l, r = q[i].r, v = q[i].v;
        if(blo[l] != blo[q[i - 1].l]) {
            while(top) roll_back(); c_r = n;
            while(c_l < (blo[l] - 1) * blen + 1) del(c_l++);
            clear_buf();
        }
        while(c_r > r) del(c_r--);
        int tmp = top;
        while(c_l < l) del(c_l++);
        ans[q[i].id] = get_ans(v);
        while(top > tmp) roll_back(), c_l--;
    }

    for(int i = 1; i <= nq; i++) cout << m - ans[i] << '\n';

    return 0;
}