Ynoi数据结构题单练习1-EW帮帮网

文章目录

P9994 [Ynoi Easy Round 2024] TEST_132(分块)
- 思路
P8263 [Ynoi Easy Round 2020] TEST_8(WBLT平衡树+倍增)
P8264 [Ynoi Easy Round 2020] TEST_100(文艺平衡树+分块)
P9990 [Ynoi Easy Round 2023] TEST_90(同P10822 [EC Final 2020] Prof. Pang's sequence)（线段树历史版本和+矩阵乘法）
P9989 [Ynoi Easy Round 2023] TEST_69(线段树区间取gcd+区间查询)
P4145(区间开平方+区间查询)
CF438D(区间取模)
P8512 [Ynoi Easy Round 2021] TEST_152(珂朵莉树+树状数组)
P9991 [Ynoi Easy Round 2023] TEST_107(线段树/树状数组)
P9992 [Ynoi Easy Round 2024] (树上问题，树状数组差分)
P8511 [Ynoi Easy Round 2021] TEST_68(01-Trie)

P9994 [Ynoi Easy Round 2024] TEST_132(分块)

给定平面上 $n$ 个互不相同的点 $x_i,y_i)_{i=1}^n$ ，每个点有点权，初始为 $v_i$ ；

共 $m$ 次操作：

修改操作：给定 $X$ ，将满足 $x_i=X$ 的点的点权 $v_i$ 修改为 $v_i^2$ ；

查询操作：给定 $Y$ ，求满足 $y_i=Y$ 的点的点权 $v_i$ 的和；

答案对 $10^9+7$ 取模。

第一行两个整数 $n, m$ ；

接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i$ ；

接下来 $m$ 行，每行两个整数，修改操作表示为 $1, X$ ，查询操作表示为 $2, Y$ ；

对于 $100\%$ 的数据，满足 $1\le n,m\le 1.2\times10^6$ ， $1\le x_i,y_i\le n$ ， $0\le v_i\le 10^9+6$ ， $1\le X,Y\le n$ 。

思路

看见12s时限，考虑根号分治，对于每个 $X$ 分类

如果当前的 $X$ 列，个数小于等于 $B$ ，那么修改的时候直接暴力修改，维护一个 $s u m$ 数组表示这些数对 $Y$ 的贡献
否则的话，这样的 $X$ 数量不会超过 $\frac{n}{B}$ 个，在查询的时候暴力遍历这些值即可；如果要修改，就打上标记
这样修改的复杂度是 $B$ ，查询的复杂度是 $\frac{n}{B}\log p$ , $p$ 为模数
权衡复杂度 $\frac{n}{B} \log p=B,B=\sqrt{n \log p}$
$\log 1e9 \lt 30$ ，取 $B=\sqrt{30n}$ 左右

int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
void solve(){
	int n,m;
	cin>>n>>m;
	int block=sqrt(30*n);
	vector<int> X(n),Y(n),V(n);
	vector<PII> posx[n+1],posy[n+1];
	for(int i=0;i<n;i++){
		cin>>X[i]>>Y[i]>>V[i];
		posx[X[i]].emplace_back(Y[i],V[i]);
	}
	vector<int> sum(n+1);
	for(int i=0;i<n;i++){
		if(posx[X[i]].size()<=block)sum[Y[i]]=(sum[Y[i]]+V[i])%mod;
		else posy[Y[i]].emplace_back(X[i],V[i]);
	}
	vector<int> tag(n+1,1);
	while(m--){
		int op,x,y;
		cin>>op;
		if(op==1){
			cin>>x;
			if(posx[x].size()<=block){
				for(auto &[y,v]:posx[x]){
					sum[y]=(sum[y]-v+mod)%mod;
					v=v*v%mod;
					sum[y]=(sum[y]+v)%mod;
				}
			}
			else{
				tag[x]=tag[x]*2%(mod-1);
			}
		}
		else{
			cin>>y;
			int ans=sum[y];
			for(auto [x,v]:posy[y])ans=(ans+qpow(v,tag[x]))%mod;
			cout<<ans<<"\n";
		}
	}
}

P8263 [Ynoi Easy Round 2020] TEST_8(WBLT平衡树+倍增)

在这里插入图片描述

看着就非常平衡树，难的是操作1和2

对于操作一，我们可以使用可持久化平衡树，倍增预处理 $2^0,2^1,2^2,...,2^i$ 的平衡树,然后按位遍历k，找到对应的 $2^i$ 合并，如果使用fhq，那么单次合并大概是 $O(\log(siz_x+siz_y))$ ，总复杂度为 $O(\log^2 n)$ ，并且由于大常数的原因，fhq不能在2s通过此题

因此我们改用WBLT平衡树，该算法的合并复杂度为 $O(\log (\frac{w_x}{w_y}))$ 的，那么对于倍增而言， $w_x=w_y$ ，因此理论上为 $\log 1=0$ 即为常数级别的(实际上也是如此，相同区间合并是 $O (1)$ 的)，因此实现上述过程是 $O(\log n)$ 的，并且WBLT常数会小于其他平衡树，因此速度可以得到很大的提升

再来看操作二，我们把 $i$ 看作下标从 $0$ 开始，就是看 $i$ 的二进制是不是奇数个 $1$ 来决定翻转

接下来假设已经求了 $0,2^{i-1}-1]$ 的二进制操作串，如何求 $0,2^i-1]$ ，那么前半部分不变，后半部分必然大于等于 $2^{i-1}$ ，因此第 $i - 1$ 位必然为 $1$ ，其余位和前面的相同，因此操作串是 $0,2^{i-1}-1]$ 的反串
举个例子0,1,2,3的二进制为000,001,010,011，那么对应的操作串为0110(奇数个数则为1，否则为0),4,5,6,7的二进制为100,101,110,111，每个数对应的位置恰好比前面数多一个1，因此操作序列异或1，即取反，为1001，合并在一起 $0,2^3-1]$ 的操作序列就是01101001
这启发我们同时维护一个反串，反串更新同理
因此定义 $f_i$ 表示复制翻转 $2^i$ 的结果， $g^i$ 表示反串，初始 $f_0=s_{l,r},g_0=\overline{s_{l,r}}$
$f_i=f_{i-1}+g_{i-1},g_i=g_{i-1}+f_{i-1}$
然后对于 $k$ 二进制拆分，从大到小枚举每一位，交替使用 $f_i,g_i$ 拼接，不难证明，这是对的，因为后面的操作序列都会多个1，相当于取反

剩下两个操作，就是普通平衡树的操作了

总复杂度 $\log n)$

struct WBLT{
    int ls,rs,sz,sum;
    bool rev;
};
vector<WBLT> t;
int idx,root,T1,T2,T3;
vector<int> pool;
void init(){
    t.emplace_back();
}
int newNode(){
    int u;
    if(pool.size()){
        u=pool.back();
        pool.pop_back();
    }
    else{
        u=t.size();
        t.emplace_back();
    }
    t[u]={0,0,0,0,0};
    return u;
}
int newLeaf(int val){
    int u=newNode();
    t[u].sz=1;
    t[u].sum=val;
    return u;
}
void delNode(int &x){
    pool.push_back(x);
    x=0;
}
void pushup(int u){
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz;
    t[u].sum=t[t[u].ls].sum+t[t[u].rs].sum;
}
int join(int x,int y){
    int u=newNode();
    tie(t[u].ls,t[u].rs)=tie(x,y);
    pushup(u);
    return u;
}
int copy(int p){
    int u=newNode();
    t[u]=t[p];
    return u;
}
int build(int l,int r,vector<int> &a){
    if(l==r)return newLeaf(a[l]&1);
    int mid=l+r>>1;
    return join(build(l,mid,a),build(mid+1,r,a));
}
int pushrev(int p){
    int u=copy(p);
    t[u].rev^=1;
    swap(t[u].ls,t[u].rs);
    return u;
}
void pushdown(int u){
    if(!t[u].rev)return;
    if(t[u].ls)t[u].ls=pushrev(t[u].ls);
    if(t[u].rs)t[u].rs=pushrev(t[u].rs);
    t[u].rev=0;
}
const double alp=1.0-sqrt(2.0)/2.0,delp=alp/(1-alp);
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].sz>=delp*t[y].sz&&t[y].sz>=delp*t[x].sz)return join(x,y);
    if(t[x].sz<=t[y].sz){
        pushdown(y);
        int ls=t[y].ls,rs=t[y].rs;
        if(t[rs].sz>=alp*(t[x].sz+t[y].sz))return merge(merge(x,ls),rs);
        pushdown(ls);
        return merge(merge(x,t[ls].ls),merge(t[ls].rs,rs));
    }
    pushdown(x);
    int ls=t[x].ls,rs=t[x].rs;
    if(t[ls].sz>=alp*(t[x].sz+t[y].sz))return merge(ls,merge(rs,y));
    pushdown(rs);
    return merge(merge(ls,t[rs].ls),merge(t[rs].rs,y));
}
void split(int u,int k,int &x,int &y){
    if(!u||!k){
        x=0;
        y=u;
        return;
    }
    if(k==t[u].sz){
        x=u;
        y=0;
        return;
    }
    pushdown(u);
    if(k<=t[t[u].ls].sz){
        split(t[u].ls,k,x,y);
        y=merge(y,t[u].rs);
    }
    else{
        split(t[u].rs,k-t[t[u].ls].sz,x,y);
        x=merge(t[u].ls,x);
    }
}
int bound(int u,int k){// 找到第k个1的位置
    if(!t[u].ls)return 1;
    pushdown(u);
    if(t[t[u].ls].sum>=k)return bound(t[u].ls,k);
    return t[t[u].ls].sz+bound(t[u].rs,k-t[t[u].ls].sum);
}
void del(int l,int r){
    split(root,r,T1,T2);
    split(T1,l-1,T1,T3);
    root=merge(T1,T2);
}
void work(int l,int r,int k,int op){
    int mx=__lg(k)+1;
    vector<int> flip(mx),nflip(mx);
    split(root,r,T1,T2);
    split(T1,l-1,T1,T3);
    nflip[0]=T3;
    if(op==0){
        for(int i=1;i<mx;i++)nflip[i]=merge(nflip[i-1],nflip[i-1]);
        int tmp=0;
        for(int i=mx-1;i>=0;i--){
            if(k>>i&1)tmp=merge(tmp,nflip[i]);
        }
        root=merge(T1,merge(tmp,T2));
        return;
    }
    flip[0]=pushrev(T3);
    for(int i=1;i<mx;i++){
        flip[i]=merge(flip[i-1],nflip[i-1]);
        nflip[i]=merge(nflip[i-1],flip[i-1]);
    }
    int tmp=0;
    for(int i=mx-1,g=0;i>=0;i--){
        if(k>>i&1){
            if(!g)tmp=merge(tmp,nflip[i]);
            else tmp=merge(tmp,flip[i]);
            g^=1;
        }
    }
    root=merge(T1,merge(tmp,T2));
}
void solve(){
    init();
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    root=build(1,n,a);
    int q;
    cin>>q;
    while(q--){
        int op,l,r,k;
        cin>>op;
        if(op==1){
            cin>>l>>r>>k;
            work(l,r,k,0);
            continue;
        }
        if(op==2){
            cin>>l>>r>>k;
            work(l,r,k,1);
            continue;
        }
        if(op==3){
            cin>>l>>r;
            del(l,r);
            continue;
        }
        cin>>k;
        if(t[root].sum<k)cout<<"-1\n";
        else cout<<bound(root,k)<<"\n";
    }
}

P8264 [Ynoi Easy Round 2020] TEST_100(文艺平衡树+分块)

在这里插入图片描述

考虑分块，对整块预处理 $f_{i,j}$ 表示经过第 $i$ 个块后原来为 $j$ 变成 $f_{i,j}$

可以使用平衡树来求解，维护值的变化

对于小于等于 $a_i$ ，乘上-1再加 $a_i$ ，相当于取反+区间加
大于 $a_i$ 的，区间减去 $a_i$
那么分裂出两颗平衡树后，分别操作，此时不能简单合并(集合有交)，一种方法是维护最大最小值合并，复杂度为 $log^2n$
总复杂度 $\sqrt n+n\log^2n)$

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct FHQ{
    int ls,rs,key,sz,val,mx,mn,add,rev;
} fhq[N];
int root,T1,T2,T3,idx;
int newNode(int val){
    fhq[++idx]={0,0,(int)rng(),1,val,val,val,0,0};
    return idx;
}
void pushadd(int u,int val){
    if(!u)return;
    fhq[u].val+=val;
    fhq[u].add+=val;    
    fhq[u].mx+=val;
    fhq[u].mn+=val;
}
void pushrev(int u){
    if(!u)return;
    fhq[u].rev^=1;
    fhq[u].val*=-1;
    fhq[u].add*=-1;
    fhq[u].mx*=-1;
    fhq[u].mn*=-1;
    swap(fhq[u].mx,fhq[u].mn);
    swap(fhq[u].ls,fhq[u].rs);
}
void pushdown(int u){
    if(!u)return;
    if(fhq[u].rev){
        if(fhq[u].ls)pushrev(fhq[u].ls);
        if(fhq[u].rs)pushrev(fhq[u].rs);
        fhq[u].rev=0;
    }
    if(fhq[u].add){
        if(fhq[u].ls)pushadd(fhq[u].ls,fhq[u].add);
        if(fhq[u].rs)pushadd(fhq[u].rs,fhq[u].add);
        fhq[u].add=0;
    }
}
void pushup(int u){
    fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
    fhq[u].mx=fhq[u].mn=fhq[u].val;
    if(fhq[u].ls){
        fhq[u].mx=max(fhq[u].mx,fhq[fhq[u].ls].mx);
        fhq[u].mn=min(fhq[u].mn,fhq[fhq[u].ls].mn);
    }
    if(fhq[u].rs){
        fhq[u].mx=max(fhq[u].mx,fhq[fhq[u].rs].mx);
        fhq[u].mn=min(fhq[u].mn,fhq[fhq[u].rs].mn);
    }
}
void split(int u,int val,int &x,int &y){
    if(!u){
        x=y=0;
        return;
    }
    pushdown(u);
    if(fhq[u].val>val){
        y=u;
        split(fhq[u].ls,val,x,fhq[u].ls);
    }
    else{
        x=u;
        split(fhq[u].rs,val,fhq[u].rs,y);
    }
    pushup(u);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    pushdown(x);
    pushdown(y);
    if(fhq[x].key>fhq[y].key){
        fhq[x].rs=merge(fhq[x].rs,y);
        pushup(x);
        return x;
    }
    fhq[y].ls=merge(x,fhq[y].ls);
    pushup(y);
    return y;
}
int join(int x,int y){// 有交合并，最慢单次O(log^2n)
    int z=0,tmp;
    while(x&&y){
        if(fhq[x].mn>fhq[y].mn)swap(x,y);
        split(x,fhq[y].mn,tmp,x);
        z=merge(z,tmp);
    }
    z=merge(z,x);
    z=merge(z,y);
    return z;
}
void dfs(int u){
    pushdown(u);
    if(fhq[u].ls)dfs(fhq[u].ls);
    if(fhq[u].rs)dfs(fhq[u].rs);
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int block=4000,tot=(n+block-1)/block;
    vector<int> be(n+1),L(tot+1),R(tot+1);
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(i*block,n);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
    }
    vector<int> t(M+1);
    for(int i=0;i<=M;i++){
        t[i]=newNode(i);
        root=merge(root,t[i]);
    }
    vector<FHQ> T(idx+1);
    auto change=[&](int d){
        int x,y;
        split(root,d,x,y);
        pushrev(x);
        pushadd(x,d);
        pushadd(y,-d);
        root=join(x,y);
    };
    vector f(tot+1,vector<int>(N));
    int rt=root;
    for(int i=1;i<=idx;i++)T[i]=fhq[i];
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=idx;j++){
            fhq[j]=T[j];
        }
        root=rt;
        for(int j=L[i];j<=R[i];j++){
            change(a[j]);
        }
        dfs(root);
        for(int j=0;j<=M;j++)f[i][j]=fhq[t[j]].val;
    }
    int ans=0;
    while(m--){
        int l,r,v;
        cin>>l>>r>>v;
        l^=ans,r^=ans,v^=ans;
        if(be[l]==be[r]){
            for(int i=l;i<=r;i++)v=abs(v-a[i]);
            cout<<(ans=v)<<"\n";
            continue;
        }
        for(int i=l;i<=R[be[l]];i++)v=abs(v-a[i]);
        for(int i=be[l]+1;i<be[r];i++)v=f[i][v];
        for(int i=L[be[r]];i<=r;i++)v=abs(v-a[i]);
        cout<<(ans=v)<<"\n";
    }
}

P9990 [Ynoi Easy Round 2023] TEST_90(同P10822 [EC Final 2020] Prof. Pang’s sequence)（线段树历史版本和+矩阵乘法）

在这里插入图片描述
首先看简单版本，考虑离线，从1到n枚举，维护以当前 $i$ 为右端点的合法左端点， $0/1$ 表示是否合法，可以发现影响的范围为 $lst_{a_i},i]$ 这些范围的数的个数都会+1，在模2意义下就是翻转。对于区间查询我们就是查询区间的历史版本和

一个简单的方法就是矩阵表示，每个节点维护矩阵 $cnt_0,cnt_1,ans]$ 分别表示 $0/1$ 个数和历史版本和

那么对于翻转操作，应该要变成 $cnt_1,cnt_0,cnt_0+ans]$ ，可以构造出矩阵
$\begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 0 &1 \end{pmatrix}$
不翻转的贡献是 $cnt_0,cnt_1,cnt_1+ans]$ ，即乘上矩阵
$\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 1\\ 0 & 0 &1 \end{pmatrix}$
然后初始化叶子节点为 $[1, 0, 0]$
实现一个区间乘，区间查询的线段树即可，复杂度为 $\log n \cdot 3^3)$
这个 $3^3$ 无法被忽略，矩阵乘法常数太大的原因，时间和空间都无法接受，需要一些卡常技巧

一开始是MLE，换成如下的模板类可以减少空间，能过洛谷的数据，但是过不了cf的

template<int X,int Y>
struct Matrix{
    LL a[X][Y];
    Matrix(){
        memset(a,0,sizeof a);  
    }
    void set(const vector<vector<int>> &v){
        for(int i=0;i<X;i++){
            for(int j=0;j<Y;j++)a[i][j]=v[i][j];
        }
    }
    template<int _X,int _Y>
    Matrix<X,_Y> operator*(const Matrix<_X,_Y> &t){
        Matrix<X,_Y> res;
        for(int k=0;k<Y;k++){
            for(int i=0;i<X;i++){
                for(int j=0;j<_Y;j++)res.a[i][j]+=a[i][k]*t.a[k][j];
            }
        }
        return res;
    }
    Matrix<X,Y> operator+(const Matrix<X,Y> &t){
        Matrix<X,Y> res;
        for(int i=0;i<X;i++){
            for(int j=0;j<Y;j++)res.a[i][j]=a[i][j]+t.a[i][j];
        }
        return res;
    }
};

将矩阵乘法循环展开，速度会得到质的飞跃

struct Vec{
    int x00,x01,x02;
};
struct Matrix{
    int x00,x01,x02,x10,x11,x12,x20,x21,x22;
};
Matrix operator *(const Matrix &a,const Matrix &b){
    Matrix res;
    res.x00=a.x00*b.x00+a.x01*b.x10+a.x02*b.x20;
    res.x01=a.x00*b.x01+a.x01*b.x11+a.x02*b.x21;
    res.x02=a.x00*b.x02+a.x01*b.x12+a.x02*b.x22;
    
    res.x10=a.x10*b.x00+a.x11*b.x10+a.x12*b.x20;
    res.x11=a.x10*b.x01+a.x11*b.x11+a.x12*b.x21;
    res.x12=a.x10*b.x02+a.x11*b.x12+a.x12*b.x22;
    
    res.x20=a.x20*b.x00+a.x21*b.x10+a.x22*b.x20;
    res.x21=a.x20*b.x01+a.x21*b.x11+a.x22*b.x21;
    res.x22=a.x20*b.x02+a.x21*b.x12+a.x22*b.x22;
    
    return res;
}
Vec operator *(const Vec &a,const Matrix &x){
    Vec res;
    res.x00=a.x00*x.x00+a.x01*x.x10+a.x02*x.x20;
    res.x01=a.x00*x.x01+a.x01*x.x11+a.x02*x.x21;
    res.x02=a.x00*x.x02+a.x01*x.x12+a.x02*x.x22;
    return res;
}
Vec operator +(const Vec &a,const Vec &b){
    return {a.x00+b.x00, a.x01+b.x01, a.x02+b.x02};
}
Matrix I={1,0,0,0,1,0,0,0,1};
Matrix A={0,1,1,1,0,0,0,0,1};
Matrix B={1,0,0,0,1,1,0,0,1};
struct SegmentTree{
    struct Node{
        Vec m;
        Matrix tag=I;
        bool lazy=0;
    };
    vector<Node> t;
    void init(int n){
        t=vector<Node>(n<<2);
        build(1,1,n);
    }
    void pushup(int p){
        t[p].m=t[p<<1].m+t[p<<1|1].m;
    }
    void pushtag(int p,const Matrix &x){
        t[p].m=t[p].m*x;
        t[p].tag=t[p].tag*x;
        t[p].lazy=1;
    }
    void pushdown(int p){
        if(t[p].lazy){
            pushtag(p<<1,t[p].tag);
            pushtag(p<<1|1,t[p].tag);
            t[p].lazy=0;
            t[p].tag=I;
        }
    }
    void build(int p,int l,int r){
        if(l==r){
            t[p].m={1,0,0};
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int ql,int qr,const Matrix &x){
        if(ql<=l&&r<=qr){
            pushtag(p,x);
            return;
        }
        pushdown(p);
        int mid=l+r>>1;
        if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);  
        if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,x);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return t[p].m.x02;
        pushdown(p);
        int res=0,mid=l+r>>1;
        if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
        if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
        return res;
    }
};
void solve(){
    int n;
    cin>>n;
    SegmentTree t;
    t.init(n);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int m;
    cin>>m;
    vector<PII> Que[n+1];
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        Que[r].emplace_back(l,i);
    }
    vector<int> lst(n+1);
    for(int i=1;i<=n;i++){
        t.modify(1,1,n,lst[a[i]]+1,i,A);
        if(lst[a[i]])t.modify(1,1,n,1,lst[a[i]],B);
        lst[a[i]]=i;
        for(auto &[l,id]:Que[i]){
            ans[id]=t.query(1,1,n,l,i);
        }
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

这样就可以通过 $5 e 5$ 的数据了，但是Ynoi的 $1 e 6$ 的数据仍然无法通过
维护区间历史版本问题，就要上吉司机线段树了
考虑维护历史版本和 $h s$ ，翻转标记 $re v$ ， $0/1$ 的个数 $cnt_0,cnt_1$ ， $0/1$ 的贡献标记 $tag_0,tag_1$

先下放翻转标记，再下放贡献标记

翻转： $rev \oplus 1,swap(cnt_0,cnt_1),swap(tag_0,tag_1)$
贡献： $hs=hs+cnt_0*tag_{p,0}+cnt_1*tag_{p,1},tag_0=tag_0+tag_{p,0},tag_1=tag_1+tag_{p,1}$

struct SegmentTree{
    struct Node{
        int hs,cnt0,cnt1,tag0,tag1;
        bool rev;
    };
    vector<Node> t;
    void init(int n){
        t=vector<Node>(n<<2);
        build(1,1,n);
    }
    void pushup(int p){
        t[p].hs=t[p<<1].hs+t[p<<1|1].hs;
        t[p].cnt0=t[p<<1].cnt0+t[p<<1|1].cnt0;
        t[p].cnt1=t[p<<1].cnt1+t[p<<1|1].cnt1;
    }
    void pushrev(int p){
        swap(t[p].cnt0,t[p].cnt1);
        swap(t[p].tag0,t[p].tag1);
        t[p].rev^=1;
    }
    void pushtag(int p,int tag0,int tag1){
        t[p].hs+=tag0*t[p].cnt0+tag1*t[p].cnt1;
        t[p].tag0+=tag0;
        t[p].tag1+=tag1;
    }
    void pushdown(int p){
        if(t[p].rev){
            pushrev(p<<1);
            pushrev(p<<1|1);
            t[p].rev=0;
        }
        if(t[p].tag0||t[p].tag1){
            pushtag(p<<1,t[p].tag0,t[p].tag1);
            pushtag(p<<1|1,t[p].tag0,t[p].tag1);
            t[p].tag0=0;
            t[p].tag1=0;
        }
    }
    void build(int p,int l,int r){
        t[p]={0,0,0,0,0,0};
        if(l==r){
            t[p].cnt0=1;
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int ql,int qr,int op){
        if(ql<=l&&r<=qr){
            if(op)pushrev(p);
            pushtag(p,0,1);
            return;
        }
        pushdown(p);
        int mid=l+r>>1;
        if(ql<=mid)modify(p<<1,l,mid,ql,qr,op);
        if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,op);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return t[p].hs;
        pushdown(p);
        int res=0,mid=l+r>>1;
        if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
        if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
        return res;
    }
};
void solve(){
    int n;
    cin>>n;
    SegmentTree t;
    t.init(n);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int m;
    cin>>m;
    vector<PII> Que[n+1];
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        Que[r].emplace_back(l,i);
    }
    vector<int> lst(n+1);
    for(int i=1;i<=n;i++){
        t.modify(1,1,n,lst[a[i]]+1,i,1);
        if(lst[a[i]])t.modify(1,1,n,1,lst[a[i]],0);
        lst[a[i]]=i;
        for(auto &[l,id]:Que[i]){
            ans[id]=t.query(1,1,n,l,i);
        }
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

P9989 [Ynoi Easy Round 2023] TEST_69(线段树区间取gcd+区间查询)

在这里插入图片描述
一个经典的结论：
$\gcd(x,y)=x$ 或者 $\gcd(x,y) \leq \frac{x}{2}$

维护区间lcm，如果 $x\%lcm=0$ 说明没有影响，退出；否则暴力更新

线段树每个节点最多更新 $\log V$ 次

复杂度为 $\log n \log V)$

int a[N];
__int128 lcm(__int128 a,__int128 b){
    return a/__gcd(a,b)*b;
}
struct SegmentTree{
    struct Node{
        __int128 lcm;
        int sum;
    };
    vector<Node> t;
    void init(int n){
        t=vector<Node>(n<<2);
        build(1,1,n);
    }
    void pushup(int p){
        t[p].lcm=lcm(t[p<<1].lcm,t[p<<1|1].lcm);
        if(t[p].lcm>2e18)t[p].lcm=2e18;
        t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
        t[p].sum%=1ll<<32;
    }
    void build(int p,int l,int r){
        if(l==r){
            t[p].lcm=t[p].sum=a[l];
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int ql,int qr,int k){
        if(ql<=l&&r<=qr){
            if(k%t[p].lcm==0)return;
            if(l==r){
                t[p].lcm=t[p].sum=__gcd(t[p].sum,k);
                return;
            }
        }
        int mid=l+r>>1;
        if(ql<=mid)modify(p<<1,l,mid,ql,qr,k);
        if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,k);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return t[p].sum;
        int res=0,mid=l+r>>1;
        if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
        if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
        res%=1ll<<32;
        return res;
    }
} seg;
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    seg.init(n);
    while(m--){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            seg.modify(1,1,n,l,r,x);
        }else{
            cout<<seg.query(1,1,n,l,r)<<"\n";
        }
    }
}

P4145(区间开平方+区间查询)

值域为 $1 e 12$ ，最多开6次变成1，维护区间最大值，如果最大值不为1则暴力修改

复杂度 $\log n)$

CF438D(区间取模)

一个道理

P8512 [Ynoi Easy Round 2021] TEST_152(珂朵莉树+树状数组)

在这里插入图片描述
首先很显然的是总颜色段是 $O (n)$ 的，可以使用珂朵莉树ODT来维护颜色段，因为只有assign，复杂度可以保证

把所有询问离线

然后对于时间序列，用树状数组维护每个时间的操作在当前时间的贡献，每次查询就是大于等于 $l$ 的时间的颜色段总和

时间复杂度 $O(n\log n)$

template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_=0){
        init(n,identity);
    }
    void init(int n_,T identity_=0){
        n=n_;
        c.assign(n+1,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
Fenwick<int,decltype([](const int &a,const int &b){return a+b;})> fw;
struct Node{
    int l,r,t;
    mutable int v;//永远可变，可以直接修改set的值中的v，而不用重新插入
    bool operator<(const Node&t)const{
        return l<t.l;
    }
};
set<Node> odt;
auto split(int x){
    auto it=odt.lower_bound(Node(x,0,0));
    if(it!=odt.end()&&it->l==x)return it;
    it--;
    auto [l,r,t,v]=*it;
    odt.erase(it);
    odt.insert(Node(l,x-1,t,v));
    return odt.insert(Node(x,r,t,v)).first;
}
void assign(int l,int r,int t,int v){
    auto R=split(r+1),L=split(l);// 先R再L防止迭代器擦除
    for(auto it=L;it!=R;it++){
        if(it->t)fw.add(it->t,-it->v*(it->r-it->l+1));
    }
    odt.erase(L,R);
    odt.insert(Node(l,r,t,v));
    fw.add(t,v*(r-l+1));
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    odt.insert(Node(1,n,0,0));
    fw.init(n+1,0);
    vector<array<int,3>> op(n);
    for(auto &[l,r,v]:op)cin>>l>>r>>v;
    vector<int> res(q);
    vector<PII> Que[n];
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        Que[r-1].emplace_back(l-1,i);
    }
    for(int i=0;i<n;i++){
        auto [l,r,v]=op[i];
        assign(l,r,i+1,v);
        for(auto [ql,id]:Que[i]){
            res[id]=fw.query(i+1)-fw.query(ql);
        }
    }
    for(int i=0;i<q;i++)cout<<res[i]<<"\n";
}

P9991 [Ynoi Easy Round 2023] TEST_107(线段树/树状数组)

在这里插入图片描述
题目可以转变为将 $[l, r]$ 的一种颜色去掉，然后找最大的连续区间

很明显的trick离线，扫描线

三种情况

$p os$ 是该颜色在 $[l, r]$ 的第一次出现的位置，那么贡献为 $p os - l$
$p os$ 是最后一次出现的位置，贡献为 $r - p os$
颜色至少出现两次，记为 $p os 1, p os 2$ ，贡献为 $p os 2 - p os 1 - 1$

前面两种非常好解决，从左到右从右到左分别做一遍即可，用set就行
第三种，我们每次遇到 $a_i$ ，就把 $lst_{a_i}+1$ 的位置答案更新成 $i-lst_{a_i}-1$ ，然后变成单点修改区间查询，线段树或者树状数组

复杂度 $\log n)$

有点卡常，懒得卡了，下面是70分的做法

template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_=0){
        init(n,identity);
    }
    void init(int n_,T identity_=0){
        n=n_;
        c.assign(n+1,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
Fenwick<int,decltype([](const int &a,const int &b){return max(a,b);})> fw;
int a[N],pos[N],ans[N];
vector<PII> Que[N],que[N];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int mx=*max_element(a+1,a+n+1);
    fw.init(n,0);
    set<int> lst;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        Que[r].emplace_back(l,i);
        que[l].emplace_back(r,i);
    }
    for(int i=1;i<=n;i++){
        if(pos[a[i]]){
            lst.erase(pos[a[i]]);
            if(pos[a[i]]+1<i)fw.add(pos[a[i]]+1,i-pos[a[i]]-1,1);
        }
        lst.insert(i);
        pos[a[i]]=i;
        for(auto [l,id]:Que[i]){
            int res=0;
            if(lst.size()){
                auto it=lst.lower_bound(l);
                if(it!=lst.end()){
                    res=max(res,i-*it);
                }
            }
            if(l+1<i)res=max(res,fw.query(l+1,1));
            ans[id]=res;
        }
    }
    for(int i=1;i<=n;i++)pos[a[i]]=0;
    lst.clear();
    for(int i=n;i>=1;i--){
        if(pos[a[i]])lst.erase(pos[a[i]]);
        lst.insert(i);
        pos[a[i]]=i;
        for(auto &[r,id]:que[i]){
            if(lst.size()){
                auto it=lst.upper_bound(r);
                if(it!=lst.begin()){
                    it--;
                    ans[id]=max(ans[id],*it-i);
                }
            }
        }
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

P9992 [Ynoi Easy Round 2024] (树上问题，树状数组差分)

在这里插入图片描述

考虑离线，分别考虑每颗子树
对于 $u$ 子树下的一个节点 $v$ ，三种情况
- $dep_u+d \geq mxdep_v$ ,此时贡献为 $mxdep_v-dep_v+1$
- $dep_v \leq dep_u+d \lt mxdep_v$ ，此时贡献为 $dep_u+d-dep_v+1$
- $dep_u+d \lt dep_v$ ，无贡献

上面的贡献可以看作对一个区间作加法，查询的时候就是单点查询 $dep_u+d$ ，可以用三颗树状数组维护差分

至于如何只考虑当前子树的贡献，一个经典的做法是树上启发式合并，复杂度为 $O(n\log^2n)$ ，但是可以发现贡献查询非常简单，因此可以在一开始未遍历子树时作一次减法查询，减去子树外的贡献，复杂度为 $\log n)$

template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_=0){
        init(n,identity);
    }
    void init(int n_,T identity_=0){
        n=n_;
        c.assign(n+1,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
Fenwick<int,decltype([](const int &a,const int &b){return a+b;})> t1,t2,t3;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n+1);
    for(int i=2;i<=n;i++){
        int p;
        cin>>p;
        adj[p].push_back(i);
    }
    vector<vector<PII>> Que(n+1);
    vector<int> ans(m);
    t1.init(n);
    t2.init(n);
    t3.init(n);
    for(int i=0;i<m;i++){
        int w,d;
        cin>>w>>d;
        Que[w].emplace_back(d,i);
    }
    vector<int> dep(n+1),mxdep(n+1);
    auto dfs1=[&](auto &&self,int u,int fa)->void{
        dep[u]=dep[fa]+1;
        mxdep[u]=dep[u];
        for(auto v:adj[u]){
            self(self,v,u);
            mxdep[u]=max(mxdep[u],mxdep[v]);
        }
    };
    dfs1(dfs1,1,0);
    auto dfs=[&](auto &&self,int u)->void{
        for(auto [d,id]:Que[u]){
            int D=min(n,dep[u]+d);
            int res=t1.query(D);
            res+=t2.query(D)*(dep[u]+d+1)-t3.query(D);
            ans[id]=-res;
        }
        for(auto v:adj[u]){
            self(self,v);
        }
        t1.add(mxdep[u],mxdep[u]-dep[u]+1);
        t2.add(dep[u],1);
        t2.add(mxdep[u],-1);
        t3.add(dep[u],dep[u]);
        t3.add(mxdep[u],-dep[u]);
        for(auto [d,id]:Que[u]){
            int D=min(n,dep[u]+d);
            int res=t1.query(D);
            res+=t2.query(D)*(dep[u]+d+1)-t3.query(D);
            ans[id]+=res;
        }
    };
    dfs(dfs,1);
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

P8511 [Ynoi Easy Round 2021] TEST_68(01-Trie)

在这里插入图片描述

考虑全局最大，那么就是01-trie板子题

第一眼又是dsu on tree，但是发现不可做(如果是子树内则可做)

观察到有很多答案等于全局最大值，设取全局最大值的两个点为 $x, y$ ，只有 $1$ 到 $x$ 和 $1$ 到 $y$ 的路径需要算，那么就是一条链
从起点开始就可以做到只加不减，动态维护最大值，分别对两条链跑一次答案即可

复杂度 $\log V)$

int tr[N][2],id[N],idx;
void insert(LL x,int _id){
    int p=0;
    for(int i=62;i>=0;i--){
        int c=x>>i&1;
        if(!tr[p][c])tr[p][c]=++idx;
        p=tr[p][c];
    }
    id[p]=_id;
}
pair<LL,int> query(LL x){
    int p=0;
    LL res=0;
    for(int i=62;i>=0;i--){
        int c=x>>i&1;
        if(tr[p][c^1]){
            res+=1ll<<i;
            p=tr[p][c^1];
        }
        else p=tr[p][c];
    }
    return {res,id[p]};
}
void clear(){
    for(int i=0;i<=idx;i++)tr[i][0]=tr[i][1]=id[i]=0;
    idx=0;
}
void solve(){
    int n;
    cin>>n;
    vector<vector<int>> adj(n+1);
    vector<int> par(n+1),tag(n+1),ne(n+1);
    vector<LL> Ans(n+1);
    for(int i=2;i<=n;i++){
        int p;
        cin>>p;
        par[i]=p;
        adj[p].push_back(i);
    }
    vector<LL> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],insert(a[i],i);
    int idx,idy;
    LL res=0;
    for(int i=1;i<=n;i++){
        auto [ans,id]=query(a[i]);
        if(ans>res){
            res=ans;
            idx=id;
            idy=i;
        }
    }
    int x=idx;
    while(x!=1){
        tag[x]=1;
        ne[par[x]]=x;
        x=par[x];
    }
    tag[1]=1;
    clear();
    LL now=0;
    auto dfs=[&](auto &&self,int u)->void{
        if(tag[u])return;
        insert(a[u],u);
        now=max(now,query(a[u]).F);
        for(auto v:adj[u]){
            self(self,v);
        }
    };
    auto upd=[&](int ed){
        int x=1;
        while(x!=ed){
            Ans[x]=now;
            tag[x]=0;
            dfs(dfs,x);
            x=ne[x];
        }
        Ans[x]=now;
    };
    upd(idx);
    x=idy;
    while(x!=1){
        tag[x]=1;
        ne[par[x]]=x;
        x=par[x];
    }
    tag[1]=1;
    clear();
    now=0;
    upd(idy);
    while(idx!=1){
        tag[idx]=1;
        idx=par[idx];
    }
    while(idy!=1){
        tag[idy]=1;
        idy=par[idy];
    }
    tag[1]=1;
    for(int i=1;i<=n;i++){
        if(tag[i])cout<<Ans[i]<<"\n";
        else cout<<res<<"\n";
    }
}

Ynoi数据结构题单练习1