codeforces round 771

• A
• B
• C
• D
• E

贪心算法

#include 
typedef long long ll;
using namespace std;
void solve(){
    int n;
    cin>>n;
    vectora(n);
    for( int i=0;i
        cin>>a[i];
    }
    for( int i=0;i
        if(a[i]==i+1) continue;
        else {
            for( int j=i+1;j
                if(a[j]==i+1) {
                    reverse(a.begin()+i,a.begin()+j+1);
                }
            }
            break;
        }
    }
    for( int i=0;i
        cout<
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}

相同奇偶的数不能交换，所以看奇数和偶数是否分别有序

#include 
typedef long long ll;
using namespace std;
int solve(){
    int n;
    cin>>n;
    vectoreven,odd;
    for( int i=0;i
        int x;
        cin>>x;
        if(x%2==1) odd.push_back(x);
        else even.push_back(x);
    }
    if(is_sorted(odd.begin(),odd.end())&&is_sorted(even.begin(),even.end())){
        return 1;
    }
    else return 0;
    
}
int main(){
    int t;
    cin>>t;
    while(t--){
        if(solve()) cout<<"YES"< 
C 
树状数组，如果前面所有数都出现一次，ans++
 
#include 
typedef long long ll;
using namespace std;
template 
struct Fenwick {
    const int n;
    std::vector a;
    Fenwick(int n) : n(n), a(n) {}
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    T sum(int x) {
        T ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    //注意下面不是闭区间
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};
int solve(){
    int n;
    cin>>n;
    Fenwickfen(n+1);
    int ans=0;
    for( int i=0;i
        int x;
        cin>>x;
        fen.add(x-1,1);
        if(fen.sum(i+1)==i+1) ans++;
    }
    return ans;
    
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cout< 
D 
模拟，dfs
 dfs看当前选择的四个格子里，没有涂色的所有格子是否是同一个颜色。
 
#include
using namespace std;
typedef long long ll;

int main(){
    int n,m;
    cin>>n>>m;
    vector>v(n,vector(m));
    for( int i=0;i
        for( int j=0;j
            cin>>v[i][j];
        }
    }
    vector>ans;
    auto dfs=[&]( auto self,int x,int y)->void{
        // cout<=n-1||y>=m-1) return ;
        int c=-1;
        for( int i=0;i<2;i++){
            for( int j=0;j<2;j++){
                int xx=x+i,yy=y+j;
                if(v[xx][yy]==-1) continue;
                if(c!=-1&&c!=v[xx][yy]) return ;
                c=v[xx][yy];
            }
        }  
        if(c==-1) return ;
        ans.push_back({x,y,c});
        for( int i=0;i<2;i++){
            for( int j=0;j<2;j++){
                v[x+i][y+j]=-1;
            }
        }
        for( int i=-1;i<=1;i++){
            for( int j=-1;j<=1;j++){
                self(self,x+i,y+j);
            }
        }
    };
    for( int i=0;i
        for( int j=0;j
            dfs(dfs,i,j);
        }
    }
    for( int i=0;i
        for( int j=0;j
            if(v[i][j]!=-1) {
                cout<<-1<
        printf("%d %d %dn",it[0]+1,it[1]+1,it[2]);
    }
    system("pause");
}

 
E 
数据结构，树状数组+区间维护。
 首先使用map维护每个区间的位置，first对应左端点，second对应区间对应的颜色值。
 对于每次颜色更新，首先将更新的区间分割出来，然后更新树状数组，更新的方式是将区间减去后来颜色的值，加上原来颜色的值。
 这种区间维护的方式只能维护区间的所有数直接变化。
 
#include 
typedef long long ll;
using namespace std;
template 
struct Fenwick {
    const int n;
    std::vector a;
    Fenwick(int n) : n(n), a(n) {}
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    T sum(int x) {
        T ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    //注意下面不是闭区间
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};
int solve(){
    int n,q;
    cin>>n>>q;
    vectoradd(n+10);
    Fenwickfen(n+10);
    mapseg;
    seg[1]=1;seg[n+1]=-1;
    auto split= [&](int x){
        auto it=prev(seg.upper_bound(x));
        seg[x]=it->second;
    };
    auto rangeup=[&]( int l,int r,ll val){
        fen.add(l,val);
        fen.add(r+1,-val);
    };
    for( int i=0;i
        string s;
        cin>>s;
        if(s=="Color") {
            int l,r,c;
            cin>>l>>r>>c;
            split(l);split(r+1);
            auto it=seg.find(l);
            while(it->first!=r+1){
                int l=it->first,r=next(it)->first-1;
                rangeup(l,r,add[it->second]-add[c]);
                it=seg.erase(it);
            }
            seg[l]=c;
        }
        else if(s=="Add"){
            int x,y;
            cin>>x>>y;
            add[x]+=y;
        }
        else if(s=="Query"){
            int x;
            cin>>x;
            cout<second]<<'n';
        }
    }
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}