倒着讲，但这套题目没上场周赛质量高，A是个常规的枚举，B/C都是猜结论题，D是经典的线段树应用。前三题搞完23分钟，最后一题不想写线段树了就找了个板子改了改过了，D改板子有一个地方写错了错了一次，1:19AK的，Rank 516 / 22683。Profile Here。

Question D Handling Sum Queries After Update

题意

有两个长度均为n的数组nums1和nums2，nums1是一个01数组，针对这两个数组做q次询问，规则如下：

• “1 l r”，表示对nums1[l:r]上的0变为1，1变为0；
• “2 p 0”，表示对nums2[1:n]上的所有nums2[i] += p * nums1[i]
• “3 0 0”, 表示求$\sum_{i=1}^{n} nums2[i]$

($n \le 1e5, q \le 1e5, p \le 1e6$)

题解

我个人认为这是一道被改简单过的题，操作2和操作3完全是脱裤子放屁。操作1是一个区间01翻转，操作3实际上并不会询问特定区间的和，而只是询问nums2数组完整的和，这就要求我们的操作2并不需要单点更新，只需要维护这个数组完整的和就可以了，要想维护这个数组完整的和，我们在操作2实际上就相当于询问nums1数组[1:n]区间上到底有多少1，这个问题可以扩展到询问任意的[l:r]区间上到底有多少1。

因此我们明确了要做的事情，维护一个01序列的区间翻转，询问01序列的特定区间上到底要有多少1。这个是线段树的经典问题，更复杂的操作也可以完成，这实际上是SCOI2010(四川2010年省队)选拔的题目，我相信洛谷的评论区会比我讲的更加详细。代码如下：

typedef long long ll;
#define ls(k) ((k)<<1)
#define rs(k) (ls(k)^1)
#define mid ((l+r)>>1)

const int maxn = 1e5 + 10;

struct Node {
    int len,sum;
    int l[2],r[2],res[2];
    int same,flip;
    Node():same(-1),flip(0) {}
    void turn(int k) {
        l[k]=r[k]=res[k]=len,
        l[k^1]=r[k^1]=res[k^1]=0;
        sum=!k?0:len;
        same=k, flip=0;
    }
    void rev() {
        swap(l[0],l[1]), swap(r[0],r[1]), swap(res[0],res[1]);
        sum=len-sum;
        flip^=1;
    }
};

class Solution {
public:
    int n;
    int a[maxn];
    Node node[maxn*4];

    void pushdown(int k) {
        Node &ls=node[ls(k)], &rs=node[rs(k)];
        int &same=node[k].same, &flip=node[k].flip;
        if(same!=-1) {
            ls.turn(same), rs.turn(same);
            same=-1;
        }
        if(flip==1) {
            ls.rev(), rs.rev();
            flip=0;
        }
    }

    Node maintain(const Node &ls,const Node &rs) {
        Node R;
        R.len=ls.len+rs.len, R.sum=ls.sum+rs.sum;
        for(int i=0;i<2;i++) {
            R.l[i]=ls.l[i], R.r[i]=rs.r[i];
            if(ls.l[i]==ls.len) R.l[i]=ls.len+rs.l[i];
            if(rs.r[i]==rs.len) R.r[i]=rs.len+ls.r[i];
            R.res[i]=max(max(R.l[i],R.r[i]),ls.r[i]+rs.l[i]);
            R.res[i]=max(R.res[i],max(ls.res[i],rs.res[i]));
        }
        R.same=-1, R.flip=0;
        return R;
    }

    void build(int k,int l,int r) {
        node[k].len=r-l+1;
        if(l==r) {
            int x=a[l];
            node[k].l[x]=node[k].r[x]=node[k].res[x]=1;
            node[k].sum=x;
            return;
        }
        build(ls(k),l,mid);
        build(rs(k),mid+1,r);
        node[k]=maintain(node[ls(k)],node[rs(k)]);
        return;
    }

    void flip(int k,int l,int r,int ql,int qr) {
        if(l!=r) pushdown(k);
        if(ql<=l && r<=qr) {
            node[k].rev();
            return;
        }
        if(ql<=mid) flip(ls(k),l,mid,ql,qr);
        if(qr> mid) flip(rs(k),mid+1,r,ql,qr);
        node[k]=maintain(node[ls(k)],node[rs(k)]);
        return;
    }

    void flip(int l,int r) {
        flip(1,1,n,l,r);
    }

    Node query(int k,int l,int r,int ql,int qr) {
        if(l!=r) pushdown(k);
        if(ql<=l && r<=qr) return node[k];
        if(qr<=mid) return query(ls(k),l,mid,ql,qr);
        else if(ql>mid) return query(rs(k),mid+1,r,ql,qr);
        else return maintain(query(ls(k),l,mid,ql,qr),query(rs(k),mid+1,r,ql,qr));
    }

    int query_sum(int l,int r) {
        Node ans=query(1,1,n,l,r);
        return ans.sum;
    }


public:
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        vector<ll> ret;
        ll res = 0;
        n = nums1.size();
        for(int i = 0; i < n; i++){
            a[i + 1] = nums1[i];
        }
        build(1, 1, n);
        for(auto &it : nums2){
            res += it;
        }
        for(auto &q : queries) {
            int op = q[0], x = q[1], y = q[2];
            if(op == 1)
                x += 1, y += 1, flip(x, y);
            else if(op == 2){
                res += query_sum(1, n) * 1ll * x;
            }
            else if(op == 3){
                ret.push_back(res);
            }
        }
        return ret;
    }
};

Question C Minimum Impossible OR

题意

给定一个长为n的数组nums，问最小不能被任意个nums中的数按位或(即 $|_{i = 1}^{k} nums[index_i]$ ）表示的数。$(n \le 1e5, a[i] \le 1e9)$

题解

这也是一个观察的题目，有点数学归纳法的想法。

先从k=1开始想，如果nums不包括1，那么1一定是无法被表示的最小的那个数。

接着k=2，如果k=1已经被包括了，接下来需要考虑的不能被表示的最小数应该是k=2。而如果1和2都存在的话，下一个不能被表示的数就应该是k=4，到这里我们已经可以看出一些潜在的规律了，实际上我们只需要看看最小的不存在于给定的nums数组中的数就可以了，这些数都应该是2的幂次，就可以得到如下代码：

class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        int tt = 1;
        set<int> st;
        for(auto &it : nums) st.insert(it);
        for(int i = 1; i <= 31; i++){
            if(st.count(tt) == 0){
                return tt;
            }
            tt *= 2;
        }
        return tt;
    }
};

Question B Minimum Score by Changing Two Elements

题意

给定一个长为n的数组nums，定义low score为|nums[i] - nums[j]| (0 <= i < j < nums.length)中最小的,high score是 |nums[i] - nums[j]| (0 <= i < j < nums.length)中最大的，可以任意修改最多两个下标的nums[i] = a, nums[j] = b($a, b \in Z$)，问修改后low score + high score 的最小可能值是多少？

题解

因为要求high + low的最小可能值，low score的最小可能值只能是0，即只要nums数组中存在两个相同的数就能达到这个最小可能值。

我们希望在取到high score的最小可能值的时候也尽量让low=0，而high相当于是求nums数组中最大值和最小值的差，想要让这个值尽可能地小，我们可以考虑把nums数组中的所有数从小到大排列在一个数轴上，数对应的点之间构成一条线段，如果想让这条线段变短，就只能砍掉一部分端点(即如让nums的最大值变为num s的次大值，就相当于砍掉次大值和最大值之间的这条线段)，因为只能砍两刀，因此让这条线段尽可能短的方法，只可能在int cand1 = abs(nums[n - 1] - nums[2]), cand2 = abs(nums[n - 2] - nums[1]), cand3 = abs(nums[n - 3] - nums[0]);这三个值中取最小的，而这个过程自然可以保证产生两个相同的值。

因此我们就有了如下代码：

class Solution {
public:
    int minimizeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int cand1 = abs(nums[n - 1] - nums[2]), cand2 = abs(nums[n - 2] - nums[1]), cand3 = abs(nums[n - 3] - nums[0]);
        return min(cand1, min(cand2, cand3));
    }
};

Question A Maximum Difference by Remapping a Digit

题意

给定一个值num，可以做一次映射操作使0-9中的一个数码变为另一个数码（也可以相同，相当于不变化），从而使num变为一个新数。问这样得到的新数的最大值和最小值之间的差？

代码

暴力枚举每种映射就可以了。不需要想什么取巧的方法。

class Solution {
public:
    int minMaxDifference(int num) {
        string res = to_string(num);
        int mini = num, maxi = num;
        for(int dfm = '0'; dfm <= '9'; dfm++){
            for(int dto = '0'; dto <= '9'; dto++){
                string temp = res;
                int x = 0;
                for(auto &it : temp){
                    if(it == dfm)
                        it = dto;
                }
                for(int i = 0; i < temp.length(); i++){
                    x *= 10, x += (temp[i] - '0');
                }                
                mini = min(mini, x), maxi = max(maxi, x);
            }
        }
        return maxi - mini;
    }
};