P6587 超超的序列 加强 题解

· · 题解

P6587 超超的序列 加强 题解

题目大意

传送门。

解题思路

看到本题强制在线之后，大部分同学的乱搞之心可以死了。

本题其实是让你按某种规律去做区间修改和区间求和，而这个规律显然是 i\equiv y\pmod {2^x}。

考虑研究 i\equiv y\pmod {2^x} 的性质。

我们可以把 i 和 y 转成二进制来看。

随便举一组 i,x,y：x=19(1011_2),y=3(11_2),x=2。

此时，这一组 i,x,y 满足 i\equiv y\pmod {2^x} 的性质。

经观察可得，i 和 y 在二进制下的后 2 位相同。

由二进制数字的性质可以得出，我们实际上是把所有下标 i 的二进制表示中，后 x 位与 y 在二进制表示中的后 x 位相同的 a_i 进行修改。

如何高效地处理呢？

我们考虑 0-1 trie（不知道的同学可以点蓝字去看看）。

上面所述满足条件的 i，其实组成了 0-1 trie 中根的深度为 x（假定根的深度为 0）的一颗子树，从根到达该子树的根的路径上，按顺序用边权值组成的 0-1 串与 y 的二进制后 x 位相同。

查询与修改均为在 0-1 trie 中的某棵子树的整体进行。

我们只需要在 0-1 trie 中引入懒标记的思想，就可以做到查询与修改的时间复杂度均为 O(x) 了。

如果此时你仍然不知道代码该如何编写，那么请先阅读有关线段树的内容。

总的时间复杂度约为 O(n\log{n})。

参考代码

#include<iostream>
using namespace std;
#define int long long
const int N=5e6+10;
struct node{
    int sum,laz,all;
    int son[3];
}trie[N];
int root,cnt;
void ins(int &pos,int num,int sb,int zyh){
    if(!pos) pos=++cnt;
    trie[pos].sum+=zyh;
    trie[pos].all++;
    if(num==31) return;
    if(sb&(1ll<<(num+1))) ins(trie[pos].son[1],num+1,sb,zyh);
    else ins(trie[pos].son[0],num+1,sb,zyh);
}
void push_down(int pos){
    if(trie[pos].son[0]){
        trie[trie[pos].son[0]].sum+=trie[pos].laz*trie[trie[pos].son[0]].all;
        trie[trie[pos].son[0]].laz+=trie[pos].laz;
    }
    if(trie[pos].son[1]){
        trie[trie[pos].son[1]].sum+=trie[pos].laz*trie[trie[pos].son[1]].all;
        trie[trie[pos].son[1]].laz+=trie[pos].laz;
    }
    trie[pos].laz=0;
}
void push_up(int pos){
    int lson=trie[pos].son[0],rson=trie[pos].son[1];
    trie[pos].sum=trie[lson].sum+trie[rson].sum;
}
void upd(int pos,int num,int hope,int sb,int yy){
    if(!pos) return;
    if(num==hope){
        trie[pos].sum+=trie[pos].all*yy;
        trie[pos].laz+=yy;
        return;
    }
    push_down(pos);
    if(sb&(1ll<<(num+1))) upd(trie[pos].son[1],num+1,hope,sb,yy);
    else upd(trie[pos].son[0],num+1,hope,sb,yy);
    push_up(pos);
}
int ask(int pos,int num,int hope,int sb){
    if(!pos) return 0;
    if(num==hope) return trie[pos].sum;
    push_down(pos);
    if(sb&(1ll<<(num+1))) return ask(trie[pos].son[1],num+1,hope,sb);
    else return ask(trie[pos].son[0],num+1,hope,sb);
}
int a,n,m,lastans;
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a;
        ins(root,-1,i,a);
    }
    while(m--){
        int op,x,y,v;
        cin>>op>>x>>y;
        op=(op+lastans)%2+1;
        if(op==1){
            cin>>v;
            upd(root,-1,x-1,y%(1ll<<x),v);
        }else{
            lastans=ask(root,-1,x-1,y%(1ll<<x));
            cout<<lastans<<'\n';
        }
    }
    return 0;
}

本代码可以通过评测。

Written by toolong114514 on 2024/4/5.