动态开点线段树使用场景
- \(4 \times n\) 开不下。
- 值域需要平移（有负数）。
什么时候开点
显然，访问的节点不存在时（只会在修改递归时开点）。
trick
区间里面有负数时，\(mid = (l + R – 1) / 2\)。
防止越界。
例如区间 \([-1,0]\)。
开点上限
考虑到 update 一次最多开 \(\log V\) 个点（最多递归 \(\log V\)次）。所以总空间应当开 \(O(m \log n)\)。
代码
#include #define int long longusing namespace std;int tot;int n,q;const int maxn = 4e6+114;struct Node{int val, lt, rt, tag;}tree[maxn];void pushup(int &x){tree[x].val=tree[tree[x].lt].val+tree[tree[x].rt].val;}void addtag(int &x,int l,int r,int v){if(x==0){x=++tot;}tree[x].val+=(r-l+1)*v;tree[x].tag+=v;}void pushdown(int &x,int l,int r){if(l>r) return ;int mid=(l+r)/2;addtag(tree[x].lt,l,mid,tree[x].tag);addtag(tree[x].rt,mid+1,r,tree[x].tag);tree[x].tag=0;}int ask(int &x,int lt,int rt,int l,int r){if(rt<l||r<lt){return 0;}if(l<=lt&&rt<=r){return tree[x].val;}int mid=(lt+rt)/2;pushdown(x,lt,rt);int sum=0;sum+=ask(tree[x].lt,lt,mid,l,r);sum+=ask(tree[x].rt,mid+1,rt,l,r);return sum;}void add(int &x,int lt,int rt,int l,int r,int v){if(rt<l||r<lt){return ;}if(l<=lt&&rt>n>>q;root=++tot;for(int i=1;i>x;add(root,1,n,i,i,x);}for(int i=1;i>op;if(op==1){int x,y,k;cin>>x>>y>>k;add(root,1,n,x,y,k);}else{int x,y;cin>>x>>y;cout<<ask(root,1,n,x,y)<<'\n';}}}例题 1
题目传送门
化简题意得维护一个 01 区间，维护区间覆盖，取反以及查询第一个出现的 0。
显然这个很鬼畜。
首先考虑怎么回答询问。
可以维护区间和，然后在线段树上二分。
然后考虑覆盖。
这个很显然可以维护一个覆盖标记。
那取反呢？
可以当取反和覆盖标记在同一节点时强制消除一个。
显然，取反就是让覆盖标记也取反。
那么就可以写出代码了。
#include#define int long longusing namespace std;const int maxn = 4e6+1140;const int inf = 1e18;int tot;struct Node{long long lc,rc,val,tag1,tag2;}tree[maxn];//val 表示区间中 1 的个数 void pushup(int x){tree[x].val=tree[tree[x].lc].val+tree[tree[x].rc].val;}void addtag1(int &x,int lt,int rt,int tag)/*翻转*/{if(x==0) x=++tot;if(tag==0) return ;if(tree[x].tag1==1){tree[x].tag1=0;tree[x].val=(rt-lt+1)-tree[x].val;return ;}tree[x].tag1=1;if(tree[x].tag2!=0){tree[x].tag1=0;tree[x].tag2=((tree[x].tag2-1)^1)+1;tree[x].val=(tree[x].tag2-1)*(rt-lt+1);return ;}tree[x].val=(rt-lt+1)-tree[x].val;return ;}void addtag2(int &x,int lt,int rt,int tag){if(x==0) x=++tot;if(tag==0) return ;tree[x].tag1=0;tree[x].val=(tag-1)*(rt-lt+1);tree[x].tag2=tag;//cout<<x<<' '<<lt<<' '<<rt<<'\n';//cout<<lt<<' '<<rt<<' '<<tree[x].val<=rt) return ;int mid = (lt+rt-1)/2;addtag1(tree[x].lc,lt,mid,tree[x].tag1);addtag1(tree[x].rc,mid+1,rt,tree[x].tag1);tree[x].tag1=0;addtag2(tree[x].lc,lt,mid,tree[x].tag2);addtag2(tree[x].rc,mid+1,rt,tree[x].tag2);tree[x].tag2=0;}void reve(int &x,int l,int r,int lt,int rt){if(rrt) return ;if(r=lt){addtag1(x,l,r,1);return ;}int mid=(l+r-1)/2;pushdown(x,l,r);reve(tree[x].lc,l,mid,lt,rt);reve(tree[x].rc,mid+1,r,lt,rt);pushup(x);}void cover(int &x,int l,int r,int lt,int rt,int tag){if(rrt) return ;if(r=lt){//cout<<"c:"<<l<<' '<<r<<'\n';addtag2(x,l,r,tag);return ;}int mid=(l+r-1)/2;pushdown(x,l,r);cover(tree[x].lc,l,mid,lt,rt,tag);cover(tree[x].rc,mid+1,r,lt,rt,tag);pushup(x);}int query(int &x,int l,int r){if(l==r){return l;}pushdown(x,l,r);int mid = (l+r-1)/2;if(tree[tree[x].lc].val<(mid-l+1)){return query(tree[x].lc,l,mid);}else{return query(tree[x].rc,mid+1,r);}}int ask(int &x,int l,int r,int lt,int rt){if(rrt) return 0;if(r=lt) return tree[x].val;int mid=(l+r-1)/2;int sum=0;pushdown(x,l,r);sum+=ask(tree[x].lc,l,mid,lt,rt);sum+=ask(tree[x].rc,mid+1,r,lt,rt);return sum;}inline int read(){ int x=0,f=1; char ch=getchar(); while(ch'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}inline void write(int x) { if (x 9) write(x / 10); putchar(x % 10 + '0'); }int n,q,root;signed main(){q=read();n=inf;root=1,tot=1;while(q--){int op;op=read();if(op==1){int l,r;l=read();r=read();cover(root,1,n,l,r,2);}else if(op==2){int l,r;l=read(),r=read();cover(root,1,n,l,r,1);}else{int l,r;l=read(),r=read();reve(root,1,n,l,r);}write(query(root,1,n));putchar('\n');}return 0;}但是这样过不了，猜猜为什么？
线段树合并
在一个树形结构中每一个节点需要开一个权值线段树且区间范围完全一致）。
复杂度分析
一下分析建立在 树形结构合并 的前提下。
注意到在合并的时候需要递归 \(\log n\) 层当且仅仅当一棵线段树和另一棵线段树都有一个节点，并且合并完会变成一个节点，且把它的祖先节点也合并，也就是说每次花费 \(\log n\) 的代价合并了 \(\log n\) 个节点，由于最多有 \(n \log n\) 个节点，所以总复杂度就是 \(O(n \log n)\)。
CF600E
线段树记录最重的子树。然后合并答案。
现在就只有合并线段树的问题了。
trick
段树合并完后再还原需要额外空间，因此最好一次跑完答案，因此 线段树合并适合离线
实现（CF600E）
#include#define int long longusing namespace std;const int maxn = 1e5+114;const int inf = 1e5;struct Node{int ls,rs,val,cnt;// left son right son the anser the cnt }tree[maxn * 20];vector edge[maxn];int col[maxn];int ans[maxn];int root[maxn];int tot;inline void add(int u,int v){edge[u].push_back(v);edge[v].push_back(u);}void pushup(int &cur){//cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';if(tree[tree[cur].ls].cnt<tree[tree[cur].rs].cnt){tree[cur].cnt=tree[tree[cur].rs].cnt;tree[cur].val=tree[tree[cur].rs].val;}else if(tree[tree[cur].rs].cntr||rt>n;for(int i=1;i>col[i];for(int i=2;i>u>>v;add(u,v);}dfs(1,0);for(int i=1;i<=n;i++){cout<<ans[i]<<' ';}}P4556
首先可以考虑树上差分。
然后显然我们只要处理桶合并的问题。
那么显然就可以线段树合并。
#includeusing namespace std;const int inf = 2e5;int n,q;const int maxn = 2e5+114;vector Add[maxn*2],Del[maxn*2];int ans[maxn];int tot;int root[maxn];int fa[maxn][18];int depth[maxn];int lg[maxn];vector edge[maxn];struct Node{int ls,rs,val,cnt;// left son right son the anser the cnt }tree[maxn * 20];void pushup(int &cur){//cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';if(tree[tree[cur].ls].cnt<tree[tree[cur].rs].cnt){tree[cur].cnt=tree[tree[cur].rs].cnt;tree[cur].val=tree[tree[cur].rs].val;}else if(tree[tree[cur].rs].cntr||rt<l) return ;if(cur==0){cur=++tot;}if(lt==rt){tree[cur].cnt+=v;tree[cur].val=lt;return ;}int mid = (lt+rt)/2;addtag(tree[cur].ls,lt,mid,l,r,v);addtag(tree[cur].rs,mid+1,rt,l,r,v);pushup(cur);}int merge(int a,int b,int l,int r){if(a==0||b==0) return a+b;if(l==r){tree[a].cnt+=tree[b].cnt;tree[a].val=l;return a;}int mid=(l+r)/2;tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);pushup(a);return a;}inline void add(int u,int v){edge[u].push_back(v);edge[v].push_back(u);}inline void dfs1(int now,int fath){fa[now][0]=fath;depth[now]=depth[fath] + 1;for(int i=1;i<=lg[depth[now]];++i)fa[now][i] = fa[fa[now][i-1]][i-1];for(int nxt:edge[now]){if(nxt==fath) continue;dfs1(nxt,now);}}int LCA(int x,int y){if(depth[x] depth[y])x=fa[x][lg[depth[x]-depth[y]]- 1];if(x==y) return x;for(int k=lg[depth[x]]-1; k>=0; --k)if(fa[x][k] != fa[y][k])x=fa[x][k],y=fa[y][k];return fa[x][0];}void change(int u,int v,int z){//cout<<u<<' '<<v<<' '<<z<<' '<<LCA(u,v)<>n>>q;for(int i = 1; i <= n; ++i)lg[i]=lg[i-1]+(1<<lg[i-1]==i);for(int i=1;i>u>>v;add(u,v);}dfs1(1,0);for(int i=1;i>u>>v>>z;change(u,v,z);}dfs2(1,0);for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';}P3521
考虑怎么求逆序对。
我们可以在合并的时候用 \(A_{1,mid} \times B_{mid+1,r}\) 来求出逆序对。
那么接下来就是一个板子了。
#include#define int long longusing namespace std;const int maxn = 2e5+114;const int inf = 1e5;struct Node{ int ls,rs,val;// left son right son the anser the cnt }tree[maxn * 20];int u,v,ans;int tot;int n;void pushup(int &cur){ //cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<>1;if(val>U;if(U==0){int lt=dfs(),rt=dfs();u=0,v=0;root=merge(lt,rt,1,n);ans+=min(u,v);//cout<<u<<' '<<v<>n; dfs(); cout<<ans;}P3605
只要维护子树最大值就可以了，用线段树合并即可。
#includeusing namespace std;const int maxn = 1e6+114;vector edge[maxn];int val[maxn];int ans[maxn];int root[maxn];const int inf = 1e9+10;int n,tot;struct Node{int ls,rs,sum;// left son right son the anser the cnt }tree[maxn * 20];void pushup(int &cur){ tree[cur].sum=tree[tree[cur].ls].sum+tree[tree[cur].rs].sum;}int ask(int &cur,int lt,int rt,int l,int r){ if(rt<l||r<lt){ return 0; } if(l<=lt&&rtr||rt>n; for(int i=1;i>val[i]; for(int i=2;i>x; edge[x].push_back(i); } dfs(1,0); for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';}CF208E
本质上只需要维护 \(k\) 级祖先以及子树内深度为 \(x\) 的节点数量。
前者离线 dfs，后者线段树合并（下标表示深度）即可。
#includeusing namespace std;const int N = 1e5+114;int num,a[N];int dep[N];vector edge[N];int root[N];int ans[N];vector< pair > ask[N];//编号 ：深度 vector wyb;int in[N];struct Node{int ls,rs;int val;}tree[N * 20];int tot;int n,q;void pushup(int x){tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;}void update(int &x,int l,int r,int pos,int v){if(l>pos||rpos||r<pos){return 0; }if(l==r&&l==pos){return tree[x].val;}int mid=(l+r)/2,sum=0;sum+=query(tree[x].ls,l,mid,pos);sum+=query(tree[x].rs,mid+1,r,pos);return sum;}int merge(int a,int b,int l,int r){//cout<<a<<' '<<b<<' '<<l<<' '<<r<<'\n'; if(a==0||b==0){//cout<<a<<' '<<b<<'\n';return a+b; }if(l==r){tree[a].val+=tree[b].val;//cout<<tree[a].chifan.size()<<'\n'; tree[b].val=0;return a;}int mid=(l+r)/2;//cout<<tree[a].rs<<' '<<tree[b].rs<<'\n';tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);pushup(a);return a; }vector< pair > ASK[N];//编号 ：深度 void dfs(int cur,int fa){wyb.push_back(cur);dep[cur]=dep[fa]+1;for(int u:edge[cur]){if(u==fa) continue;dfs(u,cur);//cout<<cur<<' '<<root[cur]<<'\n'; root[cur]=merge(root[cur],root[u],1,n);}update(root[cur],1,n,dep[cur],1);for(int i=0;i=wyb.size()) continue;int kfa=wyb[wyb.size()-k-1];//cout<<cur<<' '<<k<<' '<<kfa<<' '<<dep[kfa]+k<<' '<<query(root[kfa],1,n,dep[kfa]+k)<<'\n';ASK[kfa].push_back(make_pair(ask[cur][i].first,dep[kfa]+k));/*if(dep[cur]+ask[cur][i].second<=n){//cout<<ask[cur][i].first<<' '<<query(root[cur],1,n,dep[cur]+ask[cur][i].second)<<'\n';ans[ask[cur][i].first]=query(root[cur],1,n,dep[cur]+ask[cur][i].second);}*/}for(int i=0;i<ASK[cur].size();i++){//cout<<cur<<' '<<ASK[cur][i].second<<' '<<query(root[cur],1,n,ASK[cur][i].second)<>n;for(int i=1;i>x;if(x==0) continue;in[i]++;add(x,i);}cin>>q;for(int i=1;i>x>>y; ask[x].push_back(make_pair(i,y)); } for(int i=1;i<=n;i++){if(in[i]==0){//cout<<i<<'\n';dfs(i,0); }}for(int i=1;i<=q;i++){cout<<ans[i]<<' ';}}P3224
注意到所有连通块其实是在按树形结构合并。
所以对于每个连通块开一棵线段树。
合并操作就去合并两颗线段树。
查询操作就查询第 \(k\) 大即可。
#include#define int long longusing namespace std;const int maxn = 1e5+114;const int inf = 1e5;struct Node{ int ls,rs,val,cnt;// left son right son the anser the cnt }tree[maxn * 20];vector edge[maxn];int fa[maxn];int found(int x){if(fa[x]==x) return x;else return fa[x]=found(fa[x]);}int n,q;int root[maxn];int mp[maxn];int tot;void pushup(int &cur){ //cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<=k){ return kth(tree[cur].ls,l,mid,k);}else{return kth(tree[cur].rs,mid+1,r,k-tree[tree[cur].ls].val);}}void addtag(int &cur,int lt,int rt,int l,int r,int v){ if(lt>r||rt>n>>m; for(int i=1;i>u; mp[u]=i; addtag(root[i],1,n,u,u,1);}for(int i=1;i>x>>y;x=found(x),y=found(y);root[x]=merge(root[x],root[y],1,n);fa[y]=x;}cin>>q;for(int i=1;i>op;if(op=='B'){int x,y;cin>>x>>y;x=found(x),y=found(y);root[x]=merge(root[x],root[y],1,n);fa[y]=x;}else{int x,k;cin>>x>>k;x=found(x);if(k>tree[root[x]].val){cout<<"-1\n";}else{cout<<mp[kth(root[x],1,n,k)]<<'\n';}}}}P5384
本质上和 CF208E 没有区别。
#includeusing namespace std;const int N = 1e6+114;int num,a[N];int dep[N];vector edge[N];int root[N];int ans[N];vector< pair > ask[N];//编号 ：深度 vector wyb;int in[N];struct Node{int ls,rs;int val;}tree[N * 4];int tot;int n,q;stack ioi;void pushup(int x){tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;}void update(int &x,int l,int r,int pos,int v){if(l>pos||rpos||r<pos){return 0; }if(l==r&&l==pos){return tree[x].val;}int mid=(l+r)/2,sum=0;sum+=query(tree[x].ls,l,mid,pos);sum+=query(tree[x].rs,mid+1,r,pos);return sum;}int merge(int a,int b,int l,int r){//cout<<a<<' '<<b<<' '<<l<<' '<<r<<'\n'; if(a==0||b==0){//cout<<a<<' '<<b<<'\n';return a+b; }if(l==r){tree[a].val+=tree[b].val;//cout<<tree[a].chifan.size()<<'\n'; tree[b].val=0; //ioi.push(b);return a;}int mid=(l+r)/2;//cout<<tree[a].rs<<' '<<tree[b].rs<<'\n';tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);pushup(a); ioi.push(b);return a; }vector< pair > ASK[N];//编号 ：深度 void dfs(int cur,int fa){wyb.push_back(cur);dep[cur]=dep[fa]+1;for(int u:edge[cur]){if(u==fa) continue;dfs(u,cur);//cout<<cur<<' '<<root[cur]<<'\n'; root[cur]=merge(root[cur],root[u],1,n);}update(root[cur],1,n,dep[cur],1);for(int i=0;i=wyb.size()) continue;int kfa=wyb[wyb.size()-k-1];//cout<<cur<<' '<<k<<' '<<kfa<<' '<<dep[kfa]+k<<' '<<query(root[kfa],1,n,dep[kfa]+k)<<'\n';ASK[kfa].push_back(make_pair(ask[cur][i].first,dep[kfa]+k));/*if(dep[cur]+ask[cur][i].second<=n){//cout<<ask[cur][i].first<<' '<<query(root[cur],1,n,dep[cur]+ask[cur][i].second)<<'\n';ans[ask[cur][i].first]=query(root[cur],1,n,dep[cur]+ask[cur][i].second);}*/}for(int i=0;i<ASK[cur].size();i++){//cout<<cur<<' '<<ASK[cur][i].second<<' '<<query(root[cur],1,n,ASK[cur][i].second)<>n>>q;for(int i=2;i>x;if(x==0) continue;in[i]++;add(x,i);}for(int i=1;i>x>>y; ask[x].push_back(make_pair(i,y)); } for(int i=1;i<=n;i++){if(in[i]==0){//cout<<i<<'\n';dfs(i,0); }}for(int i=1;i<=q;i++){cout<<ans[i]<<' ';}}