CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

https://codeforces.com/contest/1896

D. Ones and Twos

题意

给定一个数组 $a$，只含有 $1,2$。每次询问有两种类型：

• “1 s” 查询是否有一个子数组的和为 $s$。
• “2 i v” 将 $a_i$ 改为 $v$。

数据范围：$1\leq n,q\leq 10^5$。

题解

注意到对于原数组，一定可以凑出所有不超过它且与它奇偶性相同的数：若两端有 $2$，则不选一个 $2$，否则两个 $1$ 都不选，就由 $sum$ 得到了 $sum-2$。

所以每次询问的 $s$ 如果和 $sum$ 奇偶性一致，只需要判断 $s$ 是否不超过 $sum$。否则需要删去最靠近头或者尾的一个 $1$，再判断 $s$ 是否不超过剩下的部分。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,q;cin>>n>>q;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        set<int> s;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(a[i]==1) s.insert(i);
        }
        while(q--)
        {
            int op;cin>>op;
            if(op==1)
            {
                int x;cin>>x;
                if(sum%2==x%2) cout<<(x<=sum?"YES":"NO")<<'\n';
                else
                {
                    if(s.empty()) cout<<"NO"<<'\n';
                    else
                    {
                        auto it1=s.begin(),it2=s.end();
                        it2--;
                        cout<<(x<=sum-1-2*min(*it1-1,n-*it2)?"YES":"NO")<<'\n';
                    }
                }
            }
            else 
            {
                int i,v;cin>>i>>v;
                sum=sum-a[i]+v;
                if(a[i]==1) s.erase(i);
                a[i]=v;
                if(v==1) s.insert(i);
            }
        }
    }
    return 0;
}

E. Permutation Sorting

题解

问题可以归结为：区间（x，y）表示 x 需要到达 y，循环 y-x 次，那么 x 的答案为 y - x -（x，y）中包含的区间个数。

这可以用树状数组实现。