题解：CF1146E Hot is Cold

elswzl · 2025-06-28 17:01:57 · 题解

Solution

现在有一个01数组 a，a_i 为 1 表示原序列中的 i 要 \times -1，否则不乘。

那么读者手枚一下，可以发现无论是什么操作，都可以划归为对 a 的以下两类操作：

• 区间01翻转。
• 区间赋值01。

这个显然可以线段树维护。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,inf=1e5;
struct segmenttree{
    struct node{
        int lz,v;
    }t[N<<2];
    void push_down(int p){
        if(!t[p].lz)return ;
        if(t[p].lz==1){
            t[p<<1].v=t[p<<1|1].v=1;t[p<<1].lz=t[p<<1|1].lz=1;
        }
        if(t[p].lz==2){
            t[p<<1].v=t[p<<1|1].v=0;t[p<<1].lz=t[p<<1|1].lz=2;
        }
        if(t[p].lz==3){
            t[p<<1].v^=1;t[p<<1|1].v^=1;
            t[p<<1].lz=3-t[p<<1].lz;
            t[p<<1|1].lz=3-t[p<<1|1].lz;
        }
        t[p].lz=0;
    }
    void modify(int l,int r,int L,int R,int p,int d){
        if(L>R)return ;
        if(l>=L&&r<=R){
            if(d==1){
                t[p].lz=d;t[p].v=1;
            }
            if(d==2){
                t[p].lz=d;t[p].v=0;
            }
            if(d==3){
                t[p].lz=3-t[p].lz;t[p].v^=1;
            }
            return ;
        }
        push_down(p);
        int mid=l+r>>1;
        if(mid>=L)modify(l,mid,L,R,p<<1,d);
        if(mid<R)modify(mid+1,r,L,R,p<<1|1,d);
    }
    int find(int l,int r,int x,int p){
        if(l==r)return t[p].v;
        push_down(p);
        int mid=l+r>>1;
        if(mid>=x)return find(l,mid,x,p<<1);
        return find(mid+1,r,x,p<<1|1);
    }
}s;
int n,m,a[N];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='>'){
            x++;
            if(x>=1){
                s.modify(-inf,inf,x,inf,1,1);
                s.modify(-inf,inf,-inf,-x,1,2);
            }
            else{
                s.modify(-inf,inf,x,-x,1,3);
                s.modify(-inf,inf,-inf,x-1,1,2);
                s.modify(-inf,inf,1-x,inf,1,1);
            }
        }
        else{
            x--;
            if(x<=-1){
                s.modify(-inf,inf,-inf,x,1,1);
                s.modify(-inf,inf,-x,inf,1,2);
            }
            else{
                s.modify(-inf,inf,-x,x,1,3);
                s.modify(-inf,inf,x+1,inf,1,2);
                s.modify(-inf,inf,-inf,-x-1,1,1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        int p=s.find(-inf,inf,a[i],1);
        if(p)cout<<-a[i]<<" ";
        else cout<<a[i]<<" ";
    }
    return 0;
}