Codeforces Round 755 div.1 ABC

第一次打div1，头被锤烂了（

A. Two Arrays

题意：有两个 \(1-n\) 的排列 \(a,b\)，可以对 \(a\) 序列进行如下操作：

1. 将一些位置上的数+1
2. 任意改变 \(a\) 的顺序

问能否一次操作将 \(a\) 变成 \(b\)

排序后依次判断每一位上的 \(a\) 能否变成 \(b\) 即可

int n, m;
int a[maxn], b[maxn];
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    for(int i=1;i<=n;i++){
        if(a[i] > b[i]){
            cout << "NO\n";
            return;
        }
        if(a[i] < b[i] - 1){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

7分钟签完这题，剩下时间都在坐牢了（（

B. Guess the Permutation

题意：交互题，有一个 \(1-n\) 的排列 \(a\)，初始时 \(a_i = i\)，电脑对这个序列进行了一次更改：将 \([i,j-1]\)，\([j,k]\) 两个区间翻转了，你可以询问：\([l,r]\) 上有多少个逆序对？询问至多40次，要猜出 \(i,j,k\)

先二分找到 \(i\)，用至多30次，然后可以根据 \([i,n]\) 的结果减去 \([i+1,n]\) 直接得出第一个逆序串的长度。。同理第二个也很好弄了。

考场上剩下时间全在搞这个题的玄学二分优化、三分

赛后一看代码，发现核心思维压根就没想到，很服气

ll n;
ll query(ll l, ll r){
    cout << "? " << l << ' ' << r << endl;
    cout.flush();
    ll x;
    cin >> x;
    return x;
}
 
void solve(){
 
    cin >> n;
    ll l = 1, r = n;
    while(l < r){
        ll mid = (l + r + 1) / 2;
        ll x = query(1, mid);
        if(x == 0){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll s1 = 1 + query(l, n) - query(l + 1, n);
    ll j = l + s1;
    ll s2 = 1 + query(j, n) - query(j + 1, n);
    cout << "! " << l << ' ' << l + s1 << ' ' << l + s1 + s2 - 1 << '\n';
 
    cout.flush();
}

C. Game with Stones

题意：有一列石头堆 \(a\)，\(a_i\) 表示第 \(i\) 堆石头的数量，Bob每次可以选择两个相邻的石头堆，同时从中拿走一个石头（不能选择空石头堆），如果Bob可以把这列石头堆全部清空，则Bob获胜。现在问有多少组 \([l,r]\) 使得单独拿出 \(l\) 到 \(r\) 位置上的石头，可以使Bob获胜。

首先可以注意到，任意一列石头，Bob必须从两端开始取，比如从左到右取，那么就依次让每个位置上的值减去上一位的值，设 \(c_i=a_i-c_{i-1}\)，如果取的中途出现了一位 \(c_i\) 为负数，则一定不能获胜；取到结尾处如果 \(c_n=0\) 则恰能获胜，否则还是不能获胜。

考虑左端点为1的情况：直接一遍计算出所有的 \(c\)，然后统计 \(c\) 在第一个负数之前0的个数，即为左端点为1的答案。

接下来考虑如何快速转移：忽略第一堆石头，将左端点为1情况下的 \(c\) 转移到左端点为2的情况。

很显然，将最左边的 \(a_1\) 去掉会使得 \(c_2\) 加上 \(a_1\)，\(c_3\) 减去 \(a_1\)，\(c_4\) 又加上 \(a_1\) ...

即使得后面的所有奇数位加上或减去 \(a_1\)，偶数位反之；在任何一次转移中，所有的奇数位都同时变化，偶数位也同时变化。

那么可以考虑将奇偶数位分开维护，这样我们只需要一种数据结构，需要支持区间加减法和区间查找 \(c\) 在第一个负数之前0的个数

这里给出一种线段树维护的思路：

对于奇数位和偶数位各开一个线段树，维护区间最小值和最小值的数量，这个在区间加减法下很容易维护。

写两种操作：查询区间第一个负数的位置 和查询不含负数区间中0的数量，显然这两个操作能够满足需求。

第一种操作，查找时若左段的最小值为负，则查找左边，否则查找右边；

第二种操作，因为保证区间没有负数了，找到对应区间后直接返回最小值数量即可，注意要筛掉最小值不为0的区间。

ll n, a[maxn], c[maxn];

ll f1(ll x){ return 2 * x - 1;}
ll f2(ll x){ return 2 * x;}

struct SegTree{
    ll num[maxn << 2], mi[maxn << 2], tad[maxn << 2];
    ll ls[maxn << 2], rs[maxn << 2];
    ll (*fp)(ll);
    inline void push_up(ll p){
        num[p] = num[ls[p]] + num[rs[p]];
        mi[p] = min(mi[ls[p]], mi[rs[p]]);
        num[p] = 0;
        if(mi[p] == mi[ls[p]]) num[p] += num[ls[p]];
        if(mi[p] == mi[rs[p]]) num[p] += num[rs[p]];
    }
    inline void push_add(ll p, ll ad){
        mi[p] += ad;
        tad[p] += ad;
    }
    inline void push_down(ll p){
        push_add(ls[p], tad[p]);
        push_add(rs[p], tad[p]);
        tad[p] = 0;
    }
    void build(ll p, ll l, ll r){
        if(l > r) return;
        tad[p] = 0;
        if(l == r){
            num[p] = 1;
            mi[p] = c[fp(l)];
            return;
        }
        ll mid = (l + r) / 2;
        ls[p] = p*2, rs[p] = p*2+1;
        build(p*2, l, mid);
        build(p*2+1, mid+1, r);
        push_up(p);
    }
    void modify(ll p, ll l, ll r, ll L, ll R, ll ad){
        //lr为线段树中节点管辖下标范围，LR为实际查询范围
        if(fp(l) > R || fp(r) < L) return;
        if(L <= fp(l) && fp(r) <= R){
            push_add(p, ad);
            return;
        }
        push_down(p);
        ll mid = (l + r) / 2;
        modify(ls[p], l, mid, L, R, ad);
        modify(rs[p], mid+1, r, L, R, ad);
        push_up(p);
    }
    ll query_lz(ll p, ll l, ll r, ll L, ll R){
        if(fp(l) > R || fp(r) < L) return 1e9;
        if(mi[p] >= 0) return 1e9;
        if(l == r) return fp(l);
        push_down(p);
        ll mid = (l + r) / 2, re = 1e9;
        re = min(re, query_lz(ls[p], l, mid, L, R));
        if(re > 1e8) re = min(re, query_lz(rs[p], mid+1, r, L, R));
        return re;
    }
    ll query_num(ll p, ll l, ll r, ll L, ll R){
        if(fp(l) > R || fp(r) < L) return 0;
        if(mi[p] > 0) return 0;
        if(L <= fp(l) && fp(r) <= R) return num[p];//已经确认mi[p] == 0
        push_down(p);
        ll mid = (l + r) / 2, re = 0;
        re += query_num(ls[p], l, mid, L, R);
        re += query_num(rs[p], mid+1, r, L, R);
        return re;
    }
}st1, st2;

void solve() {
    cin >> n;
    for(ll i=1;i<=n;i++) cin >> a[i];
    for(ll i=1;i<=n;i++) c[i] = a[i] - c[i-1];

    st1.fp = f1;
    st2.fp = f2;
    st1.build(1, 1, (n+1)/2);
    st2.build(1, 1, n/2);

    ll ans = 0;
    ll zp = min(st1.query_lz(1, 1, (n+1)/2, 1, n),
                 st2.query_lz(1, 1, n/2, 1, n));
    if(zp > 1e8) zp = n + 1;
    ans += st1.query_num(1, 1, (n+1)/2, 1, zp-1);
    ans += st2.query_num(1, 1, n/2, 1, zp-1);
    for(ll i=1;i<n;i++){
        if(i % 2 == 0){
            st1.modify(1, 1, (n+1)/2, i+1, n, a[i]);
            st2.modify(1, 1, n/2, i+1, n, -a[i]);
        }else{
            st1.modify(1, 1, (n+1)/2, i+1, n, -a[i]);
            st2.modify(1, 1, n/2, i+1, n, a[i]);
        }
        ll zp = min(st1.query_lz(1, 1, (n+1)/2, i+1, n),
                     st2.query_lz(1, 1, n/2, i+1, n));
        if(zp > 1e8) zp = n + 1;
        ans += st1.query_num(1, 1, (n+1)/2, i+1, zp-1);
        ans += st2.query_num(1, 1, n/2, i+1, zp-1);
    }
    cout << ans << '\n';
}