ds简单题选讲

2025/6/17 OI 题解数据结构

题单见这里。
非本校学生可以见这里。

前言

折叠块点击可以展开，再点可以收缩。
有些代码比较宽，可以在代码框内按一下鼠标中键，然后将鼠标往右挪来看右边的内容，再按一下鼠标中键即可恢复原状。
如果折叠块打不开，刷新一下即可。
我知道 ds 难调，所以给了你们参考代码，但还是建议不要看参考代码。如果确实调不出来，可以用参考代码来对拍，但是绝对不要直接抄或者照着改。
有的题目可能比较难，我大部分题目都给了 hint，大家还是尽量努力思考一下，其实这些题基本都没什么思维难度的。

T1

P5673 「SWTR-2」Picking Gifts

题意简述

$n$ 个物品，每种物品 $i$ 的种类为 $v_{i}$，价值为 $w_{i}$。定义一段区间的价值为：对于再该区间内的每种类型的物品，仅有 从右往左 的前 $k-1$ 个会产生该物品的价值。$q$ 次询问，每次给出一段区间 $[l,r]$，问其价值。给定 $n,k,q$。

$n\le 10^6,q\le 5\times10^5,1\le v_{i}\le n,1\le w_{i}\le 2000$。

思路

Solution

这道题比较简单，就不放 Hint 了。
不难想到类似于 P1972 [SDOI2009] HH的项链的做法，先将询问离线下来，对右端点做扫描线，维护对于当前右端点，所有左端点的答案。

考虑每种物品造成的贡献，对每种类型维护一个队列，当当前的右端点为类型为 $v_{i}$ 的物品时，将其假如类型为 $v_{i}$ 的队列，不难发现其能产生的左端点是 $[1,r]$。
假如当前 $v_{i}$ 的队列里的元素已经超过 $k$ 个了，那么就得去掉队首的元素，队首的元素能产生贡献的左端点区间为 $1$ 到该点的位置。
发现这是一个区间加，单点查的操作，使用差分变成单点加，区间和。就可以使用 BIT 轻松实现了。线段树可能会被卡，我没试过。

不难发现，每种元素最多进入某一个队列，因此时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

注意

如果你像我一样开了 $n$ 个 queue，你交上去会发现 MLE，queue 的内存消耗是较大的，哪怕是空的 queue 空间消耗也是很大的。
直接改成 vector 来模拟队列即可。

参考代码

// Problem: P5673 「SWTR-2」Picking Gifts
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5673
// Memory Limit: 512 MB
// Time Limit: 500000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,k,P[MAXN],v[MAXN],t[MAXN],ans[MAXN],pos[MAXN];
vector<int> p[MAXN],q[MAXN];
struct node{
    int l,r,id;
}que[MAXN];

int lowbit(int x){return x&(-x);}

void update(int pos,int val){
    while(pos<=n){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=0;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

signed main(){
    read(n,m,k);
    for(int i=1;i<=n;i++) read(P[i]);
    for(int i=1;i<=n;i++) read(v[i]);
    for(int i=1;i<=m;i++) read(que[i].l,que[i].r),que[i].id=i,p[que[i].r].push_back(i);
    for(int i=1;i<=n;i++){
        q[P[i]].push_back(i);
        update(i,v[i]);
        if(q[P[i]].size()>=k) update(q[P[i]][pos[P[i]]],-v[q[P[i]][pos[P[i]]]]),pos[P[i]]++;
        for(int j:p[i]) ans[j]=query(i)-query(que[j].l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

T2

P10463 Interval GCD

写到一半才发现这道题先前讲过了，见每周好题分享 Week2 T1。

T3

Luogu：AT_abc371_f [ABC371F] Takahashi in Narrow Road
AtCoder：F - Takahashi in Narrow Road

题意简述

在数轴上有 $N$ 个人，每个人的坐标为 $X_i$。

你可以执行以下操作任意次：

选择一个人。如果目的地没有其他人，将这个人向左或向右移动 $1$ 米。有 $Q$ 个任务，每个任务内容如下：

将第 $T_i$ 个人移动到位置 $G_i$。

你需要按顺序完成所有任务，求最少进行多少次操作。

$1\leq N\leq2\times10 ^ 5$
$0\leq X _ 1\lt X _ 2\lt\dotsb\lt X _ N\leq10 ^ 8$
$1\leq Q\leq2\times10 ^ 5$
$1\leq T _ i\leq N (1\leq i\leq Q)$
$0\leq G _ i\leq10 ^ 8 (1\leq i\leq Q)$

碎碎念

这场 ABC 当时我打了，这道题当时就只会 $O(n^2)$ 的，后面没有改题，然后省选 D2T1 几乎是原题，然后我在场上还是只会 $O(n^2)$ 的……所以大家一定要及时改题啊。

思路

Hint1

不妨也先想想 $O(n^2)$ 的做法，并考虑优化。

Hint2

发现一个人要到他的目标位置，需要把他到终点的路径上的其他人都先往后或者往前赶。但是发现我们需要赶多少人是不确定的，据此你想到了什么？

Hint3

假设往右走，发现，对于我们当前考虑的第 $i$ 个人，后面的某个人 $j$，其会被赶的必要条件是 $x_{j}<t_{i}+j-i$。所以会被赶的人与不会被赶的人之间有一条分界线，利用这个条件即可二分找出这个位置。

Hint4

发现我们需要将某段区间赋值成一个等差数列，这个可以使用线段树来维护。
具体的：我们需要维护和来计算走了多少步，对于等差数列，我们维护其首项即可，因为公差都是 $1$。
那么现在你的时间复杂度就是 $O(nlog^2n)$ 了，AT 似乎可以通过了。

Solution

我们并不需要对于所有的查询都重新跑一次线段树，直接在线段树上二分即可。时间复杂度 $O(n\log n)$

参考代码

注意，代码均为 2025 联合省选 D2T1 的代码，对于此题修改一点就好了，如果你听懂了，改起来是容易的。

$O(n^2)$

参考代码

此代码为省选场上我的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int res=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
const int MAXN=2e5+10;
const int mod=998244353;

int c,T,n,t,a[MAXN],y[MAXN];
bool judge;
struct node{
    int a,b,t,id;
}p[MAXN];

bool cmp(node n1,node n2){
    return n1.t<n2.t;
}

int find(int id,int from,int to){
    int tot=0;
    if(from<to){
        int pos=upper_bound(a+1,a+n+1,to)-a-1;
        for(int j=pos;j>id;j--) tot+=find(j,a[j],to+(j-id));
    }
    if(from>to){
        int pos=lower_bound(a+1,a+n+1,to)-a;
        for(int j=pos;j<id;j++) tot+=find(j,a[j],to-(id-j));
    }
    p[y[id]].a=a[id]=to;
    return tot+abs(from-to);
}

signed main(){
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
//  freopen("move2.in","r",stdin);
//  freopen("move5.out","w",stdout);
    c=read();T=read();
    while(T--){
        n=read();t=0;judge=true;
        for(int i=1;i<=n;i++){a[i]=p[i].a=read();p[i].b=read();p[i].t=read();p[i].id=i;}
        if(c==12){
            for(int i=1;i<=n;i++) t+=abs(p[i].a-p[i].b);
            cout<<(t>p[1].t?"No":"Yes")<<endl;
            continue;
        }
        stable_sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++) y[p[i].id]=i;
        for(int i=1;i<=n;i++){
            t+=find(p[i].id,p[i].a,p[i].b);
            if(t>p[i].t){
                judge=false;
                break;
            }
        }
        cout<<(judge?"Yes":"No")<<endl;
    }
    return 0;
}

$O(n\log^2n)$

参考代码

此代码为省选场上 YKK 的代码。

#include<bits/stdc++.h>
#define int long long 
#define i128 __int128
using namespace std;
int read(){
    int x=0,f=1; char c=0;
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    } 
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c-'0');
        c=getchar();
    }
    return x*f;
}
const int N=1e6+10;
int C;
int n;
struct treenode{
    int l,r;
    int s,tag;
}tr[N<<2];
struct node{
    int a,b;
    int t;
}p[N];
int id[N];
bool compare(int x,int y){
    if(p[x].t==p[y].t) return false;
    return p[x].t<p[y].t;
}
void pushup(int u){tr[u].s=tr[u<<1].s+tr[u<<1|1].s;}
void pushdown(int u){
    int w=tr[u].tag;
    tr[u<<1].s=(tr[u<<1].r-tr[u<<1].l+1)*w+(tr[u<<1].r-tr[u<<1].l+1)*(tr[u<<1].l+tr[u<<1].r)/2;
    tr[u<<1|1].s=(tr[u<<1|1].r-tr[u<<1|1].l+1)*w+(tr[u<<1|1].r-tr[u<<1|1].l+1)*(tr[u<<1|1].l+tr[u<<1|1].r)/2;
    tr[u<<1].tag=tr[u<<1|1].tag=w;
    tr[u].tag=-1;
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    tr[u].tag=-1;
    if(l==r){
        tr[u].s=p[l].a;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int v){
//  cerr<<"update. "<<u<<" "<<l<<" "<<r<<" "<<v<<"\n"; 
    if(l<=tr[u].l && tr[u].r<=r){
        tr[u].s=(tr[u].r-tr[u].l+1)*v+(tr[u].r-tr[u].l+1)*(tr[u].l+tr[u].r)/2;
        tr[u].tag=v;
        return;
    }
    if(tr[u].tag!=-1) pushdown(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) update(u<<1,l,r,v);
    if(r>mid) update(u<<1|1,l,r,v);
    pushup(u);
}
int query(int u,int l,int r){
//  cerr<<"query. "<<u<<" "<<l<<" "<<r<<"\n";    
    if(l<=tr[u].l && tr[u].r<=r) return tr[u].s;
    int res=0;
    if(tr[u].tag!=-1) pushdown(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    return res;
}
void solve(){
//  cerr<<"solve. \n";
    n=read();
//  cerr<<"n. "<<n<<"\n";
    for(int i=1;i<=n;i++){
        p[i].a=read(),p[i].b=read(),p[i].t=read();
        id[i]=i;
    }
//  cerr<<"sort?\n";
    sort(id+1,id+n+1,compare);
//  cerr<<"build\n";
    build(1,1,n);
//  cerr<<"???\n";
    i128 ans=0;
    for(int i=1;i<=n;i++){
        int res=0;
        int x=id[i];
//      cerr<<"id. "<<i<<" "<<x<<"\n";
        int now=query(1,x,x);
        int b=p[x].b,t=p[x].t;
        if(now==b) continue;
        if(now>b){
            int pos=x;
            int L=1,R=x-1;
            while(L<=R){
                int mid=(L+R)>>1;
                if(query(1,mid,mid)<b-(x-mid)) L=mid+1;
                else pos=mid,R=mid-1;
            }
            int val=b-(x-pos);
            res=query(1,pos,x)-(b-val+1)*(b+val)/2;
            update(1,pos,x,val-pos);
        }
        else{
            int pos=x;
            int L=x+1,R=n;
            while(L<=R){
                int mid=(L+R)>>1;
                if(query(1,mid,mid)>b+(mid-x)) R=mid-1;
                else pos=mid,L=mid+1;
            }
            int val=b+(pos-x);
            res=(val-b+1)*(val+b)/2-query(1,x,pos);
            update(1,x,pos,b-x);
        }
        ans+=res;
//      cerr<<"ans. "<<(int)ans<<"\n";
        if(ans>t){
            puts("No");
            return;
        }
    }
    puts("Yes");
    return;
}
signed main(){
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
//  cerr<<"start.!\n";
    C=read();
    int t=read();
    while(t--) solve();
    return 0;
}

$O(n\log n)$

参考代码

此代码为我的 AC 代码。

// Problem: P11833 [省选联考 2025] 推箱子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11833
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int c,n,T,t,id[MAXN];
struct node{
    int a,b,t;
}p[MAXN];
struct node2{
    int l,r,val1,val2,sum,lazy;
}tree[MAXN<<2];

bool cmp(int n1,int n2){
    return p[n1].t<p[n2].t;
}

void pushup(int id){
    tree[id].val1=max(tree[id*2].val1,tree[id*2+1].val1);
    tree[id].val2=min(tree[id*2].val2,tree[id*2+1].val2);
    tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}

void pushdown(int id){
    if(tree[id].lazy==-1) return;
    tree[id*2].val1=tree[id*2+1].val1=tree[id].lazy;
    tree[id*2].val2=tree[id*2+1].val2=tree[id].lazy;
    tree[id*2].lazy=tree[id*2+1].lazy=tree[id].lazy;
    tree[id*2].sum=(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
    tree[id*2+1].sum=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
    tree[id].lazy=-1;
}

void build(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].lazy=-1;
    if(l==r){
        tree[id].val1=tree[id].val2=tree[id].sum=p[l].a-l;
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}

int qsum(int l,int r){return (r-l+1)*(l+r)/2;}

int query(int id,int l,int r,int pos){
    if(l==r) return tree[id].val1+l;
    int mid=(l+r)>>1;
    pushdown(id);
    if(pos<=mid) return query(id*2,l,mid,pos);
    else return query(id*2+1,mid+1,r,pos);
}

void work(int id,int l,int r,int L,int R,bool type,int pos){
    // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<type<<" "<<pos<<" "<<p[pos].b<<endl;
    if(r<L||R<l) return;
    if(l==r){
        // cout<<tree[id].val1<<" "<<p[pos].b-pos<<endl;
        if(!type){
            if(tree[id].val1<p[pos].b-pos){
                t+=p[pos].b-L-tree[id].val1;
                tree[id].val1=tree[id].val2=tree[id].sum=p[pos].b-pos;
            }
        }
        else{
            if(tree[id].val2>p[pos].b-pos){
                t+=tree[id].val2-(p[pos].b-R);
                tree[id].val1=tree[id].val2=tree[id].sum=p[pos].b-pos;
            }
        }
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(L<=l&&r<=R){
        if(!type){
            // cout<<"type0:"<<tree[id*2].sum+qsum(l,mid)<<" "<<(p[pos].b+(l-L))*(mid-l+1)+qsum(l,mid)-l*(mid-l+1)<<endl;
            if(tree[id*2].val1<p[pos].b-pos){
                t+=(p[pos].b-L)*(mid-l+1)-tree[id*2].sum;
                tree[id*2].val1=tree[id*2].val2=tree[id*2].lazy=p[pos].b-pos;
                tree[id*2].sum=(mid-l+1)*(p[pos].b-pos);
                work(id*2+1,mid+1,r,L,R,type,pos);
            }
            else work(id*2,l,mid,L,R,type,pos);
        }
        else{
            // cout<<"type1:"<<tree[id*2+1].sum+qsum(mid+1,r)<<" "<<(p[pos].b-(R-mid)+1)*(r-mid)+qsum(mid+1,r)-(mid+1)*(r-mid)<<endl;
            if(tree[id*2+1].val2>p[pos].b-pos){
                t+=tree[id*2+1].sum-(p[pos].b-R)*(r-mid);
                tree[id*2+1].val1=tree[id*2+1].val2=tree[id*2+1].lazy=p[pos].b-pos;
                tree[id*2+1].sum=(r-mid)*(p[pos].b-pos);
                work(id*2,l,mid,L,R,type,pos);
            }
            else work(id*2+1,mid+1,r,L,R,type,pos);
        }
        pushup(id);
        return;
    }
    if(L<=mid) work(id*2,l,mid,L,R,type,pos);
    if(R>mid) work(id*2+1,mid+1,r,L,R,type,pos);
    pushup(id);
}

signed main(){
    read(c,T);
    while(T--){
        read(n);t=0;
        for(int i=1;i<=n;i++) read(p[i].a,p[i].b,p[i].t);
        for(int i=1;i<=n;i++) id[i]=i;
        sort(id+1,id+n+1,cmp);
        // for(int i=1;i<=n;i++) cout<<p[id[i]].a<<" "<<p[id[i]].b<<" "<<p[id[i]].t<<endl;
        build(1,1,n);
        bool judge=true;
        for(int i=1;i<=n;i++){
            int now=id[i],nowpos=query(1,1,n,now);
            if(p[now].b>nowpos) work(1,1,n,now,n,false,now);
            else{if(p[now].b<nowpos) work(1,1,n,1,now,true,now);}
            // cout<<"t:"<<t<<endl;
            // for(int j=1;j<=n;j++) cout<<query(1,1,n,j)<<" ";
            // cout<<endl;
            if(t>p[now].t){
                judge=false;
                break;
            }
        }
        cout<<(judge?"Yes":"No")<<endl;
    }
    return 0;
}

T4

Luogu：CF1969E Unique Array
CF：E. Unique Array

题意简述

给定一个为 $n$ 的序列 $a$，定义一个子段为独特子段，当且仅当其中存在某个数，恰好只出现一次。
一次操作为选择 $a$ 中的某个数，将其修改为任意一个数，问至少多少次操作可以使 $a$ 的所有子段均为独特子段。

$1\le n\le 3\times 10^5$。

思路

Hint1

不难发现，因为可以任意修改，所以我们不会重复修改某个位置的数。

Hint2

不妨从前往后的去考虑某个数需不需要修改。想想怎么判断需不需要修改。

Hint3

同样考虑一个数产生的贡献，设他的位置为 $i$，上一个值相同的位置为 $last_{i}$，那么对于右端点为 $i$，左端点在 $[last_{i}+1,i]$ 的区间均是独特子段。
发现这类似于一个扫描线。
继续想想看。

Hint4

再次想想扫描线的过程中，什么时候需要修改这个位置的值。

Solution

设上一个更改的位置为 $pre$，根据 Hint1，包含 $pre$ 这个点的所有子段一定是独特子段，而对于目前已有的数造成的贡献，假如位于 $[pre+1,i]$ 的左端点中存在某个位置，使得 $[l,i]$ 不为独特子段，那么这个位置 $i$ 就需要更改。

发现我们 Hint3 中的贡献可以通过记录某个元素上一次出现的位置和上上次出现的位置来维护。转化为 $+1$ 和 $-1$，那么判断上一段中的条件就是区间最小值是否为 $0$。

参考代码

// Problem: Unique Array
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1969E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int t,n,ans,pre,val[MAXN],last[MAXN],llast[MAXN],b[MAXN];
struct node{
    int l,r,minval,lazy;
}tree[MAXN<<2];

void build(int id,int l,int r);

void init(){
    pre=1;ans=0;
    for(int i=1;i<=n;i++) last[i]=0;
    for(int i=1;i<=n;i++) llast[i]=0;
    build(1,1,n);
}

void pushup(int id){
    tree[id].minval=min(tree[id*2].minval,tree[id*2+1].minval);
}

void pushdown(int id){
    if(tree[id].lazy==0) return;
    tree[id*2].minval+=tree[id].lazy;
    tree[id*2+1].minval+=tree[id].lazy;
    tree[id*2].lazy+=tree[id].lazy;
    tree[id*2+1].lazy+=tree[id].lazy;
    tree[id].lazy=0;
}

void build(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].minval=0;
    tree[id].lazy=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}

void update(int id,int l,int r,int L,int R,int val){
    if(r<L||R<l) return;
    if(L<=l&&r<=R){
        tree[id].minval+=val;
        tree[id].lazy+=val;
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(L<=mid) update(id*2,l,mid,L,R,val);
    if(R>mid) update(id*2+1,mid+1,r,L,R,val);
    pushup(id);
}

int query(int id,int l,int r,int L,int R){
    if(r<L||R<l) return 1e9;
    if(L<=l&&r<=R) return tree[id].minval;
    int mid=(l+r)>>1;
    int res=1e9;
    pushdown(id);
    if(L<=mid) res=min(res,query(id*2,l,mid,L,R));
    if(R>mid) res=min(res,query(id*2+1,mid+1,r,L,R));
    return res;
}

signed main(){
    read(t);
    while(t--){
        read(n);
        for(int i=1;i<=n;i++) read(val[i]);
        for(int i=1;i<=n;i++) b[i]=val[i];
        sort(b+1,b+n+1);
        int cnt=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;i++) val[i]=lower_bound(b+1,b+cnt+1,val[i])-b;
        init();
        for(int i=1;i<=n;i++){
            update(1,1,n,last[val[i]]+1,i,1);
            update(1,1,n,llast[val[i]]+1,last[val[i]],-1);
            llast[val[i]]=last[val[i]];
            last[val[i]]=i;
            if(query(1,1,n,pre,i)==0){
                ans++;
                pre=i+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

T5

本来题单里面是没有这道题的，fl 说你们都不会线段树合并，于是先讲下板子。

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

题意简述

给定一棵 $n$ 个点的树，$m$ 次操作，每次会选择一条路径，将这条路径上的所有点都发放一个权值 $v$，问最后每个点上哪个权值的数量最多。

$1\le n,m,v \le 10^5$

思路

Hint1

暴力是很显然的，对树上的每个点开一个桶，加的时候暴力加。
时间复杂度 $O(nm+n)$，空间复杂度 $O(nV)$。
先不想什么线段树合并，考虑一下优化。

Hint2

区间加单点查可以转化为单点加区间查，序列这样，树上亦然。
我们使用树上差分，统计的时候从叶子往上合并即可。
时间复杂度 $O(m+nV)$，空间复杂度 $O(nV)$。

Hint3

时间复杂度的瓶颈在于合并，空间复杂度的瓶颈在于存储。
想想怎么用线段树优化，其实就出来了。

Solution

上面讲的差不多了。
我们不可能对于每个点都开一棵完整的线段树，所以我们使用动态开点。

具体讲讲合并的过程。
设我们要合并 $A$ 和 $B$ 这两棵线段树，我们从区间 $[1,n]$ 开始合并，分四种情况讨论。

当前区间 $A$ 有，$B$ 有：那么我们不知道具体合并成什么样子，需要向下递归处理。
当前区间 $A$ 有，$B$ 没有：那么合并后这个位置取 $A$ 的即可。
当前区间 $A$ 没有，$B$ 有：那么合并后这个位置取 $B$ 的即可。
当前区间 $A$ 没有，$B$ 没有：那么这个位置合并后也不会有。

当然假如递归到了叶子节点，直接合并两者信息即可。
后三种情况可以综合一下，具体可以看代码的 merge 部分。

对于线段树合并的时间复杂度，容易发现单次合并的复杂度是 $O($重复节点个数$)$ 的。空间复杂度也比较抽象。所以这里就不做分析了。

一般而言，假如你一次操作只会修改 $O(1)$ 个位置，时间复杂度可以当成 $O(n\log n)$ 的，空间的话开 $50$ 倍左右就行了。

空间小优化

一般而言我们合并后，会有一棵线段树的大部分点都不会被用到，我们可以创建一个垃圾回收机制，具体的：维护一个栈/队列，存储哪些点没用了，当我们需要新点的时候，优先从这里面取，没有的话，再新建一个点。这样可以优化很多空间。
当然，如果某道题需要类似于可持久化的操作，就不能这样用了。

参考代码

// Problem: P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4556
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,k,cnt,head[MAXN],root[MAXN],dep[MAXN],fa[MAXN][18],ans[MAXN];
struct node{
    int to,next;
}edge[MAXN<<1];
struct node2{
    int l,r,lson,rson,maxval,maxid;
}tree[MAXN<<6];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void dfs(int u,int f){
    for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        dep[v]=dep[u]+1;
        fa[v][0]=u;
        dfs(v,u);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int del=dep[u]-dep[v];
    for(int i=0;(1<<i)<=del;i++) if(del&(1<<i)) u=fa[u][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

void pushup(int id){
    if(tree[tree[id].lson].maxval>=tree[tree[id].rson].maxval){
        tree[id].maxval=tree[tree[id].lson].maxval;
        tree[id].maxid=tree[tree[id].lson].maxid;
    }
    else{
        tree[id].maxval=tree[tree[id].rson].maxval;
        tree[id].maxid=tree[tree[id].rson].maxid;
    }
}

void newnode(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].maxval=0;
    tree[id].maxid=l;
}

void update(int id,int l,int r,int pos,int val){
    if(l==r){
        tree[id].maxval+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid){
        if(!tree[id].lson){
            tree[id].lson=++cnt;
            newnode(tree[id].lson,l,mid);
        }
        update(tree[id].lson,l,mid,pos,val);
    }
    else{
        if(!tree[id].rson){
            tree[id].rson=++cnt;
            newnode(tree[id].rson,mid+1,r);
        }
        update(tree[id].rson,mid+1,r,pos,val);
    }
    pushup(id);
}

int merge(int u,int v){
    if(u==0||v==0) return u+v;
    if(tree[u].l==tree[u].r){
        tree[u].maxval+=tree[v].maxval;
        return u;
    }
    tree[u].lson=merge(tree[u].lson,tree[v].lson);
    tree[u].rson=merge(tree[u].rson,tree[v].rson);
    pushup(u);
    return u;
}

void solve(int u,int f){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        solve(v,u);
        root[u]=merge(root[u],root[v]);
    }
    if(tree[root[u]].maxval!=0) ans[u]=tree[root[u]].maxid;
}

signed main(){
    read(n,m);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        build(u,v);
        build(v,u);
    }
    dfs(1,1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u,v,w);
        int lc=lca(u,v);
        if(!root[u]){
            root[u]=++cnt;
            newnode(root[u],1,1e5);
        }
        update(root[u],1,1e5,w,1);
        if(!root[v]){
            root[v]=++cnt;
            newnode(root[v],1,1e5);
        }
        update(root[v],1,1e5,w,1);
        if(!root[lc]){
            root[lc]=++cnt;
            newnode(root[lc],1,1e5);
        }
        update(root[lc],1,1e5,w,-1);
        if(!fa[lc][0]) continue;
        if(!root[fa[lc][0]]){
            root[fa[lc][0]]=++cnt;
            newnode(root[fa[lc][0]],1,1e5);
        }
        update(root[fa[lc][0]],1,1e5,w,-1);
    }
    solve(1,1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}

T6

SP2916 GSS5 - Can you answer these queries V
GSS 系列之一，有 GSS1~GSS8，除了 GSS2，其他七道，你们以你们现在学了的东西，理论上都可以做。
这个系列已经统一降过一次难度了。也就是说现在这个系列中的蓝以前是紫，紫是黑，不禁令人感叹时代在进步。（跑题了）

题意简述

给定一个长为 $n$ 的序列 $a$。每次询问，给定 $l_1,r_1,l_2,r_2$，问左端点在 $[l_1,r_1]$，右端点在 $[l_2,r_2]$ 的子段的和的最大值。

$\left|a_{i}\right|\le 10^4，1\le n\le 10^4,l_1\le l_2,r_1\le r_2$。

思路

Hint1

注意题目没有保证区间不重。

Hint2

不妨分讨一下两种情况。
两个区间相交和不交这两种情况。

Solution

不交相对简单，我们先来看这种情况。
首先对于区间 $[r_1+1,l_2-1]$，这里面的数一定会被取到，那么我们本质上只需要求 $[l_1,r_1]$ 的最大和后缀和 $[l_2,r_2]$ 的最大前缀和即可。

相交的时候又可以分为三种情况：
1. $l\in [l_1,l_2],r\in[l_2,r_2]$：本质求的就是 $[l_1,l_2]$ 的最大后缀和加上 $[l_2,r_2]$ 的最大前缀和。
2. $l\in [l_1,r_1],r\in[r_1,r_2]$：本质求的就是 $[l_1,r_1]$ 的最大后缀和加上 $[r_1,r_2]$ 的最大前缀和。
3. $l\in [l_2,r_1],r\in[l_2,r_1]$：这种显然就直接是 $[l_2,r_1]$ 的最大子段和。

这些东西在用线段树维护最大子段和的过程中已经全部求出了，直接查询即可。

参考代码

// Problem: SP2916 GSS5 - Can you answer these queries V
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP2916
// Memory Limit: 1 MB
// Time Limit: 132000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int T,n,m,val[MAXN];
struct num{
    int pre,suf,sum,ans;
    void init(){pre=suf=ans=-inf_int;sum=0;}
};
struct node{
    int l,r;
    num ans;
}tree[MAXN<<2];

num merge(num a,num b){
    num res;res.init();
    res.pre=max(a.pre,a.sum+b.pre);
    res.suf=max(b.suf,b.sum+a.suf);
    res.sum=a.sum+b.sum;
    res.ans=max({res.pre,res.suf,a.ans,b.ans,a.suf+b.pre});
    return res;
}

void pushup(int id){
    tree[id].ans=merge(tree[id*2].ans,tree[id*2+1].ans);
}

void build(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].ans.init();
    if(l==r){
        tree[id].ans=(num){val[l],val[l],val[l],val[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}

num query(int id,int l,int r,int L,int R){
    num res;res.init();
    if(r<L||R<l) return res;
    if(L<=l&&r<=R) return tree[id].ans;
    int mid=(l+r)>>1;
    if(L<=mid) res=merge(res,query(id*2,l,mid,L,R));
    if(R>mid) res=merge(res,query(id*2+1,mid+1,r,L,R));
    return res;
}

signed main(){
    read(T);
    while(T--){
        read(n);
        for(int i=1;i<=n;i++) read(val[i]);
        build(1,1,n);
        read(m);
        for(int i=1;i<=m;i++){
            int x1,x2,y1,y2;
            read(x1,y1,x2,y2);
            if(y1<=x2) cout<<query(1,1,n,x1,y1).suf+query(1,1,n,y1,x2).sum+query(1,1,n,x2,y2).pre-val[y1]-val[x2]<<'\n';
            else cout<<max({query(1,1,n,x1,x2).suf+query(1,1,n,x2,y1).pre-val[x2],query(1,1,n,x1,x2).suf+query(1,1,n,x2,y1).sum+query(1,1,n,y1,y2).pre-val[x2]-val[y1],query(1,1,n,x2,y1).ans,query(1,1,n,x2,y1).suf+query(1,1,n,y1,y2).pre-val[y1]})<<'\n';
        }
    }
    return 0;
}

T7

P2042 [NOI2005] 维护数列

题意简述

请写一个程序，要求维护一个数列，支持以下 $6$ 种操作：

编号	名称	格式	说明
1	插入	$\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$	在当前数列的第 $posi$ 个数字后插入 $tot$ 个数字：$c_1, c_2 \cdots c_{tot}$；若在数列首插入，则 $posi$ 为 $0$
2	删除	$\operatorname{DELETE} \ posi \ tot$	从当前数列的第 $posi$ 个数字开始连续删除 $tot$ 个数字
3	修改	$\operatorname{MAKE-SAME} \ posi \ tot \ c$	从当前数列的第 $posi$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$
4	翻转	$\operatorname{REVERSE} \ posi \ tot$	取出从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字，翻转后放入原来的位置
5	求和	$\operatorname{GET-SUM} \ posi \ tot$	计算从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字的和并输出
6	求最大子列和	$\operatorname{MAX-SUM}$	求出当前数列中和最大的一段子列，并输出最大和

任何时刻数列中最多含有 $5 \times 10^5$ 个数，任何时刻数列中任何一个数字均在 $[-10^3, 10^3]$ 内，$1 \le M \le 2 \times 10^4$，插入的数字总数不超过 $4 \times 10^6$。

思路

Solution

文艺平衡树可以维护一段区间的一些东西，需要维护的东西具有结合律就大半部分可以维护。

因此最大子段和也是可以维护的。那么 $\operatorname{MAX-SUM}$ 和 $\operatorname{GET-SUM}$ 就实现了。

翻转操作和文艺平衡树板子一样打 tag 即可，那么 $\operatorname{REVERSE}$ 就实现了。

插入一堆数也是容易的，类似于初始建树那样插入一条链即可，一个个插入是会时间复杂度是 $O(n\log n)$ 的，插入共 $4 \times 10^6$ 个数，是会 TLE 的。那么 $\operatorname{INSERT}$ 就实现了。

删除和插入很类似，一次删掉一整个区间，不要一个个删。那么 $\operatorname{DELETE}$ 就实现了。

修改也是容易的，打 tag 即可，那么 $\operatorname{MAKE-SAME}$ 也就实现了。
为什么不能全删了再全加进去，每次可能最多会改整个序列，所以直接做的话时间复杂度是 $O(nm)$ 的。

那么就没了。

参考代码

// Problem: P2042 [NOI2005] 维护数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2042
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,cnt,root,top,sta[MAXN],siz[MAXN],a[MAXN],son[MAXN][2],tag[MAXN],tag2[MAXN],fa[MAXN],val[MAXN],maxval[MAXN],premax[MAXN],sufmax[MAXN],sum[MAXN];

int get(int x){return x==son[fa[x]][1];}
void rev(int x){
    swap(son[x][0],son[x][1]);
    swap(premax[x],sufmax[x]);
    tag[x]^=1;
}
void updtag(int x,int z){
    premax[x]=sufmax[x]=max(0,siz[x]*z);
    maxval[x]=(z>=0?siz[x]*z:z);
    sum[x]=siz[x]*z;
    val[x]=tag2[x]=z;
}

void pushup(int x){
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
    maxval[x]=premax[x]=sufmax[x]=sum[x]=val[x];
    if(son[x][0]){
        int pre=premax[x];
        premax[x]=max(premax[son[x][0]],sum[son[x][0]]+premax[x]);
        sufmax[x]=max(sufmax[x],sufmax[son[x][0]]+sum[x]);
        maxval[x]=max({maxval[son[x][0]],maxval[x],sufmax[son[x][0]]+pre});
        sum[x]=sum[son[x][0]]+sum[x];
    }
    if(son[x][1]){
        int suf=sufmax[x];
        premax[x]=max(premax[x],sum[x]+premax[son[x][1]]);
        sufmax[x]=max(sufmax[x]+sum[son[x][1]],sufmax[son[x][1]]);
        maxval[x]=max({maxval[x],maxval[son[x][1]],suf+premax[son[x][1]]});
        sum[x]=sum[x]+sum[son[x][1]];
    }
}

void pushdown(int x){
    if(tag[x]){
        if(son[x][0]) rev(son[x][0]);
        if(son[x][1]) rev(son[x][1]);
        tag[x]=0;
    }
    if(tag2[x]!=-1e9){
        if(son[x][0]) updtag(son[x][0],tag2[x]);
        if(son[x][1]) updtag(son[x][1],tag2[x]);
        tag2[x]=-1e9;
    }
}

void print(int rt){
    pushdown(rt);
    if(son[rt][0]) print(son[rt][0]);
    cout<<rt<<" "<<fa[rt]<<" "<<son[rt][0]<<" "<<son[rt][1]<<" "<<val[rt]<<" "<<maxval[rt]<<endl;
    if(son[rt][1]) print(son[rt][1]);
}

void rotate(int x){
    int y=fa[x],z=fa[y],ch=get(x);
    son[y][ch]=son[x][ch^1];
    if(son[x][ch^1]) fa[son[x][ch^1]]=y;
    son[x][ch^1]=y;
    if(z) son[z][get(y)]=x;
    fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}

void splay(int x,int &rt){
    int z=fa[rt];
    for(int f=fa[x];f!=z;f=fa[x]){
        if(fa[f]!=z) rotate(get(x)==get(f)?f:x);
        rotate(x);
    }
    rt=x;
}

void build(int &rt){
    for(int i=0;i<=n+2;i++){
        rt=i+1;
        tag2[i+1]=-1e9;
        son[i+1][0]=i;
        val[i+1]=premax[i+1]=sufmax[i+1]=maxval[i+1]=sum[i+1]=(i==0?0:a[i-1]);
        siz[i+1]=i+1;
        if(i) fa[i]=i+1;
        pushup(i+1);
    }
    cnt=n+3;
    splay(1,rt);
}

void selval(int x,int &rt){
    int pos=rt;
    while(true){
        pushdown(pos);
        if(son[pos][0]&&siz[son[pos][0]]>=x) pos=son[pos][0];
        else{
            x-=siz[son[pos][0]]+1;
            if(x<=0){
                splay(pos,rt);
                return;
            }
            pos=son[pos][1];
        }
    }
}

void split(int l,int r,int &rt){
    l+=2;r+=2;
    selval(l-1,rt);
    selval(r-siz[son[rt][0]],son[rt][1]);
}

int newnode(){
    if(top!=0) return sta[top--];
    return ++cnt;
}

void insert(int x,vector<int> z,int &rt){
    split(x,x,rt);
    int pos=son[son[rt][1]][0];
    pushdown(pos);
    for(int i=0;i<z.size();i++){
        int now=newnode();
        son[pos][1]=now;
        fa[now]=pos;
        val[now]=premax[now]=sufmax[now]=maxval[now]=sum[now]=z[i];
        tag[now]=0;
        tag2[now]=-1e9;
        siz[now]=z.size()-i;
        pushdown(pos);
        pos=now;
    }
    splay(pos,rt);
}

void recycle(int rt){
    if(son[rt][0]) recycle(son[rt][0]);
    if(son[rt][1]) recycle(son[rt][1]);
    son[fa[rt]][get(rt)]=0;
    son[rt][0]=son[rt][1]=fa[rt]=maxval[rt]=siz[rt]=premax[rt]=sufmax[rt]=val[rt]=tag[rt]=0;
    tag2[rt]=-1e9;
    sta[++top]=rt;
}

void del(int l,int r,int &rt){
    split(l,r,rt);
    int pos=son[son[rt][1]][0];
    recycle(pos);
    splay(son[rt][1],rt);
}

int query(int l,int r,int &rt,bool op){
    split(l,r,rt);
    int pos=son[son[rt][1]][0];
    return op?maxval[pos]:sum[pos];
}

void reverse(int l,int r,int &rt){
    split(l,r,rt);
    int pos=son[son[rt][1]][0];
    rev(pos);
    pushdown(pos);
    splay(pos,rt);
}

void change(int l,int r,int z,int &rt){
    split(l,r,rt);
    int pos=son[son[rt][1]][0];
    updtag(pos,z);
    pushdown(pos);
    splay(pos,rt);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(root);
    for(int i=1;i<=m;i++){
        string opt;
        int a,b,c;
        cin>>opt;
        if(opt=="INSERT"){
            cin>>a>>b;n+=b;
            vector<int> num;
            for(int j=1;j<=b;j++) cin>>c,num.push_back(c);
            insert(a,num,root);
        }
        if(opt=="DELETE") cin>>a>>b,del(a,a+b-1,root),n-=b;
        if(opt=="MAKE-SAME") cin>>a>>b>>c,change(a,a+b-1,c,root);
        if(opt=="REVERSE") cin>>a>>b,reverse(a,a+b-1,root);
        if(opt=="GET-SUM") cin>>a>>b,cout<<query(a,a+b-1,root,false)<<'\n';
        if(opt=="MAX-SUM") cout<<query(1,n,root,true)<<'\n';
        // print(root);
        // cout<<endl;
    }
    return 0;
}
/*
1 8 1 7
1 8 7 1
1 7 8 7 1
1 7 8 7 1
1 7 1 7 8
1 7 1 7 1 -9 -6 8
1 7 1 1 7 -9 -6 8
1 7 1 1 7 -9 9 1 3 10 -6 8
*/

T8

Luogu：CF551E GukiZ and GukiZiana
CF：E. GukiZ and GukiZiana

题意简述

给定一个长度为 $n$ 的序列 $a$，$q$ 次操作，操作有两种类型：区间加；给定 $y$，求最大的 $j-i$ 使得 $a_{i}=a_{j}=y$，无解输出 $-1$。

$1\le n\le 5\times 10^5,1\le q \le 5\times 10^4$。
时限为 $10$ 秒

思路

Hint1

线段树可做吗？

Hint2

除了线段树，还能用什么维护？注意一下数据范围和时限。

Solution

我们使用分块来维护这道题。
区间加和普通的分块类似，分为整块加和单点加。

查询，我们贪心的先从前往后找哪个块有，找到后再去内部找是哪个点。
再从最后开始类似的找，直接返回这两个位置的差即可。
没有直接返回 $-1$。
找有没有某个值用 multiset 即可。
时间复杂度 $O(q\sqrt{n}\log n)$，算出来是 $6\times 10^8$ 左右，但是限时 $10$ 秒，随便跑。

参考代码

// Problem: CF551E GukiZ and GukiZiana
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF551E
// Memory Limit: 250 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,B,a[MAXN],bel[MAXN],add[MAXN];
multiset<int> z[MAXN];

void update(int l,int r,int val){
    int lb=bel[l],rb=bel[r];
    if(lb==rb){
        for(int i=l;i<=r;i++){
            z[lb].erase(z[lb].find(a[i]));
            a[i]+=val;
            z[lb].insert(a[i]);
        }
    }
    else{
        for(int i=l;i<=lb*B;i++){
            z[lb].erase(z[lb].find(a[i]));
            a[i]+=val;
            z[lb].insert(a[i]);
        }
        for(int i=lb+1;i<rb;i++) add[i]+=val;
        for(int i=(rb-1)*B+1;i<=r;i++){
            z[rb].erase(z[rb].find(a[i]));
            a[i]+=val;
            z[rb].insert(a[i]);
        }
    }
}

int query(int val){
    for(int i=1;i<=bel[n];i++)
        if(z[i].find(val-add[i])!=z[i].end())
            for(int j=(i-1)*B+1;j<=min(n,i*B);j++)
                if(a[j]+add[i]==val)
                    for(int k=bel[n];k>=i;k--)
                        if(z[k].find(val-add[k])!=z[k].end())
                            for(int l=min(n,k*B);l>=(k-1)*B+1;l--)
                                if(a[l]+add[k]==val)
                                    return l-j;
    return -1;
}

signed main(){
    read(n,m);
    B=sqrt(n);
    for(int i=1;i<=n;i++) bel[i]=(i+B-1)/B;
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) z[bel[i]].insert(a[i]);
    for(int i=1;i<=m;i++){
        int op,l,r,x;
        read(op);
        if(op==1) read(l,r,x),update(l,r,x);
        if(op==2) read(x),cout<<query(x)<<'\n';
    }
    return 0;
}

T9

P3203 [HNOI2010] 弹飞绵羊

题意简述

给定长度为 $n$ 的序列 $a$，一次查询求从某个数字 $i$ 开始，从 $i$ 跳到 $i+a_{i}$ 再往后跳，直到 $i>n$ 所需的次数。有若干次修改操作。

$1\le n \le 2\times 10^5，1\le q \le 10^5。$
保证 $a$ 中全为正整数。

思路

Hint1

暴力模拟的时间复杂度显然是 $O(nq)$ 的。发现我们每次计算时重复计算了很多东西，怎么优化？

Hint2

这个显然线段树是不能维护的，我们真的有必要一次只跳一次吗？

Solution

使用分块，我们跳整块的时候可以直接计算。
我们将整个区间拆成 $\sqrt{n}$ 个小区间，每个区间内暴力计算，暴力修改。具体的，假如某次跳出块外，将这个点的 $val$ 设为 $1$，没跳出则 $val_{i}=val_{i+a_{i}}+1$。
对于查询，我们从这个点开始，一直跳块外即可。
时间复杂度 $O(q\sqrt{n})$。

ps：如果你们会 LCT 的话，会发现这其实是一道 LCT 裸题，将块外也设为一个点，将 $i$ 与 $i+a_{i}$ 连边。这是一棵树，每次询问求的本质就是这个点到根的距离，修改本质就是断边和连边。这道题数据范围较小，数据也比较水，放过了分块。（其实有更轻量的 LCT 写法，可以看看题解区第一篇。）

参考代码

远古代码。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int n,m,p[MAXN],len,to[MAXN],cnt[MAXN],bl[555],br[555],belong[MAXN];
int main(){
    cin>>n;
    len=sqrt(n);
    for(int i=0;i<=(len*len==n?len:len+1);i++){
        bl[i+1]=len*i+1;
        br[i+1]=min(len*(i+1),n);
        for(int j=bl[i+1];j<=br[i+1];j++) belong[j]=i+1;
    }
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=n;i>=1;i--){
        if(belong[i]==belong[i+p[i]]){
            cnt[i]=cnt[i+p[i]]+1;
            to[i]=to[i+p[i]];
        }
        else{
            cnt[i]=1;
            to[i]=i+p[i];
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int opt,a,b;
        cin>>opt;
        if(opt==2){
            cin>>a>>b;
            a++;
            p[a]=b;
            for(int j=br[belong[a]];j>=bl[belong[a]];j--){
                if(belong[j]==belong[j+p[j]]){
                    cnt[j]=cnt[j+p[j]]+1;
                    to[j]=to[j+p[j]];
                }
                else{
                    cnt[j]=1;
                    to[j]=j+p[j];
                }
            }
        }
        if(opt==1){
            cin>>a;
            a++;
            int ans=0;
            while(a<=n){
                ans+=cnt[a];
                a=to[a];
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

T10

P5355 [Ynoi Easy Round 2017] 由乃的玉米田

题意简述

给定一个长度为 $n$ 的序列 $a$，有 $m$ 次询问，为以下这 $4$ 种：

询问一个区间是否可以选出两个数它们的差为 $x$。
询问一个区间是否可以选出两个数它们的和为 $x$。
询问一个区间是否可以选出两个数它们的乘积为 $x$。
询问一个区间是否可以选出两个数它们的商为 $x$（没有余数）。

$1\le n,m\,a_{i}\le 10^5$。

思路

Hint1

询问区间，你想到了什么算法？
分块？线段树？

Hint2

先只考虑前两个询问，该怎么做？

Hint3

前两个询问不难想到直接使用莫队维护一个桶。但是这样我们需要对每个数查询一下，太慢了。
实际上我们只需要知道是否存在不需要知道数量，也就是只需维护一个 01 串，不难想到 bitset。
对于差也就是找到 $a$ 与 $a+x$ 均存在，使用 bitset 也就是a&(a<<x)。
和是类似的，也可以用 bitset 实现。
一次询问用时为 $O(\dfrac{n}{w})$ 那么第三个询问怎么实现呢？

Hint4

前三个询问其实就是这道题：P3674 小清新人渣的本愿。
其实不难想到直接枚举因子，再判断是否存在。单次询问 $O(\sqrt{n})$。
然后就是最难的第四种询问。

Hint5

有一些第四种询问已经可以处理了吗？剩下的又怎么办？

Solution

前三种前面已经说了，就不再赘述了。对于第四种，我们类似于第三种询问的做法，暴力枚举除数，乘起来得到被除数，判断两者是否存在。这样的复杂度显然是 $O(\dfrac{V}{x})$。适用于 $x\ge \sqrt{V}$。
那么对于 $x$ 更小的怎么办呢？

我们发现此时 $x<\sqrt{V}$，那么我们对每一种 $x$ 去计算一下，我们只要能做到对于一种 $x$，在 $O(n)$ 的时间内计算完所有需要的区间的答案即可。不妨类似于扫描线那样去做，对于右端点维护所有左端点的答案。
发现对于左端点，其一段的答案可行，另一段不可行，于是我们贪心的取位置最靠右的可行的左端点，对于查询的左端点在其左侧的可行，否则不可行。
怎么找到这个最靠右的点？对于当前右端点的数 $a_{x}$，它可以作为除数或者被除数，分别枚举这两种情况，记录下每种数最后出现的位置，就可以轻松找到啦。
注意特判一下一些情况。
时间复杂度 $O(\dfrac{nm}{w}+n\sqrt{n})$，有些许卡常，用一些时间优化小技巧即可。

参考代码

远古代码。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int N=1e5;
int n,m,B,cnt1,cnt2,a[MAXN],belong[MAXN],t[MAXN],last[MAXN];
bitset<MAXN> ans,num,num2;
struct q1{int opt,l,r,x,id;}Q1[MAXN];
struct q2{int l,r,x,id;}Q2[MAXN];
bool cmp1(q1 n1,q1 n2){return belong[n1.l]==belong[n2.l]?n1.r<n2.r:n1.l<n2.l;}
bool cmp2(q2 n1,q2 n2){return n1.x==n2.x?n1.r<n2.r:n1.x<n2.x;}
void inc(int a){if(t[a]==0) num[a]=num2[N-a]=1;t[a]++;}
void dec(int a){t[a]--;if(t[a]==0) num[a]=num2[N-a]=0;}
bool work1(int x){for(int i=1;i<=int(sqrt(x));i++) if(x%i==0&&num[i]&&num[x/i]) return 1;return 0;}
bool work2(int x){for(int i=1;i<=int(N/x);i++) if(num[i]&&num[i*x]) return 1;return 0;}
void work3(int l,int r,int x){
    memset(last,-1,sizeof(last));
    int L=-1;
    for(int R=1;R<=n;R++){
        last[a[R]]=R;
        if(a[R]%x==0) L=max(L,last[a[R]/x]);
        if(1ll*(a[R]*x)<=N) L=max(L,last[a[R]*x]);
        while(l<r&&Q2[l].r==R){
            ans[Q2[l].id]=(Q2[l].l<=L);
            l++;
        }
    }
}
void solve1(){
    sort(Q1+1,Q1+cnt1+1,cmp1);
    int L=1,R=0,l,r;
    for(int i=1;i<=cnt1;i++){
        l=Q1[i].l;r=Q1[i].r;
        while(l<L) inc(a[--L]);
        while(r>R) inc(a[++R]);
        while(l>L) dec(a[L++]);
        while(r<R) dec(a[R--]);
        if(Q1[i].opt==1) ans[Q1[i].id]=((num<<Q1[i].x)&num).any();
        else if(Q1[i].opt==2) ans[Q1[i].id]=((num<<(N-Q1[i].x))&num2).any();
        else if(Q1[i].opt==3) ans[Q1[i].id]=work1(Q1[i].x);
        else ans[Q1[i].id]=work2(Q1[i].x);
    }
}
void solve2(){
    if(cnt2==0) return;
    sort(Q2+1,Q2+cnt2+1,cmp2);
    int i=2,j=1,x=Q2[1].x;
    for(;i<=cnt2;i++){
        if(Q2[i].x!=x){
            work3(j,i,x);
            j=i;x=Q2[i].x;
        }
    }
    work3(j,i,x);
}
int main(){
    cin>>n>>m;
    B=sqrt(N);
    for(int i=1;i<=n;i++) belong[i]=(i-1)/B+1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        int opt,l,r,x;
        cin>>opt>>l>>r>>x;
        if(opt==4&&x==0) ans[i]=0;
        else if(opt==4&&x<B) Q2[++cnt2]=(q2){l,r,x,i};
        else Q1[++cnt1]=(q1){opt,l,r,x,i};
    }
    solve1();
    solve2();
    for(int i=1;i<=m;i++) cout<<(ans[i]?"yuno":"yumi")<<endl;
    return 0;
}

T11

Luogu：CF1967C Fenwick Tree
CF：C. Fenwick Tree

题意简述

对于数组 $a$，有函数 $f(a)$，设数组 $s=f(a)$，则对于每一个 $s_ k$，都有：

\[ s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353 \]

对于一个正整数 $k$，函数 $f^k (a)$ 定义如下：

\[ f^k(a)= \begin{cases} f(a)&\textrm{if }k=1\\ f(f^{k-1}(a))&\textrm{otherwise.}\\ \end{cases} \]

给你正整数 $n,k$ 和一个长度为 $n$ 的数组 $b$ 表示 $f ^k (a)$，求一个符合题意的数组 $a$，可以证明答案总是存在的。

$1\le n\le 2\times 10^5,1\le k\le 10^9,0\le b_i< 998\,244\,353$。

思路

Hint1

手玩一下样例，你发现这道题本质上在问什么？
结合一下题面式子中的lowbit，你想到了什么？

Hint2

画出一个树状数组的样子，发现我们只需要算出每个叶子节点对上面节点的贡献即可。

Hint3

只考虑一个叶子对上面的某个点的贡献，怎么计算？
不妨模拟一下贡献的过程。

Solution

假设距离上面某个点的距离为 $d$，那么贡献的系数就应该是，从叶子这个点，总共往上走 $k$ 次，每次可以不动也可以往上走任意多步（当然不能走过）的方案数。
这个等价于你有 $k$ 个小球，需要插 $d$ 个板，方案数显然是 $C_{d+k-1}^{k-1}$。
发现 $k$ 很大但是 BIT 的层数很小，也就是说你每次从某个叶子节点开始，一直跳父亲，计算贡献即可。具体的，你对于当前父亲的贡献是 $C_{d+k-1}^{k-1}$，那么你对这个父亲的父亲的贡献是 $C_{d+1+k-1}^{k-1}$。将组合数展开可以得到 $O(1)$ 的转移式子。

参考代码

// Problem: Fenwick Tree
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1967C
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int t,val[MAXN],ans[MAXN];

int lowbit(int u){return u&(-u);}

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=res*x%mod2;
        x=x*x%mod2;
        y>>=1;
    }
    return res;
}

signed main(){
    read(t);
    while(t--){
        int n,k;
        read(n,k);
        for(int i=1;i<=n;i++) read(val[i]);
        for(int i=1;i<=n;i++) ans[i]=val[i];
        for(int j=1;j<=n;j++){
            int pos=j+lowbit(j),cnt=1,C=1;
            while(pos<=n&&cnt<=k){
                C=(-C*(k-cnt+1)%mod2*qpow(cnt,mod2-2)%mod2+mod2)%mod2;
                ans[pos]=(ans[pos]+C*val[j]%mod2)%mod2;
                pos+=lowbit(pos);
                cnt++;
            }
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

T12

P4175 [CTSC2008] 网络管理

题意简述

给定一棵 $n$ 个点的树，有点权。有两种操作，修改某个点的点权，查询一段路径上的点权第 $k$ 大。

思路

Hint1

不妨考虑简单一点的问题，树是一条链怎么做？
也就是给定一个序列，修改某个点的值，查询区间第 $k$ 大。

Hint2

没有修改很简单对吧，就是主席树板子。
这里找到一道题：P1533 可怜的狗狗。
有修改其实就是这道题：P2617 Dynamic Rankings
有两种做法，一种叫做带修主席树，一种叫做整体二分，我们两个都简单提一下。

带修主席树

所谓带修主席树，本质是树状数组套线段树。
我们来重温一下主席树是怎么用的。
本质是维护了前缀和，查询的时候两棵线段树一减，就是该区间的权值线段树。
那我们带修了后，每次就需要修改后面所有的位置的线段树，也就是单次修改就需要修改 $O(n\log n)$ 个节点，显然会 TLE。
那我们怎么快速维护这么一段区间的前缀和呢？

树状数组可以单点修改区间查询对吧。那么我们不妨在树状数组上的某个点都开一棵权值线段树。
那么我们在修改的时候，只会修改 $O(\log n)$ 个树状数组上的点，再往下每个点又会改 $O(\log n)$ 个对应权值线段树上的点，总共修改的时间复杂度就是 $O(\log ^2n)$。
同样的，在查询的时候，我们也会查询 $O(\log n )$ 个权值线段树的和再减去 $O(\log n)$ 个权值线段树的和。

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

整体二分

这是一个离线算法。
不妨先想想查询区间第 $k$ 大怎么用二分来做。
我们二分权值来检验答案，假设当前检验的值为 $mid$，统计区间内小于 $mid$ 的数的个数，再决定继续往哪个区间二分。这样的时间复杂度是 $O(n\log n)$。显然多次询问就爆炸了。
我们发现，假如我现在有一些询问的区间二分的过程有重复，那么我先前那样去做，就很慢了。我们对于有重复的，一起处理即可。找到区间小于某个数的个数可以使用树状数组简单求出。
然后再根据结果，把询问分成两部分，一部分下次二分区间为 $[l,mid]$，另一部分为 $[mid+1,r]$。
可以分析得出时间复杂度为 $O((n+m)\log^2 V)$。

那么带修怎么做呢？
不难想到我们把修改同样放进二分的过程中，显然是需要按照时间顺序的依次处理的。时间复杂度不变。
细节比较多，有问题可以问我或者看看代码自行理解。

Hint3

树上怎么做呢？

Solution

其实直接套一个树剖就好了对吧。时间复杂度 $O(n\log^3n)$，能过。套带修主席树或者整体二分都是可以的。
存在使用 dfn 序改为区间修改并使用带修主席树或者整体二分的 $O(n\log^2n)$ 做法。
细节有亿点多。

参考代码

带修区间第 $k$ 大整体二分参考代码

// Problem: P2617 Dynamic Rankings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2617
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,tot,cnt,ans[MAXN],b[MAXN],t[MAXN],val[MAXN];
struct node{
    int type,l,r,k,pos,val,id;
}q[MAXN],q1[MAXN],q2[MAXN];

int lowbit(int u){return u&(-u);}

void update(int pos,int val){
    while(pos<=n){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=0;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

bool cmp(node n1,node n2){
    return n1.id<n2.id;
}

void work(int l,int r,int L,int R){
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    if(l==r){
        for(int i=L;i<=R;i++) if(!q[i].type) ans[q[i].id]=b[l];
        return;
    }
    for(int i=L;i<=R;i++){
        if(q[i].type){
            if(q[i].val<=mid){
                update(q[i].pos,q[i].k);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else{
            int val=query(q[i].r)-query(q[i].l-1);
            if(val>=q[i].k) q1[++cnt1]=q[i];
            else q[i].k-=val,q2[++cnt2]=q[i];
        }
    }
    for(int i=L;i<=L+cnt1-1;i++) q[i]=q1[i-L+1];
    for(int i=L+cnt1;i<=R;i++) q[i]=q2[i-L-cnt1+1];
    for(int i=L;i<=L+cnt1-1;i++) if(q[i].type) update(q[i].pos,-q[i].k);
    work(l,mid,L,L+cnt1-1);
    work(mid+1,r,L+cnt1,R);
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=1;i<=n;i++) q[++tot].type=1,q[tot].pos=i,q[tot].val=val[i],q[tot].id=tot,q[tot].k=1;
    for(int i=1;i<=m;i++){
        char opt;
        cin>>opt;
        if(opt=='Q'){
            q[++tot].type=0;
            q[tot].id=tot;
            cin>>q[tot].l>>q[tot].r>>q[tot].k;
        }
        else{
            q[++tot].type=1;
            q[tot].id=tot;
            q[tot].k=1;
            cin>>q[tot].pos>>q[tot].val;
            q[++tot].type=1;
            q[tot].id=tot;
            q[tot].k=-1;
            q[tot].pos=q[tot-1].pos;
            q[tot].val=val[q[tot].pos];
            swap(q[tot],q[tot-1]);
            swap(q[tot].id,q[tot-1].id);
            val[q[tot].pos]=q[tot].val;
        }
    }
    for(int i=1;i<=tot;i++) if(q[i].type) b[++cnt]=q[i].val;
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=tot;i++) if(q[i].type) q[i].val=lower_bound(b+1,b+cnt+1,q[i].val)-b;
    work(1,cnt,1,tot);
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;i++) if(!q[i].type) cout<<ans[i]<<endl;
    return 0;
}

本题参考代码

// Problem: P4175 [CTSC2008] 网络管理
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4175
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,tot,cnt,Cnt,k,b[MAXN],top[MAXN],siz[MAXN],hson[MAXN],head[MAXN],ans[MAXN],val[MAXN],dep[MAXN],fa[MAXN],dfsnum[MAXN],dfsnod[MAXN];
struct node{
    int to,next;
}edge[MAXN];
struct node2{
    int type,id,u,v,k,pos,val;
}q[MAXN],q1[MAXN],q2[MAXN];
struct node3{
    int l,r,val;
}tree[MAXN<<2];

bool cmp(node2 n1,node2 n2){
    return n1.id<n2.id;
}

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void dfs(int u,int f){
    siz[u]=1;
    int maxsiz=0;
    hson[u]=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs(v,u);
        siz[u]+=siz[v];
        if(maxsiz<siz[v]){
            maxsiz=siz[v];
            hson[u]=v;
        }
    }
}

void dfs2(int u,int f){
    top[u]=f;
    dfsnum[u]=++cnt;
    dfsnod[cnt]=u;
    if(hson[u]==0) return;
    dfs2(hson[u],f);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[u]||v==hson[u]) continue;
        dfs2(v,v);
    }
}

void pushup(int id){tree[id].val=tree[id*2].val+tree[id*2+1].val;}

void build_tree(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build_tree(id*2,l,mid);
    build_tree(id*2+1,mid+1,r);
}

void update(int id,int l,int r,int pos,int val){
    if(l==r){
        tree[id].val+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(id*2,l,mid,pos,val);
    else update(id*2+1,mid+1,r,pos,val);
    pushup(id);
}

int query(int id,int l,int r,int L,int R){
    if(r<L||R<l) return 0;
    if(L<=l&&r<=R) return tree[id].val;
    int res=0,mid=(l+r)>>1;
    if(L<=mid) res+=query(id*2,l,mid,L,R);
    if(R>mid) res+=query(id*2+1,mid+1,r,L,R);
    return res;
}

int ask(int u,int v){
    int res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=query(1,1,n,dfsnum[top[u]],dfsnum[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    res+=query(1,1,n,dfsnum[v],dfsnum[u]);
    return res;
}

int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}

void work(int l,int r,int L,int R){
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    if(l==r){
        for(int i=L;i<=R;i++) if(q[i].type==0) ans[q[i].id]=b[l];
        return;
    }
    for(int i=L;i<=R;i++){
        if(q[i].type==1){
            if(q[i].val<=mid){
                update(1,1,n,dfsnum[q[i].pos],q[i].k);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        if(q[i].type==0){
            int val=ask(q[i].u,q[i].v);
            if(val>=q[i].k) q1[++cnt1]=q[i];
            else q[i].k-=val,q2[++cnt2]=q[i];
        }
        if(q[i].type==-1) q1[++cnt1]=q[i];
    }
    for(int i=L;i<=L+cnt1-1;i++) q[i]=q1[i-L+1];
    for(int i=L+cnt1;i<=R;i++) q[i]=q2[i-L-cnt1+1];
    for(int i=L;i<=L+cnt1-1;i++) if(q[i].type) update(1,1,n,dfsnum[q[i].pos],-q[i].k);
    work(l,mid,L,L+cnt1-1);
    work(mid+1,r,L+cnt1,R);
}

signed main(){
    read(n,m);
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        build(u,v);
        build(v,u);
    }
    dfs(1,1);
    dfs2(1,1);
    build_tree(1,1,n);
    for(int i=1;i<=n;i++){tot++;q[tot].val=val[i];q[tot].id=tot;q[tot].pos=i;q[tot].k=1;q[tot].type=1;}
    for(int i=1;i<=m;i++){
        int A,B,C;
        read(A,B,C);
        if(A==0){
            tot++;q[tot].val=val[B];q[tot].id=tot;q[tot].pos=B;q[tot].k=-1;q[tot].type=1;
            tot++;q[tot].val=C;q[tot].id=tot;q[tot].pos=B;q[tot].k=1;q[tot].type=1;
            val[B]=C;
        }
        else{
            int p=dep[B]+dep[C]-2*dep[lca(B,C)]+1;
            if(p<A){tot++;q[tot].type=-1;q[tot].id=tot;}
            else{tot++;q[tot].u=B;q[tot].v=C;q[tot].type=0;q[tot].id=tot;q[tot].k=p-A+1;}
        }
    }
    for(int i=1;i<=tot;i++) if(q[i].type==1) b[++Cnt]=q[i].val;
    sort(b+1,b+Cnt+1);
    Cnt=unique(b+1,b+Cnt+1)-b-1;
    for(int i=1;i<=tot;i++) if(q[i].type==1) q[i].val=lower_bound(b+1,b+Cnt+1,q[i].val)-b;
    work(1,Cnt,1,tot);
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        if(q[i].type==0) cout<<ans[i]<<endl;
        if(q[i].type==-1) cout<<"invalid request!\n";
    }
    return 0;
}

T13

Luogu：CF896C Willem, Chtholly and Seniorious
CF：C. Willem, Chtholly and Seniorious

题意简述

给定一个长度为 $n$ 的序列，请你维护以下四种操作：

将 $[l,r]$ 区间所有数加上 $x$。
将 $[l,r]$ 区间所有数改成 $x$。
输出 $[l,r]$ 区间的第 $k$ 小。
输出 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值。

共 $m$ 次操作。

$1\le n,m\le10^5$，保证数据随机。

思路

Hint1

随机数据！先想想暴力怎么做，并考虑优化。

Hint2

暴力很简单对吧，$O(n^2)$。
有覆盖操作，我们不妨把相同的数统一起来处理？

Solution

ODT，全称 Old Driver Tree，中文称作珂朵莉数或者老司机树，也可称为颜色段均摊。
在数据保证随机的情况下，并且会出现区间覆盖之类的类似操作时，会有优异的时间复杂度。

因为数据随机，所以有 $\dfrac{1}{4}$ 的概率会出将一段区间覆盖的操作。
我们维护一下数列中连续的相同的数，比如 $[l,r]$ 区间都是 $val$。

那么我们怎么维护上述四种操作呢？
直接暴力去做就好了。
区间加，直接把 $[l,r]$ 区间内维护的所有东西拿出来，直接将 $val$ 增加即可。
区间覆盖，直接把 $[l,r]$ 区间内原本维护的全部删掉，插入一个新的区间为 $[l,r]$，值为 $x$ 的节点。
区间第 $k$ 小，把 $[l,r]$ 区间拿出来，排序，从前往后找即可。
第四个操作，同样拿出来，直接计算即可。

我们发现，有时候一段区间不会完整的被拿出来，我们这时候直接将其断开，变成两个区间即可。
具体可以看代码。

参考代码

// Problem: CF896C Willem, Chtholly and Seniorious
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF896C
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,seed,v_max,a[MAXN];
struct node{
    int l,r;
    mutable int val;
    node(int L,int R=-1,int z=0){l=L,r=R,val=z;}
    bool operator <(const node &a) const{
        return l<a.l;
    }
};

//ODT 的一个点一般就像上面那样定义。  
//mutable 意为可变的，与 const 相反，定义了后，可以直接在 set 中改该变量的值。

set<node> s;

int next_rand(){
    int ret=seed;
    seed=(seed*7+13)%mod1;
    return ret;
}

int qpow(int x,int y,int mod){
    x%=mod;
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

auto split(int pos){
    auto z=s.lower_bound(node(pos));
    if(z!=s.end()&&z->l==pos) return z;
    z--;
    int l=z->l,r=z->r,val=z->val;
    s.erase(z);
    s.insert(node(l,pos-1,val));
    return s.insert(node(pos,r,val)).first;
}

void change(int l,int r,int val){
    auto R=split(r+1),L=split(l);
    s.erase(L,R);
    s.insert(node(l,r,val));
}

void add(int l,int r,int val){
    auto R=split(r+1),L=split(l);
    for(auto i=L;i!=R;i++) i->val+=val;//这里的 val 就直接改了。
}

int kth(int l,int r,int pos){
    auto R=split(r+1),L=split(l);
    vector<pair<int,int> > p;
    for(auto i=L;i!=R;i++) p.push_back(make_pair(i->val,i->r-i->l+1));
    sort(p.begin(),p.end());
    for(auto i:p){
        pos-=i.second;
        if(pos<=0) return i.first;
    }
}

int qmi(int l,int r,int x,int mod){
    auto R=split(r+1),L=split(l);
    int res=0;
    for(auto i=L;i!=R;i++) (res+=(i->r-i->l+1)*qpow(i->val,x,mod)%mod)%=mod;
    return res;
}

signed main(){
    read(n,m,seed,v_max);
    for(int i=1;i<=n;i++) a[i]=(next_rand()%v_max)+1;
    for(int i=1;i<=n;i++) s.insert(node(i,i,a[i]));
    for(int i=1;i<=m;i++){
        int op=(next_rand()%4)+1;
        int l=(next_rand()%n)+1;
        int r=(next_rand()%n)+1;
        int x,y;
        if(l>r) swap(l,r);
        if(op==3) x=(next_rand()%(r-l+1))+1;
        else x=(next_rand()%v_max)+1;
        if(op==4) y=(next_rand()%v_max)+1;
        if(op==1) add(l,r,x);
        if(op==2) change(l,r,x);
        if(op==3) cout<<kth(l,r,x)<<'\n';
        if(op==4) cout<<qmi(l,r,x,y)<<'\n';
    }
    return 0;
}

T14

P10626 [JOI Open 2024] 考试 2

题意简述

（这个真不好简述。）

JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 IOI 函数。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\texttt{True}/\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造：

设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\texttt{[a]}$ 是一个 IOI 函数。它将不小于 $a$ 的整数映射成 $\texttt{True}$，将小于 $a$ 的整数映射成 $\texttt{False}$。
记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{(f)}$ 是一个 IOI 函数，它的映射规则与 $\texttt{f}$ 的映射规则相同。
记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{!f}$ 是一个 IOI 函数。设 $x$ 为整数，若 $\texttt{f}$ 将 $x$ 映射为 $\texttt{True}$，则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{False}$；否则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{True}$。
记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\&g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\&g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 都将 $x$ 映射为 $\texttt{True}$。
记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\^ g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\^ g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中恰好有一个将 $x$ 映射为 $\texttt{True}$。
记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f|g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f|g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中至少有一个将 $x$ 映射为 $\texttt{True}$。

越前面的规则优先级越高。

为备战期末考试，JOI 君准备好了一个长度为 $N$ 的 IOI 函数 $S$。他打算用 $Q$ 个整数 $X_1,X_2,\cdots,X_Q$ 来练习他的计算技能。于是他找来了你——能够熟练处理 IOI 函数的人，来解决这个问题。

你需要写一个程序。给定 $N,Q,S$ 以及 $X_1,X_2,\cdots,X_Q$，对于 $i=1,2=\cdots,Q$，回答 IOI 函数 $S$ 会将 $X_i$ 映射成 $\texttt{True}$ 还是 $\texttt{False}$。

$1 \le N \le 1\,000\,000$；
$1 \le Q \le 200\,000$；
$S$ 为长度为 $N$ 的 IOI 函数；
$1 \le X_i \le 10^9$（$1 \le i \le Q$）；
$N, Q, X_i$（$1 \le i \le Q$）均为整数。

思路

Hint1

暴力很显然吧，直接模拟即可。时间复杂度 $O(nq)$。
想办法优化一点吧。

Hint2

有一个东西叫做表达式树。
我们发现将询问离线下来，并从小到大排序后，我们对于最下面每个 IOI 函数，只会更改一次，并且会对其上一整条链修改。

Hint3

挨个挨个往上改一条链太慢了，最慢会是 $O(n)$ 的，有什么办法可以加速吗？

Hint4

树剖可以将树上任意一条路径拆成 $O(\log n)$ 段。
那么我们假如可以一次修改一整段，那么便可以只修改 $O(\log n)$ 次。
那么怎么一次修改一整段呢？
注意：表达式树有个特性，每个点至多有两个儿子。

Hint5

你有没有发现什么问题？对于表达式树上的一个点，其最多有一个重儿子和一个轻儿子。这俩共同决定了 IOI 函数的值。你在统一修改整条链的时候，轻儿子也是会产生影响的，这个影响怎么处理？

Hint6

我们不妨对于轻儿子的情况讨论一下。
假如对于当前表达式树上的某个点，其为&。
轻儿子的值为 $1$，不难定义这个点有一个函数 $f(x)=x$，表示重儿子的值为 $x$ 时，这个点的答案是多少。
不难发现查询答案，其实就是求根所在的这条重链的所有点的函数的复合。

函数的复合：我们有 $f(x)$ 和 $g(x)$ 两个函数，称 $(f \circ g)(x)$ 为函数 $f(x)$ 与函数 $g(x)$ 的复合，其值等于 $f(g(x))$。

那么我们怎么去求这么多函数的复合呢？

Solution

DDP（动态 DP）

动态 DP 可以用于解决上述问题，通常基于普通的树形 DP。
我们在写出朴素的树形 DP 式子后，发现题目中要求你修改值，如果你暴力重新从下面往上重新计算 DP 值，时间复杂度就爆炸了。此时，你可以考虑一下 DDP。

具体过程大致如下：

改写 DP 式：将原本树形 DP 式子拆开（原本通常是枚举所有儿子进行转移），拆成轻儿子和重儿子两部分。那么我们在更改的时候，只会更改这一条重链的信息。
改写成矩阵乘法：如上文所言，我们发现要求函数的复合，矩阵乘法可以做到这一点。这里的矩阵乘法可能并不是传统意义上的矩阵乘法，而是广义上的，比如 DDP 模板题就不是传统的矩阵乘法。

广义矩阵乘法

一般的矩阵乘法，我们不妨称其为乘-加矩阵运算，回忆矩阵乘法的步骤你们就可以明白含义。
有时候我们根据题目写出的 DP 式子，可能一般的矩阵乘法不能做到，我们就可以修改一下，比如改成加-max矩阵运算，类比上面的，你应该能明白是什么意思。
这就叫做广义矩阵乘法。
需要注意的是，并不是随便怎么运算都是可行的。需要满足结合律才可行。一般而言，如果你两个运算都具有结合律就行了，最好的话，可以自己严谨带参算一下。

对于我们这道题而言，你可能说他不是 DP 式子，但实际上可以说是。
我们计算某个点，其实就是前面举例中的 $f(x)=x$，这其实也是 DP 式，并且我们前面 Hint 中提到它会根据轻儿子变化来改变。

我们第一步就已经做到了。接下来就是写矩乘了。
我们不妨定义一个 $2\times2$ 的矩阵来表达状态，第一行中 $\begin{bmatrix}0&1\end{bmatrix}$ 表示这个点的值为 $1$，$\begin{bmatrix}1&0\end{bmatrix}$ 表示这个点的值为 $0$。
我们来举一个例子即可，其他的自行尝试推导一下。
假如当前点符号为&，轻儿子为 $1$，那么我们的矩阵可以选择朴素的矩乘，转移矩阵就是 $\begin{bmatrix}1&0\\0&1\end{bmatrix}$。

那么我们从下往上修改的时候，因为矩乘具有结合律，直接修改值，在线段树上合并一下，得出新的复合矩阵。下一步该是跳链了，我们根据当前所在的链的复合结果，来决定链顶的父亲的矩阵是否需要修改。

最后查询直接查询根所在的重链的复合即可。

细节有亿点点多。

其实有一种更简单的线段树合并的做法，这个你们可以自行思考一下。

至于建表达式树，类似于表达式求值那样即可，用两个栈来维护。

这道题目中的!有点烦人，我调了很久都是因为这个东西，有两种处理方式：
1. 定义矩阵的时候多定义一倍的矩阵。
2. 将!也加入表达式树中。

我写的时候写的是第一种，就会出现更多的细节，建议使用第二种。

参考代码

// Problem: P10626 [JOI Open 2024] 考试 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10626
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

bool awa;
int n,q,cnt,node_cnt,k,leaf_pos,lastans,top1,top2;
int fa[MAXN],hson[MAXN],siz[MAXN],top[MAXN],down[MAXN],dfsnum[MAXN],dfsnod[MAXN],dep[MAXN];
int head[MAXN],sta2[MAXN],son[MAXN][2];
vector<pair<int,int> > leaf;
bool ans[MAXN],z[MAXN],vis[MAXN],is_leaf[MAXN],rev[MAXN],REV;
char s[MAXN],type[MAXN],sta1[MAXN];

struct mat{
    bool s[2][2];
    mat(){memset(s,0,sizeof(s));}
    mat operator * (mat t){
        mat res;
        res.s[0][0]=(s[0][0]*t.s[0][0])+(s[0][1]*t.s[1][0]);
        res.s[0][1]=(s[0][0]*t.s[0][1])+(s[0][1]*t.s[1][1]);
        res.s[1][0]=(s[1][0]*t.s[0][0])+(s[1][1]*t.s[1][0]);
        res.s[1][1]=(s[1][0]*t.s[0][1])+(s[1][1]*t.s[1][1]);
        return res;
    }
    friend bool operator == (mat n1,mat n2){
        if(n1.s[0][0]!=n2.s[0][0]) return false;
        if(n1.s[0][1]!=n2.s[0][1]) return false;
        if(n1.s[1][0]!=n2.s[1][0]) return false;
        if(n1.s[1][1]!=n2.s[1][1]) return false;
        return true;
    }
}opt[3][2][2],stdmat;

//opt[0] &
//opt[1] ^
//opt[2] |

struct node{
    int val,id;
}que[MAXN];

struct node2{
    int to,next;
}edge[MAXN<<2];

struct node3{
    int l,r;
    mat val;
}tree[MAXN<<2];

bool cmp(node n1,node n2){
    return n1.val<n2.val;
}

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void pre(){
    opt[0][0][0].s[0][0]=1;opt[0][0][0].s[0][1]=0;
    opt[0][0][0].s[1][0]=1;opt[0][0][0].s[1][1]=0;
    
    opt[0][1][0].s[0][0]=1;opt[0][1][0].s[0][1]=0;
    opt[0][1][0].s[1][0]=0;opt[0][1][0].s[1][1]=1;
    
    opt[1][0][0].s[0][0]=1;opt[1][0][0].s[0][1]=0;
    opt[1][0][0].s[1][0]=0;opt[1][0][0].s[1][1]=1;
    
    opt[1][1][0].s[0][0]=0;opt[1][1][0].s[0][1]=1;
    opt[1][1][0].s[1][0]=1;opt[1][1][0].s[1][1]=0;
    
    opt[2][0][0].s[0][0]=1;opt[2][0][0].s[0][1]=0;
    opt[2][0][0].s[1][0]=0;opt[2][0][0].s[1][1]=1;
    
    opt[2][1][0].s[0][0]=0;opt[2][1][0].s[0][1]=1;
    opt[2][1][0].s[1][0]=0;opt[2][1][0].s[1][1]=1;
    
    opt[0][0][1]=opt[2][1][0];
    opt[0][1][1]=opt[1][1][0];
    opt[1][0][1]=opt[1][1][0];
    opt[1][1][1]=opt[2][0][0];
    opt[2][0][1]=opt[1][1][0];
    opt[2][1][1]=opt[0][0][0];
    
    stdmat.s[0][0]=1;stdmat.s[0][1]=0;
    stdmat.s[1][0]=0;stdmat.s[1][1]=1;
}

void build_expression_tree(){
    for(int i=1;i<=n;){
        if(s[i]=='(') sta1[++top1]='(',rev[n+top1]=REV,REV=0;
        if(s[i]==')'){
            while(sta1[top1]!='('){
                son[++node_cnt][0]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                son[node_cnt][1]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                type[node_cnt]=sta1[top1--];
                sta2[++top2]=node_cnt;
            }
            rev[node_cnt]=rev[n+top1];
            top1--;
        }
        if(s[i]=='!') REV^=1;
        if(s[i]=='['){
            char ch=s[++i];
            int val=0;
            while(ch>='0'&&ch<='9'){
                val=val*10+ch-'0';
                ch=s[++i];
            }
            leaf.push_back({val,++node_cnt});
            is_leaf[node_cnt]=true;
            z[node_cnt]=REV;
            rev[node_cnt]=REV;
            REV=0;
            sta2[++top2]=node_cnt;
        }
        if(s[i]=='&'){
            while(sta1[top1]=='&'){
                son[++node_cnt][0]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                son[node_cnt][1]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                type[node_cnt]=sta1[top1--];
                sta2[++top2]=node_cnt;
            }
            sta1[++top1]='&';
        }
        if(s[i]=='^'){
            while(sta1[top1]=='&'||sta1[top1]=='^'){
                son[++node_cnt][0]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                son[node_cnt][1]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                type[node_cnt]=sta1[top1--];
                sta2[++top2]=node_cnt;
            }
            sta1[++top1]='^';
        }
        if(s[i]=='|'){
            while(sta1[top1]=='&'||sta1[top1]=='^'||sta1[top1]=='|'){
                son[++node_cnt][0]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                son[node_cnt][1]=sta2[top2];
                build(sta2[top2],node_cnt);
                build(node_cnt,sta2[top2--]);
                type[node_cnt]=sta1[top1--];
                sta2[++top2]=node_cnt;
            }
            sta1[++top1]='|';
        }
        i++;
    }
    while(top1){
        if(sta1[top1]=='!') break;
        son[++node_cnt][0]=sta2[top2];
        build(sta2[top2],node_cnt);
        build(node_cnt,sta2[top2--]);
        son[node_cnt][1]=sta2[top2];
        build(sta2[top2],node_cnt);
        build(node_cnt,sta2[top2--]);
        type[node_cnt]=sta1[top1--];
        sta2[++top2]=node_cnt;
    }
}

void dfs(int u){
    vis[u]=true;
    int maxsiz=0;
    siz[u]=1;
    down[u]=hson[u]=u;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]) continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs(v);
        if(maxsiz<siz[v]){
            down[u]=down[v];
            maxsiz=siz[v];
            hson[u]=v;
        }
        siz[u]+=siz[v];
    }
    if(type[u]=='|') z[u]=(z[son[u][0]]|z[son[u][1]])^rev[u];
    if(type[u]=='^') z[u]=(z[son[u][0]]^z[son[u][1]])^rev[u];
    if(type[u]=='&') z[u]=(z[son[u][0]]&z[son[u][1]])^rev[u];
}

void dfs2(int u,int f){
    top[u]=f;
    dfsnum[u]=++cnt;
    dfsnod[cnt]=u;
    if(hson[u]==u) return;
    dfs2(hson[u],f);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[u]||v==hson[u]) continue;
        dfs2(v,v);
    }
}

void pushup(int id){
    tree[id].val=tree[id*2+1].val*tree[id*2].val;
}

void build_tree(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        int xwx=dfsnod[l];
        bool light=hson[xwx]==son[xwx][0];
        if(type[xwx]=='&') tree[id].val=opt[0][z[son[xwx][light]]][rev[xwx]];
        else if(type[xwx]=='^') tree[id].val=opt[1][z[son[xwx][light]]][rev[xwx]];
        else if(type[xwx]=='|') tree[id].val=opt[2][z[son[xwx][light]]][rev[xwx]];
        else{
            tree[id].val.s[0][0]=z[xwx]==0;
            tree[id].val.s[0][1]=z[xwx]==1;
        }
        return;
    }
    int mid=(l+r)>>1;
    build_tree(id*2,l,mid);
    build_tree(id*2+1,mid+1,r);
    pushup(id);
}

void update(int id,int l,int r,int pos){
    if(l==r){
        if(is_leaf[dfsnod[l]]) swap(tree[id].val.s[0][0],tree[id].val.s[0][1]);
        else{
            if(type[dfsnod[l]]=='&') tree[id].val=opt[0][tree[id].val==opt[0][0][rev[dfsnod[l]]]][rev[dfsnod[l]]];
            if(type[dfsnod[l]]=='^') tree[id].val=opt[1][tree[id].val==opt[1][0][rev[dfsnod[l]]]][rev[dfsnod[l]]];
            if(type[dfsnod[l]]=='|') tree[id].val=opt[2][tree[id].val==opt[2][0][rev[dfsnod[l]]]][rev[dfsnod[l]]];
        }
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(id*2,l,mid,pos);
    else update(id*2+1,mid+1,r,pos);
    pushup(id);
}

mat query(int id,int l,int r,int L,int R){
    if(r<L||R<l) return stdmat;
    if(L<=l&&r<=R) return tree[id].val;
    int mid=(l+r)>>1;
    if(L<=mid&&R>mid) return query(id*2+1,mid+1,r,L,R)*query(id*2,l,mid,L,R);
    else if(L<=mid) return query(id*2,l,mid,L,R);
    else if(R>mid) return query(id*2+1,mid+1,r,L,R);
    return stdmat;
}

void change(int pos){
    while(pos){
        mat old=query(1,1,node_cnt,dfsnum[top[pos]],dfsnum[down[pos]]);
        update(1,1,node_cnt,dfsnum[pos]);
        mat now=query(1,1,node_cnt,dfsnum[top[pos]],dfsnum[down[pos]]);
        if(old==now) break;
        pos=fa[top[pos]];
    }
}
bool qwq;

signed main(){
    // cout<<(&awa-&qwq)/1024.0/1024.0<<'\n';
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>s[i];
    pre();build_expression_tree();
    sort(leaf.begin(),leaf.end());
    dfs(node_cnt);
    dfs2(node_cnt,node_cnt);
    build_tree(1,1,node_cnt);
    for(int i=1;i<=q;i++) cin>>que[i].val;
    for(int i=1;i<=q;i++) que[i].id=i;
    sort(que+1,que+q+1,cmp);
    for(int i=1;i<=q;i++){
        while(leaf[leaf_pos].first<=que[i].val&&leaf_pos<leaf.size()) change(leaf[leaf_pos++].second);
        mat val=query(1,1,node_cnt,1,dfsnum[down[node_cnt]]);
        ans[que[i].id]=val.s[0][1]==1;
    }
    for(int i=1;i<=q;i++) cout<<(ans[i]?"True\n":"False\n");
    return 0;
}

T15

P5693 EI 的第六分块

题意简述

给定一个长度为 $n$ 的整数序列 $a$，$q$ 次操作，有以下两种：

给区间 $[l,r]$ 中每个数加上 $x$
查询区间 $[l,r]$ 的最大子段和（可以为空）

$1\le n,q \le 4\times 10^5$，$|a_i| \le 10^9$，$1 \le x \le 10^6$。

思路

Hint1

最大子段和都会对吧。但是现在区间加怎么做呢？
最大子段和，最大前缀和，最大后缀和也能一起加吗？

Hint2

显然是不可以的对吧。
比如这么个序列5 4 -3 2 1。我将 $[3,5]$ 区间增加 $100$，那么区间 $[2,3]$ 的最大子段和从先前的 $[2,2]$ 和为 $4$ 变成了现在的 $[2,3]$ 和为 $101$。
那么你怎么去去掉这个影响或者维护这个影响呢？
~~其实你们要能自己想出来就有国集水平了。~~

Hint3

我们发现，对于一段区间的最大子段和，我们假如将这个区间内所有数增加 $x$，那么这个区间的最大子段和就会增加 $kx$。（$k$ 是区间长度）也就是一个 $y=kx+b$ 的形式，其中，$b$ 式是当前的最大子段和，$k$ 是区间长度，$x$ 是区间统一增加的值，$y$ 是增加后的最大子段和。
同样的，前缀最大和，后缀最大和，和，都可以表示成 $kx+b$ 的形式。

Solution

回忆我们求最大子段和的过程。我们就拿其中一种情况举例。
我们现在要合并左子树和右子树，我们合并后的最大子段和可能是这两段的最大子段和取 $\max$，我们就拿这个举例，其他几种情况是类似的。

按前文所讲，我们这个最大子段和是可以表示成 $kx+b$ 的形式的，那么这两条直线取 $\max$ 有两种情况：

在这个区间内不相交：那么说明在上面那条后面无论再加多少都一定优于下面那条，直接取上面那条即可。
在这个区间内相交了：说明在加到某一时刻时，原本更劣的会变成更优的，我们把这个位置需要记录下来。

那么在全局增加的时候，也就是等价于这个转化点往左挪动了，假如挪到小于等于 $0$ 的位置了，就说明某条线段一定优于另一条了。这时候，我们需要去将原本的最优线段替换掉，暴力往下递归处理即可。

查询即找到区间内最优线段的 $b$。

原论文证明了时间复杂度至多为是 $O(n\log^3 n)$，但能卡满 $O(n\log^3 n)$ 的数据极其难造，一般情况均可看作 $O(n\log^2n)$ 的。

不妨思考一下为什么这道题中 $x$ 保证了大于 $0$。
总结一下，假如你发现你需要维护的东西可以写成 $kx+b$ 的形式的时候，区间加，并且是取最值的时候，走投无路之时可以尝试想一想。

参考代码

// Problem: P5693 EI 的第六分块
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5693
// Memory Limit: 256 MB
// Time Limit: 1800 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const long long inf=1e18;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,a[MAXN],lazy[MAXN<<2];
struct line{
    int k,b;
    friend line operator +(line n1,line n2){
        return (line){n1.k+n2.k,n1.b+n2.b};
    }
    void add(int val){b+=k*val;}
};
struct node{
    int th;
    line premax,sufmax,maxval,sum;
}tree[MAXN<<2];

pair<line,int> max(line n1,line n2){
    if(n1.k<n2.k||(n1.k==n2.k&&n1.b<n2.b)) swap(n1,n2);
    if(n1.b>=n2.b) return make_pair(n1,inf);
    else return make_pair(n2,(n2.b-n1.b)/(n1.k-n2.k));
}

node merge(node n1,node n2){
    node ans;
    pair<line,int> cache;
    ans.th=min(n1.th,n2.th);
    cache=max(n1.premax,n1.sum+n2.premax);
    ans.premax=cache.first;
    ans.th=min(ans.th,cache.second);
    cache=max(n2.sufmax,n1.sufmax+n2.sum);
    ans.sufmax=cache.first;
    ans.th=min(ans.th,cache.second);
    cache=max(n1.maxval,n2.maxval);
    ans.maxval=cache.first;
    ans.th=min(ans.th,cache.second);
    cache=max(ans.maxval,n1.sufmax+n2.premax);
    ans.maxval=cache.first;
    ans.th=min(ans.th,cache.second);
    ans.sum=n1.sum+n2.sum;
    return ans;
}

void pushup(int id){
    tree[id]=merge(tree[id*2],tree[id*2+1]);
}

void pushdown(int id){
    if(lazy[id]==0) return;
    tree[id*2].premax.add(lazy[id]);
    tree[id*2].sufmax.add(lazy[id]);
    tree[id*2].maxval.add(lazy[id]);
    tree[id*2].sum.add(lazy[id]);
    tree[id*2].th-=lazy[id];
    lazy[id*2]+=lazy[id];
    tree[id*2+1].premax.add(lazy[id]);
    tree[id*2+1].sufmax.add(lazy[id]);
    tree[id*2+1].maxval.add(lazy[id]);
    tree[id*2+1].sum.add(lazy[id]);
    tree[id*2+1].th-=lazy[id];
    lazy[id*2+1]+=lazy[id];
    lazy[id]=0;
}

void build(int id,int l,int r){
    if(l==r){
        line now=(line){1,a[l]};
        tree[id]=(node){inf,now,now,now,now};
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}

void rebuild(int id){
    if(tree[id].th>=0) return;
    pushdown(id);
    rebuild(id*2);
    rebuild(id*2+1);
    pushup(id);
}

void update(int id,int l,int r,int L,int R,int val){
    if(L<=l&&r<=R){
        tree[id].premax.add(val);
        tree[id].sufmax.add(val);
        tree[id].maxval.add(val);
        tree[id].sum.add(val);
        lazy[id]+=val;
        tree[id].th-=val;
        rebuild(id);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(id);
    if(L<=mid) update(id*2,l,mid,L,R,val);
    if(R>mid) update(id*2+1,mid+1,r,L,R,val);
    pushup(id);
}

node query(int id,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tree[id];
    int mid=(l+r)>>1;
    pushdown(id);
    if(L<=mid&&R>mid) return merge(query(id*2,l,mid,L,R),query(id*2+1,mid+1,r,L,R));
    else if(L<=mid) return query(id*2,l,mid,L,R);
    else return query(id*2+1,mid+1,r,L,R);
}

signed main(){
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r,x;
        read(op,l,r);
        if(op==1){
            read(x);
            update(1,1,n,l,r,x);
        }
        else cout<<max(0ll,query(1,1,n,l,r).maxval.b)<<'\n';
    }
    return 0;
}

总结

总共选了 $15$ 道题，后 $5$ 道我认为能听懂是最好的，能写出来就更好了，不做强行要求，因为确实是有难度的。
前面的题大家还是尽量写一写。
希望你能从这 $15$ 道题中学到很多有用的内容。
比如知道一些新的套路啊，trick 啊之类的。
总之感谢大家的倾听。

编号	名称	格式	说明
1	插入	\(\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}\)	在当前数列的第 \(posi\) 个数字后插入 \(tot\) 个数字：\(c_1, c_2 \cdots c_{tot}\)；若在数列首插入，则 \(posi\) 为 \(0\)
2	删除	\(\operatorname{DELETE} \ posi \ tot\)	从当前数列的第 \(posi\) 个数字开始连续删除 \(tot\) 个数字
3	修改	\(\operatorname{MAKE-SAME} \ posi \ tot \ c\)	从当前数列的第 \(posi\) 个数字开始的连续 \(tot\) 个数字统一修改为 \(c\)
4	翻转	\(\operatorname{REVERSE} \ posi \ tot\)	取出从当前数列的第 \(posi\) 个数字开始的 \(tot\) 个数字，翻转后放入原来的位置
5	求和	\(\operatorname{GET-SUM} \ posi \ tot\)	计算从当前数列的第 \(posi\) 个数字开始的 \(tot\) 个数字的和并输出
6	求最大子列和	\(\operatorname{MAX-SUM}\)	求出当前数列中和最大的一段子列，并输出最大和

LOADING

ds简单题选讲

前言

T1

题意简述

思路

注意

参考代码

T2

T3

题意简述

碎碎念

思路

参考代码

\(O(n^2)\)

\(O(n\log^2n)\)

\(O(n\log n)\)

T4

题意简述

思路

参考代码

T5

题意简述

思路

空间小优化

参考代码

T6

题意简述

思路

参考代码

T7

题意简述

思路

参考代码

T8

题意简述

思路

参考代码

T9

题意简述

思路

参考代码

T10

题意简述

思路

参考代码

T11

题意简述

思路

参考代码

T12

题意简述

思路

带修主席树

整体二分

参考代码

T13

题意简述

思路

参考代码

T14

题意简述

思路

DDP（动态 DP）

广义矩阵乘法

参考代码

T15

题意简述

思路

参考代码

总结