Distorted Fate solution

MornStar · 2024-09-07 18:55:32 · 题解

D.Distorted Fate 题解

出题人题解。

Subtask 0(20 pts)

直接照着题目上的式子模拟就可以了，复杂度 O(qn^2)。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,mod=(1<<30);
int n,q,a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=1,opt,l,r,x;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>x;
            for(int j=l;j<=r;j++)   a[j]^=x;
        }else{
            long long ans=0;
            for(int j=l;j<=r;j++){
                int tmp=0;
                for(int k=l;k<=j;k++)   tmp|=a[k];
                ans=(ans+tmp)%mod;
            }
            cout<<ans<<"\n";
        }
    }
}

Subtask 1(40 pts)

发现 \sum_{i=l}^r\bigcap_{j=l}^i A_j 可以在求值的时候做前缀或，O(n) 回答询问，时间复杂度 O(qn)。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,mod=(1<<30);
int n,q,a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=1,opt,l,r,x;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>x;
            for(int j=l;j<=r;j++)   a[j]^=x;
        }else{
            long long ans=0,tmp=0;
            for(int j=l;j<=r;j++){
                tmp|=a[j];
                ans=(ans+tmp)%mod;
            }
            cout<<ans<<"\n";
        }
    }
}

Subtask 2(60 pts)

既然我们可以使用前缀或统计答案，说明在求和的右端点 i 逐渐向右移的过程中，\bigcap_{j=l}^i A_j 的的值在不断变大，而这种变化最多进行 O(\log w) 次，因为一个数在二进制下最多只有 O(\log w) 位为 0。

所以我们可以得到一个思路，找到答案改变的位置，这个可以很容易地使用线段树上二分做到。

考虑一个好写但时空复杂度不会变的思路，将每个数按二进制位拆开，开 30 颗线段树分别维护每一位，这样，问题就转换成了寻找区间 [l,r] 内的第一个 1。

从第一个 1 的位置开始，直到 r 这一段区间的长度乘上这一位的权值就是这一位的贡献。

线段树节点记录区间内 1 的个数，以及异或标记，这个问题是容易在 O(\log n) 的时间复杂度下解决的。

对每一位询问一次，需要询问 O(\log w) 次，所以单次询问是 O(\log n \log w) 的。

同理，单次修改也要对应修改每一位，时间复杂度也是 O(\log n\log w) 的。

所以总的时间复杂度就是 O(n\log n\log w)。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,C=30,mod=1<<30;
int n,q,a[N];
struct segment_tree{
    struct segment_tree_node{int num;bool tag;}t[N<<2];
    inline int ls(int x){return x<<1;}
    inline int rs(int x){return x<<1|1;}
    inline void f(int p,int l,int r){t[p].num=(r-l+1)-t[p].num,t[p].tag^=1;}
#define mid ((l+r)>>1)
    inline void push_down(int p,int l,int r){
        if(!t[p].tag)   return;
        f(ls(p),l,mid);
        f(rs(p),mid+1,r);
        t[p].tag=0;
    }
    inline void push_up(int x){t[x].num=t[ls(x)].num+t[rs(x)].num;}
    void build(int p,int l,int r){
        if(l==r)    return t[p].num=a[l]&1,void();
        else{
            build(ls(p),l,mid);
            build(rs(p),mid+1,r);
            push_up(p);
        }
    }
    void change(int p,int l,int r,int re_l,int re_r){
        if(re_l<=l&&r<=re_r)    return f(p,l,r);
        else{
            push_down(p,l,r);
            if(re_l<=mid)   change(ls(p),l,mid,re_l,re_r);
            if(mid<re_r)    change(rs(p),mid+1,r,re_l,re_r);
            push_up(p);
        }
    }
    int find(int p,int l,int r,int k){
        if(l==r)    return l;
        else{
            push_down(p,l,r);
            if(t[ls(p)].num>=k) return find(ls(p),l,mid,k);
            else    return find(rs(p),mid+1,r,k-t[ls(p)].num);
        }
    }
    int query(int p,int l,int r,int re_l,int re_r){
        if(re_l<=l&&r<=re_r)    return t[p].num;
        else if(!(r<re_l||l>re_r))  return push_down(p,l,r),query(ls(p),l,mid,re_l,re_r)+query(rs(p),mid+1,r,re_l,re_r);
        else    return 0;
    }
}T[30];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=0;i<C;i++){
        T[i].build(1,1,n+1);
        for(int j=1;j<=n;j++)   a[j]>>=1;
    }
    for(int i=1,opt,l,r,x;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>x;
            for(int j=0;j<C;j++){
                if(x&(1<<j))    T[j].change(1,1,n+1,l,r);
            }
        }else{
            long long ans=0;
            for(int j=0;j<C;j++){
                int num=T[j].query(1,1,n+1,1,l-1),pos=T[j].find(1,1,n+1,num+1);
                ans=(ans+(1ll<<j)*(r-min(r+1,pos)+1ll))%mod;
            }
            cout<<ans<<"\n";
        }
    }
}

Subtask 3(100pts)

Subtask 2 的做法在时间上已经足够优秀了，但是在空间上却不能满足要求。

考虑如何优化。

发现对于一个区间，我们并不关心其中 1 的数量，只需要知道区间里是否有 1 就行了。

我们可以在线段树节点中分别记录区间中这一位或起来的值 x 和与起来的值 y。

考虑异或对区间带来的影响。

当且仅当 x=y=1，区间内全是 1，这时，区间异或会使 x 和 y 均变为 0。
当且仅当 x=y=0，区间内全是 0，这时，区间异或会使 x 和 y 均变为 1。
否则，异或不会改变 x 和 y 的取值。

区间内有 1 等价于 x=1。

这时候，我们就可以顺利进行修改和查询操作了。

这样就可以在线段树上二分了……吗？

考虑一个问题：为什么一定要在线段树中记录 1 的个数呢？

因为这个条件可以具有可差分性，所以可以用线段树上二分求解。

而我们维护的这个信息很明显没有可差分性，那应该怎么办呢？

考虑修改一下线段树上二分的步骤。

在线段树上查询区间 [l,r] 时，将这个区间分成 O(\log n) 段（类似于区间查询）。

按从左往右的顺序遍历每个段，这个可以在线段树上先遍历左子树，后遍历右子树实现，若遍历到这个段时，若区间里没有 1 就直接返回。

否则就在这个区间里线段树上二分找到答案，然后不再遍历后面的区间，因为这个区间内线段树节点维护的信息与询问区间以外的部分无关，所以这时就不需要维护的数据满足可差分性了。

考虑时间复杂度，线段树上查询将区间分为 O(\log n) 段是正常线段树区间查询的 O(\log n)，线段树上二分是 O(\log n)，但由于上面所说的剪枝，线段树的上二分的步骤实际只执行了一次，所以一次这样的操作总复杂度仍然是 O(\log n)。

于是将线段树节点内存储的一个整型变量优化成了两个布尔变量，可以顺利通过 Subtask 3。

时间复杂度仍然是 O(n\log n\log w)。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,C=30,mod=1<<30;
int n,q,a[N];
struct segment_tree{
    struct segment_tree_node{bool x,y,tag;}t[N<<2];
    inline int ls(int x){return x<<1;}
    inline int rs(int x){return x<<1|1;}
    inline void f(int p){
        if(t[p].x==t[p].y)  t[p].x^=1,t[p].y^=1;
        t[p].tag^=1;
    }
#define mid ((l+r)>>1)
    inline void push_down(int p){
        if(!t[p].tag)   return;
        f(ls(p)),f(rs(p));
        t[p].tag=0;
    }
    inline void push_up(int p){
        t[p].x=t[ls(p)].x|t[rs(p)].x;
        t[p].y=t[ls(p)].y&t[rs(p)].y;
    }
    void build(int p,int l,int r){
        if(l==r)    return t[p].x=t[p].y=a[l]&1,void();
        else{
            build(ls(p),l,mid);
            build(rs(p),mid+1,r);
            push_up(p);
        }
    }
    void change(int p,int l,int r,int re_l,int re_r){
        if(re_l<=l&&r<=re_r)    return f(p);
        else{
            push_down(p);
            if(re_l<=mid)   change(ls(p),l,mid,re_l,re_r);
            if(mid<re_r)    change(rs(p),mid+1,r,re_l,re_r);
            push_up(p);
        }
    }
    int find(int p,int l,int r){
        if(l==r)    return l;
        else{
            push_down(p);
            if(t[ls(p)].x)  return find(ls(p),l,mid);
            else    return find(rs(p),mid+1,r);
        }
    }
    int query(int p,int l,int r,int re_l,int re_r){
        if(re_l<=l&&r<=re_r){
            if(t[p].x)  return find(p,l,r);
            else    return -1;
        }else if(!(r<re_l||l>re_r)){
            push_down(p);
            int ansl=query(ls(p),l,mid,re_l,re_r);
            if(ansl!=-1)    return ansl;
            else    return query(rs(p),mid+1,r,re_l,re_r);
        }else   return -1;
    }
}T[30];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=0;i<C;i++){
        T[i].build(1,1,n+1);
        for(int j=1;j<=n;j++)   a[j]>>=1;
    }
    for(int i=1,opt,l,r,x;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>x;
            for(int j=0;j<C;j++){
                if(x&(1<<j))    T[j].change(1,1,n+1,l,r);
            }
        }else{
            long long ans=0;
            for(int j=0;j<C;j++){
                int pos=T[j].query(1,1,n+1,l,r);
                if(pos!=-1) ans=(ans+(1ll<<j)*(r-min(r+1,pos)+1ll))%mod;
            }
            cout<<ans<<"\n";
        }
    }
}