题解：P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II

· · 题解

思路

先提出一个结论（以下讨论均局限于询问的区间 (x,y) 中）：

令第二个人可以操作的区间集合为 S，即：

S=\{(l,r)\mid r-l+1\le c_2,\sum_{i=l}^ra_i>w_2\}

如果存在一个区间 (L,R) 满足：

并且如果忽略第二个人的存在，这个区间可以全部变成红色，即 \max_{i=x}^ya_i\le w_1。

如果以上两个条件均满足，那么第一个人会赢。否则第二个人会赢。

证明

先证充分性：充分性是显然的。第一个人只需要先把 S 没有覆盖的点变成红色，再对 (L,R) 操作，一次性把剩下的点变红，第一个人就赢了。

然后证必要性：考虑反证。假设不存在区间 (L,R)，下面给出一种第二个人的操作策略，使得第一个人无法胜利。

设 S 中左端点最靠左的区间为 (l_1,r_1)，右端点最靠右的区间为 (l_2,r_2)。

假设第一个人操作了区间 (l_3,r_3)：

因为第一个人的可操作区间中不存在 (L,R) 满足 L\le l_1,R\ge r_2，所以前两种情况不会同时出现，故这个操作是可以实现的。而这样操作保证了每一轮操作后 a_{l_1},a_{r_2} 中至少有一个是蓝色的，故第一个人不可能获胜。

于是我们证明了这个结论。于是我们可以对于每次询问，找到集合 S 的左边界和右边界（即证明中提到的 l_1,r_2），然后判断是否存在一个区间 (L,R)，满足开始提到的两个条件即可。

容易发现，当且仅当第一个人可以操作 (l_1,r_2) 时，满足条件的 (L,R) 存在。这是因为，区间的长度越长，其区间和就越大，就越有可能不满足条件，所以 (l_1,r_2) 是最有可能满足条件的区间。所以直接判断 r_2-l_1+1\le c_1,\sum_{i=l_1}^{r_2}a_i\le w_1 是否成立即可。

那么如何寻找 (l_1,r_2) 呢？同样容易发现，区间的长度越短，其区间和就越小，就越有可能不能被第二个人操作。所以，只需要找所有长度为 c_2 的区间进行判断即可。

可以维护一个值 f_i 表示 a_i 到 a_{i+c_2-1} 的，即：

f_i=\sum_{j=i}^{i+c_2-i}a_i

那么，l_1 就是满足 f_i>w_2 的最小的 i，r_2-c_2+1 就是满足 f_i>w_2 的最大的 i。可以用线段树维护 f_i，查询时在线段树上二分即可。这样就得到了 (l_1,r_2)。

当然，如果 y-x+1<c_2，就只需要判一下 (x,y) 能不能被第二个人操作即可。

总结一下，具体的步骤就是：

然后就做完了。修改使用线段树、树状数组容易维护。时间复杂度 O(q\log n)。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 3e5 + 5;

int n, q, c1, c2;
ll w1, w2;
ll a[maxn], tr[maxn];

void upd(int id, ll k){
    for(int i = id; i <= n; i += i & -i) tr[i] += k; 
}
ll que(int id){
    ll s = 0;
    for(int i = id; i > 0; i -= i & -i) s += tr[i];
    return s;
}
namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2], tag[maxn << 2];
void up(int x){
    max1[x] = max(max1[l(x)], max1[r(x)]);
}
void down(int x){
    max1[l(x)] += tag[x], tag[l(x)] += tag[x];
    max1[r(x)] += tag[x], tag[r(x)] += tag[x];
    tag[x] = 0;
}
void update(int x, int l, int r, int ql, int qr, ll k){
    if(ql <= l && r <= qr){
        max1[x] += k, tag[x] += k;
        return;
    }
    down(x);
    int mid = l + r >> 1;
    if(ql <= mid) update(l(x), l, mid, ql, qr, k);
    if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);
    up(x);
}
int query1(int x, int l, int r, int ql, int qr, ll k){
    if(ql <= l && r <= qr){
        if(max1[x] <= k) return 0;
        if(l == r){
            if(max1[x] > k) return l;
            else return 0;
        }
        down(x);
        int mid = l + r >> 1;
        if(max1[l(x)] > k) return query1(l(x), l, mid, ql, qr, k);
        else return query1(r(x), mid + 1, r, ql, qr, k);
    }
    down(x);
    int mid = l + r >> 1, res = 0;
    if(ql <= mid) res = query1(l(x), l, mid, ql, qr, k);
    if(res) return res;
    if(qr > mid) res = query1(r(x), mid + 1, r, ql, qr, k);
    return res;
}
int query2(int x, int l, int r, int ql, int qr, ll k){
    if(ql <= l && r <= qr){
        if(max1[x] <= k) return 0;
        if(l == r){
            if(max1[x] > k) return l;
            else return 0;
        }
        down(x);
        int mid = l + r >> 1;
        if(max1[r(x)] > k) return query2(r(x), mid + 1, r, ql, qr, k);
        else return query2(l(x), l, mid, ql, qr, k);
    }
    down(x);
    int mid = l + r >> 1, res = 0;
    if(qr > mid) res = query2(r(x), mid + 1, r, ql, qr, k);
    if(res) return res;
    if(ql <= mid) res = query2(l(x), l, mid, ql, qr, k);
    return res;
}}
namespace seg2{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2];
void up(int x){
    max1[x] = max(max1[l(x)], max1[r(x)]);
}
void build(int x, int l, int r){
    if(l == r){
        max1[x] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(l(x), l, mid), build(r(x), mid + 1, r);
    up(x);
}
void update(int x, int l, int r, int id, ll k){
    if(l == r){
        max1[x] += k;
        return;
    }
    int mid = l + r >> 1;
    if(id <= mid) update(l(x), l, mid, id, k);
    else update(r(x), mid + 1, r, id, k);
    up(x);
}
ll query(int x, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr) return max1[x];
    int mid = l + r >> 1;
    ll res = 0;
    if(ql <= mid) res = max(res, query(l(x), l, mid, ql, qr));
    if(qr > mid) res = max(res, query(r(x), mid + 1, r, ql, qr));
    return res;
}}

int main(){
    scanf("%d %d %d %d %lld %lld", &n, &q, &c1, &c2, &w1, &w2);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i ++){
        upd(i, a[i]);
        seg::update(1, 1, n, max(1, i - c2 + 1), i, a[i]);
    }
    seg2::build(1, 1, n);
    while(q --){
        int op;
        scanf("%d", &op);
        if(op == 1){
            int x;
            ll y;
            scanf("%d %lld", &x, &y);
            upd(x, y);
            seg::update(1, 1, n, max(1, x - c2 + 1), x, y);
            seg2::update(1, 1, n, x, y);
            a[x] += y;
        }else{
            int l, r;
            scanf("%d %d", &l, &r);
            if(seg2::query(1, 1, n, l, r) > w1){
                printf("tetris\n");
                continue;
            }
            int L = 0, R = 0;
            if(r - l + 1 <= c2){
                if(que(r) - que(l - 1) > w2) L = l, R = r;
            }else{
                L = seg::query1(1, 1, n, l, r - c2 + 1, w2);
                R = seg::query2(1, 1, n, l, r - c2 + 1, w2) + c2 - 1;
            }
            if(!L || !R){
                printf("cont\n");
                continue;
            }
            if(que(R) - que(L - 1) <= w1 && R - L + 1 <= c1) printf("cont\n");
            else printf("tetris\n");
        }
    }
    return 0;
}