2023.3.26 小红书后端后两题题解

第二题：简单思维题

const int N = 100010;
int a[N];
int pos[N];
int n,k;
void solve()
{
    
    cin >> n >> k;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        pos[a[i]] = i;
    }
    // 按照顺序判断2是否在1后面 如果不在可以把2,3,4...,k+1都放在最后
    int curr = 1;
    while(curr < n){
        int pos1 = pos[curr],pos2 = pos[curr + 1];
        if(pos2 < pos1){
            break;
        }
        curr ++;
    }
    int res = (n - curr + k - 1) / k;
    cout << res << endl;
}
int main()
{
    IOS;
    int _;
    cin >> _;
    while (_--)
    {
         solve();
    }
     return 0;
}

`

第三题：区间修改单点更新线段树+位运算性质(每一位开一颗线段树)

const int N = 100010,M = 100010;
int a[N];
int l[N],r[N];
int v[N];
string ops;
int n,m;

// 一共只有20位  或操作时只需要维护每一位上是否有1即可 如果赋值就被覆盖
// 与操作只需要判断是否与0即可

// 每次操作维护一个区间上的比特位上每一位的lazy
struct tnode
{
    int l,r;
    vector<int> bits;
    vector<int> lazy;
}tr[N << 2];
void build(int p,int l,int r){
    tr[p].l = l,tr[p].r = r;
    tr[p].bits.assign(20,0);
    tr[p].lazy.assign(20,-1);
    if(l == r){
        for(int i=0;i<19;++i){
            if(a[l] >> i & 1){
                tr[p].bits[i] = 1;
            }
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
}
void pushdown(int p){
    for(int i=0;i<20;++i){
        if(tr[p].lazy[i] != -1){
            tr[p<<1].bits[i] = tr[p].lazy[i];
            tr[p<<1|1].bits[i] = tr[p].lazy[i];
            tr[p<<1].lazy[i] = tr[p].lazy[i];
            tr[p<<1|1].lazy[i] = tr[p].lazy[i];
            tr[p].lazy[i] = -1;
        }
    }
}
void update(int p,int l,int r,int val,int ops){
    if(l <= tr[p].l && r >= tr[p].r){
        // cout << tr[p].l << ":" << tr[p].r << ":" << l << ":" << r << ":" <<  val << endl;
        if(ops == 0){
            for(int i=0;i<20;++i){
                int bit = val >> i & 1;
                if(bit == 0){
                    tr[p].bits[i] = bit;
                    tr[p].lazy[i] = bit;
                }
            }
        }else if(ops == 1){
            for(int i=0;i<20;++i){
                int bit = val >> i & 1;
                if(bit == 1){
                    tr[p].bits[i] = bit;
                    tr[p].lazy[i] = bit;
                }
            }
        }else{
            for(int i=0;i<20;++i){
                int bit = val >> i & 1;
                tr[p].bits[i] = bit;
                tr[p].lazy[i] = bit;
            }
        }
        return;
    }

    pushdown(p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid){
        update(p<<1,l,r,val,ops);
    }
    if(r > mid){
        update(p<<1|1,l,r,val,ops);
    }
    return;
}
// 单点查询线段树
vector<int> query(int p,int x){
    if(x == tr[p].l && x == tr[p].r){
        return tr[p].bits;
    }
    pushdown(p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(x <= mid){
        return query(p<<1,x);
    }else{
        return query(p<<1|1,x);
    }  
}

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

    build(1,1,n);

    cin >> m;
    for(int i=1;i<=m;++i){
        cin >> l[i];
    }
    for(int i=1;i<=m;++i){
        cin >> r[i];
    }
    cin >> ops;
    for(int i=1;i<=m;++i) cin >> v[i];
    
    for(int i=1;i<=m;++i){
        int left = l[i],right = r[i];
        int val = v[i];
        char op = ops[i-1];
        if(op == '&'){
            update(1,left,right,val,0);
        }else if(op == '|'){
            update(1,left,right,val,1);
        }else if(op == '='){
            update(1,left,right,val,2);
        }
    }

    for(int i=1;i<=n;++i){
        auto vec = query(1,i);
        int res = 0;
        for(int i=0;i<20;++i){
            if(vec[i] == 1){
                res += 1 << i;
            }
        }
        cout << res << " ";
    }
    cout << endl;
}

int main()
{
    IOS;
    int _ = 1;
    while (_--)
    {
         solve();
    }
    return 0;
}