经过寒假数据结构专项训练本蒟蒻也是做出了acm生涯第一道金牌题特此写一篇题解纪念一下也是本蒟蒻第一篇题解如果有问题恳请各位批评指正。前置芝士树链剖分线段树题意分析阅读题面后可以将题意抽象为一棵树节点为矩形给出矩形左下角(x1,y1)和右上角(x2,y2)的坐标父节点和子节点的关系为父节点对应的矩形完全包含子节点对应的矩形。操作 ^ 为根节点到k节点这条链上所有节点的权值加一或减一此处在下文具体分析操作 ? 为询问这颗树上深度为k且权值大于0的节点个数。实现方法题目可以分成两部分实现第一部分将矩阵关系转化为树第二部分是树上操作。建树根据题意我们知道矩阵只有完全包含和不相交两种情况可以用线段树维护。二维矩阵可以联想到扫描线可以将x坐标和y坐标离散化排序x坐标从小到大扫描再遍历边界线是x的所有矩阵。如果x是矩阵左边界相当于进入就在y1-y2区间存储矩形编号在递归路径中矩阵的父节点一直更新为本线段树节点存储的最新编号如果x是矩形右边界相当于退出就将y1-y2区间最新存储的编号出队此编号就是此矩阵对应的编号因为矩阵不重合。这里解释一下为什么在线段树递归路径中将此次操作的矩阵的编号的父节点要一直更新为线段树节点中存储的最新编号如下图根据遍历顺序1号矩阵先被存储再存储2号矩阵此时在线段树中2号矩阵被存储的位置一定在1号矩阵存储位置的子树里。当到右边界时将y1-y2区间最新存储的编号出队比如下图3和5号矩阵不然会出现5的父节点为3的情况。另外由于我在后续的树上操作中用了树链剖分所以我加入了一个边界矩形当作根节点。struct juxing{ int l,r; vectorint a; }ju[N*8]; void buildju(int p,int l,int r){ ju[p]{l,r,{}}; if(lr)return; int m(lr)1ll; buildju(lc,l,m); buildju(rc,m1,r); } void updateju(int p,int l,int r,int id){ if(!ju[p].a.empty()){ dep[id]dep[ju[p].a.back()]1; fa[id][0]ju[p].a.back(); } if(lju[p].lju[p].rr){ ju[p].a.emplace_back(id); return; } if(ju[p].lju[p].r)return; int mid(ju[p].lju[p].r)1; if(lmid)updateju(lc,l,r,id); if(rmid)updateju(rc,l,r,id); } void updatedel(int p,int l,int r){ if(lju[p].lju[p].rr){ ju[p].a.pop_back(); return; } if(ju[p].lju[p].r)return; int mid(ju[p].lju[p].r)1; if(lmid)updatedel(lc,l,r); if(rmid)updatedel(rc,l,r); }cinnm; a[1].x10;a[1].y10;a[1].x21e91;a[1].y21e91; n; for(int i2;in;i){ cina[i].x1a[i].y1a[i].x2a[i].y2; } for(int i1;in;i){ x[i]a[i].x1,x[ni]a[i].x2; } sort(x1,x(n1)1); int numunique(x1,x(n1)1)-x-1; for(int i1;in;i){ a[i].x1lower_bound(x1,xnum1,a[i].x1)-x; a[i].x2lower_bound(x1,xnum1,a[i].x2)-x; } for(int i1;in;i){ y[i]a[i].y1,y[ni]a[i].y2; } sort(y1,y(n1)1); numunique(y1,y(n1)1)-y-1; for(int i1;in;i){ a[i].y1lower_bound(y1,ynum1,a[i].y1)-y; a[i].y2lower_bound(y1,ynum1,a[i].y2)-y; } for(int i1;i(n);i){ x[i]a[i].x1,x[ni]a[i].x2; } for(int i1;i(n1);i){ p[i]i; } sort(p1,p(n1)1,cmp); buildju(1,1,num); for(int o1;o(n1);o){ int ip[o]; if(in){ updateju(1,a[i].y1,a[i].y2,i); g[fa[i][0]].emplace_back(i); for(int j1;j18;j) fa[i][j]fa[fa[i][j-1]][j-1]; } else updatedel(1,a[i-n].y1,a[i-n].y2); }树上操作^ 操作有点像染色k节点染过了根节点到k节点整条链权值都减1k节点没染过条链权值都加1。这里对于链的操作用树链剖分线段树更新但是这里要注意最后查询的是某深度权值大于0的节点数但是如果根节点到k节点整条链权值都改变不代表根节点的深度到k节点的深度的节点数都要改变。权值要加1时只有节点权值等于0的节点的深度的节点数要加1权值要减1时只有节点权值等于1的节点的深度的节点数要加1。所以我们要用两颗线段树维护一颗线段树维护节点的权值和区间最大值和最小值一颗线段树维护某深度权值大于0的节点数。那我们怎么快速知道我们要更新的深度区间呢因为每次权值更新是从k结点到根节点的更新那么从子节点到根节点的权值一定是递增的所以我们可以一直查找k结点的父结点的父节点......找到所有权值符合条件的。但是显然太慢了所以我们用倍增来查找。如果操作权值减1查找链上a结点的最小值如果最小值是1那么结点a的深度到结点k的深度区间就要减1。如果操作权值加1查找链上a结点的最大值如果最大值是0那么结点a的深度到结点k的深度区间就要加1。其他的都是树链剖分和线段树基础操作。int fa[N][20],dep[N],son[N],sz[N]; int top[N]; int id[N]; int cnt; void dfs1(int now,int fat){ fa[now][0]fat,dep[now]dep[fat]1,sz[now]1; for(int i1;(1i)dep[now];i){ fa[now][i]fa[fa[now][i-1]][i-1]; } for(auto ne:g[now]){ if(nefat)continue; dfs1(ne,now); sz[now]sz[ne]; if(sz[son[now]]sz[ne])son[now]ne; } } void dfs2(int now,int t){ top[now]t; id[now]cnt; if(!son[now])return; dfs2(son[now],t); for(auto ne:g[now]){ if(nefa[now][0]||neson[now])continue; dfs2(ne,ne); } } struct T{ int l,r; int add,sum; }tr[N*4];//存储深度对应结点数 void pushup(int p){ tr[p].sumtr[lc].sumtr[rc].sum; } void pushdown(int p){ if(tr[p].add){ tr[lc].sumtr[p].add*(tr[lc].r-tr[lc].l1); tr[rc].sumtr[p].add*(tr[rc].r-tr[rc].l1); tr[lc].addtr[p].add; tr[rc].addtr[p].add; tr[p].add0; } } void build(int p,int l,int r){ tr[p]{l,r,0,0}; if(lr)return; int m(lr)1ll; build(lc,l,m); build(rc,m1,r); pushup(p); } void update(int p,int l,int r,int k){ if(ltr[p].ltr[p].rr){ tr[p].addk; tr[p].sumk; return ; } pushdown(p); int mid(tr[p].ltr[p].r)1ll; if(lmid)update(lc,l,r,k); if(rmid)update(rc,l,r,k); pushup(p); } int query(int p,int l,int r){ if(ltr[p].ltr[p].rr){ return tr[p].sum; } pushdown(p); int mid(tr[p].ltr[p].r)1ll; int res0; if(lmid)resquery(lc,l,r); if(rmid)resquery(rc,l,r); return res; } struct T1{ int l,r; int maxl;int add; int minl; }tr1[N*4];//存储节点权值 最大值和最小值 void pushup1(int p){ tr1[p].maxlmax(tr1[lc].maxl,tr1[rc].maxl); tr1[p].minlmin(tr1[lc].minl,tr1[rc].minl); } void pushdown1(int p){ if(tr1[p].add){ tr1[rc].maxltr1[p].add; tr1[lc].maxltr1[p].add; tr1[lc].minltr1[p].add; tr1[rc].minltr1[p].add; tr1[lc].addtr1[p].add; tr1[rc].addtr1[p].add; tr1[p].add0; } } void build1(int p,int l,int r){ tr1[p]{l,r,0,0,0}; if(lr)return; int m(lr)1ll; build1(lc,l,m); build1(rc,m1,r); pushup1(p); } void update1(int p,int l,int r,int k){ if(ltr1[p].ltr1[p].rr){ tr1[p].minlk, tr1[p].maxlk,tr1[p].addk; return ; } if(tr1[p].ltr1[p].r)return;; pushdown1(p); int mid(tr[p].ltr[p].r)1ll; if(lmid)update1(lc,l,r,k); if(rmid)update1(rc,l,r,k); pushup1(p); } void update_path(int u,int v,int k){ while(top[u]!top[v]){ if(dep[top[u]]dep[top[v]])swap(u,v); update1(1,id[top[u]],id[u],k); ufa[top[u]][0]; } if(dep[u]dep[v])swap(u,v); update1(1,id[v],id[u],k); } int querymi(int p,int l,int r){ if(ltr1[p].ltr1[p].rr){ return tr1[p].minl; } pushdown1(p); int mid(tr1[p].ltr1[p].r)1ll; int res0; if(lmid)resquerymi(lc,l,r); if(rmid)resquerymi(rc,l,r); return res; } int query1(int p,int l,int r){ if(ltr1[p].ltr1[p].rr){ return tr1[p].maxl; } pushdown1(p); int mid(tr1[p].ltr1[p].r)1ll; int res0; if(lmid)resquery1(lc,l,r); if(rmid)resquery1(rc,l,r); return res; }dfs1(root,-1); dfs2(root,root); build(1,1,n); build1(1,1,n); while(m--){ char t;int k; cintk; if(t^){ if(hx[k1]){ int ttk1; for(int i18;i0;i--){ if(fa[tt][i]0querymi(1,id[fa[tt][i]],id[fa[tt][i]])1){ ttfa[tt][i]; } } if(querymi(1,id[tt],id[tt])1) update(1,dep[tt],dep[k1],-1); update_path(1,k1,-1); hx[k1]0; } else { int ttk1; for(int i18;i0;i--){ if(fa[tt][i]0query1(1,id[fa[tt][i]],id[fa[tt][i]])0){ ttfa[tt][i]; } } if(query1(1,id[tt],id[tt])0) update(1,dep[tt],dep[k1],1); update_path(1,k1,1); hx[k1]1; } } else if(t?){ coutquery(1,k2,k2)endl; } }总结这题是vpicpc上海站的时候感觉可以做的但是当时时间不够了加之比赛的时候没有想很明白没能出的了赛后补题的时候花了六七个小时改了很多实现有很多灵光乍现的地方比如倍增找结点用线段树建节点的关系。主要是没想明白就写导致写了改改了写希望之后做题的时候不要着急上机先把整个思路捋清晰确保可以实现了再写避免脑子糊成依托。还有就是跑的很慢卡时间过的qaq。完整代码#includebits/stdc.h #define int long long #define lc p1 #define rc p1|1 using namespace std; int mod998244353; const int N500025; struct ju{ int x1,y1,x2,y2; }a[N]; int x[N1],y[N1],p[N1]; int n,m; int hx[N]; vectorint g[N]; int fa[N][20],dep[N],son[N],sz[N]; int top[N]; int id[N]; int cnt; void dfs1(int now,int fat){ fa[now][0]fat,dep[now]dep[fat]1,sz[now]1; for(int i1;(1i)dep[now];i){ fa[now][i]fa[fa[now][i-1]][i-1]; } for(auto ne:g[now]){ if(nefat)continue; dfs1(ne,now); sz[now]sz[ne]; if(sz[son[now]]sz[ne])son[now]ne; } } void dfs2(int now,int t){ top[now]t; id[now]cnt; if(!son[now])return; dfs2(son[now],t); for(auto ne:g[now]){ if(nefa[now][0]||neson[now])continue; dfs2(ne,ne); } } struct T{ int l,r; int add,sum; }tr[N*4];//存储深度对应结点数 void pushup(int p){ tr[p].sumtr[lc].sumtr[rc].sum; } void pushdown(int p){ if(tr[p].add){ tr[lc].sumtr[p].add*(tr[lc].r-tr[lc].l1); tr[rc].sumtr[p].add*(tr[rc].r-tr[rc].l1); tr[lc].addtr[p].add; tr[rc].addtr[p].add; tr[p].add0; } } void build(int p,int l,int r){ tr[p]{l,r,0,0}; if(lr)return; int m(lr)1ll; build(lc,l,m); build(rc,m1,r); pushup(p); } void update(int p,int l,int r,int k){ if(ltr[p].ltr[p].rr){ tr[p].addk; tr[p].sumk; return ; } pushdown(p); int mid(tr[p].ltr[p].r)1ll; if(lmid)update(lc,l,r,k); if(rmid)update(rc,l,r,k); pushup(p); } int query(int p,int l,int r){ if(ltr[p].ltr[p].rr){ return tr[p].sum; } pushdown(p); int mid(tr[p].ltr[p].r)1ll; int res0; if(lmid)resquery(lc,l,r); if(rmid)resquery(rc,l,r); return res; } struct T1{ int l,r; int maxl;int add; int minl; }tr1[N*4];//存储节点权值 最大值和最小值 void pushup1(int p){ tr1[p].maxlmax(tr1[lc].maxl,tr1[rc].maxl); tr1[p].minlmin(tr1[lc].minl,tr1[rc].minl); } void pushdown1(int p){ if(tr1[p].add){ tr1[rc].maxltr1[p].add; tr1[lc].maxltr1[p].add; tr1[lc].minltr1[p].add; tr1[rc].minltr1[p].add; tr1[lc].addtr1[p].add; tr1[rc].addtr1[p].add; tr1[p].add0; } } void build1(int p,int l,int r){ tr1[p]{l,r,0,0,0}; if(lr)return; int m(lr)1ll; build1(lc,l,m); build1(rc,m1,r); pushup1(p); } void update1(int p,int l,int r,int k){ if(ltr1[p].ltr1[p].rr){ tr1[p].minlk, tr1[p].maxlk,tr1[p].addk; return ; } if(tr1[p].ltr1[p].r)return;; pushdown1(p); int mid(tr[p].ltr[p].r)1ll; if(lmid)update1(lc,l,r,k); if(rmid)update1(rc,l,r,k); pushup1(p); } void update_path(int u,int v,int k){ while(top[u]!top[v]){ if(dep[top[u]]dep[top[v]])swap(u,v); update1(1,id[top[u]],id[u],k); ufa[top[u]][0]; } if(dep[u]dep[v])swap(u,v); update1(1,id[v],id[u],k); } int querymi(int p,int l,int r){ if(ltr1[p].ltr1[p].rr){ return tr1[p].minl; } pushdown1(p); int mid(tr1[p].ltr1[p].r)1ll; int res0; if(lmid)resquerymi(lc,l,r); if(rmid)resquerymi(rc,l,r); return res; } int query1(int p,int l,int r){ if(ltr1[p].ltr1[p].rr){ return tr1[p].maxl; } pushdown1(p); int mid(tr1[p].ltr1[p].r)1ll; int res0; if(lmid)resquery1(lc,l,r); if(rmid)resquery1(rc,l,r); return res; } //矩形的线段树 bool cmp(int x1,int x2){ return x[x1]x[x2]; } struct juxing{ int l,r; vectorint a; }ju[N*8]; void buildju(int p,int l,int r){ ju[p]{l,r,{}}; if(lr)return; int m(lr)1ll; buildju(lc,l,m); buildju(rc,m1,r); } void updateju(int p,int l,int r,int id){ if(!ju[p].a.empty()dep[ju[p].a.back()]dep[id]){ dep[id]dep[ju[p].a.back()]1; fa[id][0]ju[p].a.back(); } if(lju[p].lju[p].rr){ ju[p].a.emplace_back(id); return; } if(ju[p].lju[p].r)return; int mid(ju[p].lju[p].r)1; if(lmid)updateju(lc,l,r,id); if(rmid)updateju(rc,l,r,id); } void updatedel(int p,int l,int r){ if(lju[p].lju[p].rr){ ju[p].a.pop_back(); return; } if(ju[p].lju[p].r)return; int mid(ju[p].lju[p].r)1; if(lmid)updatedel(lc,l,r); if(rmid)updatedel(rc,l,r); } void solve(){ int root1; cinnm; a[1].x10;a[1].y10;a[1].x21e91;a[1].y21e91; n; for(int i2;in;i){ cina[i].x1a[i].y1a[i].x2a[i].y2; } for(int i1;in;i){ x[i]a[i].x1,x[ni]a[i].x2; } sort(x1,x(n1)1); int numunique(x1,x(n1)1)-x-1; for(int i1;in;i){ a[i].x1lower_bound(x1,xnum1,a[i].x1)-x; a[i].x2lower_bound(x1,xnum1,a[i].x2)-x; } for(int i1;in;i){ y[i]a[i].y1,y[ni]a[i].y2; } sort(y1,y(n1)1); numunique(y1,y(n1)1)-y-1; for(int i1;in;i){ a[i].y1lower_bound(y1,ynum1,a[i].y1)-y; a[i].y2lower_bound(y1,ynum1,a[i].y2)-y; } for(int i1;i(n);i){ x[i]a[i].x1,x[ni]a[i].x2; } for(int i1;i(n1);i){ p[i]i; } sort(p1,p(n1)1,cmp); buildju(1,1,num); for(int o1;o(n1);o){ int ip[o]; if(in){ updateju(1,a[i].y1,a[i].y2,i); g[fa[i][0]].emplace_back(i); for(int j1;j18;j) fa[i][j]fa[fa[i][j-1]][j-1]; } else updatedel(1,a[i-n].y1,a[i-n].y2); } dfs1(root,-1); dfs2(root,root); build(1,1,n); build1(1,1,n); while(m--){ char t;int k; cintk; if(t^){ if(hx[k1]){ int ttk1; for(int i18;i0;i--){ if(fa[tt][i]0querymi(1,id[fa[tt][i]],id[fa[tt][i]])1){ ttfa[tt][i]; } } if(querymi(1,id[tt],id[tt])1) update(1,dep[tt],dep[k1],-1); update_path(1,k1,-1); hx[k1]0; } else { int ttk1; for(int i18;i0;i--){ if(fa[tt][i]0query1(1,id[fa[tt][i]],id[fa[tt][i]])0){ ttfa[tt][i]; } } if(query1(1,id[tt],id[tt])0) update(1,dep[tt],dep[k1],1); update_path(1,k1,1); hx[k1]1; } } else if(t?){ coutquery(1,k2,k2)endl; } } return; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen(in.txt,r,stdin); //freopen(out.txt,w,stdout); int T_case1; //cinT_case; while(T_case--){ solve(); } return 0; }