1.数据结构
数据结构1
\(A\) luogu P5494 【模板】线段树分裂
\(B\) luogu P1637 三元上升子序列
- 题解
\(C\) luogu P6492 [COCI2010-2011#6] STEP
-
将
L视作 \(0\) ,R视作 \(1\) 。 -
则等价于查询最长 \(01\) 串长度,线段树维护前后缀信息即可,写法跟维护最大子段和差不多。
点击查看代码
int a[200010]; struct SMT { struct SegmentTree { int l,r,pre,suf,ans; }tree[800010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { tree[rt].ans=max(tree[lson(rt)].ans,tree[rson(rt)].ans); tree[rt].pre=tree[lson(rt)].pre; tree[rt].suf=tree[rson(rt)].suf; if(a[tree[lson(rt)].r]!=a[tree[rson(rt)].l]) { tree[rt].ans=max(tree[rt].ans,tree[lson(rt)].suf+tree[rson(rt)].pre); tree[rt].pre+=(tree[lson(rt)].pre==tree[lson(rt)].r-tree[lson(rt)].l+1)*tree[rson(rt)].pre; tree[rt].suf+=(tree[rson(rt)].suf==tree[rson(rt)].r-tree[rson(rt)].l+1)*tree[lson(rt)].suf; } } void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].pre=tree[rt].suf=tree[rt].ans=1; return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(int rt,int pos) { if(tree[rt].l==tree[rt].r) { a[tree[rt].l]^=1; return; } int mid=(tree[rt].l+tree[rt].r)/2; if(pos<=mid) { update(lson(rt),pos); } else { update(rson(rt),pos); } pushup(rt); } SegmentTree query(int rt,int x,int y) { if(x<=tree[rt].l&&tree[rt].r<=y) { return tree[rt]; } int mid=(tree[rt].l+tree[rt].r)/2; SegmentTree p,q,ans; if(y<=mid) { return query(lson(rt),x,y); } else { if(x>mid) { return query(rson(rt),x,y); } else { p=query(lson(rt),x,y); q=query(rson(rt),x,y); ans.ans=max(p.ans,q.ans); ans.pre=p.pre; ans.suf=q.suf; if(a[p.r]!=a[q.l]) { ans.ans=max(ans.ans,p.suf+q.pre); ans.pre+=(p.pre==p.r-p.l+1)*q.pre; ans.suf+=(q.suf==q.r-q.l+1)*p.suf; } return ans; } } } }T; int main() { int n,m,x,i; cin>>n>>m; T.build(1,1,n); for(i=1;i<=m;i++) { cin>>x; T.update(1,x); cout<<T.query(1,1,n).ans<<endl; } return 0; }
\(D\) luogu P6136 【模板】普通平衡树(数据加强版)
- 题解
\(E\) luogu P3038 [USACO11DEC] Grass Planting G
- 多倍经验: SP12005 GRASSPLA - Grass Planting
- 题解
\(F\) luogu P7735 [NOI2021] 轻重边
-
维护路径信息,考虑树剖。
-
边权直接维护不太好维护,考虑转成点权。而直接将边权信息赋给深度较深的儿子节点在本题中难以适应。
-
考虑给每一个点赋一个权值 \(val\) 使得对于任意一条边 \(u \to v\) 若 \(val_{u}=val_{v}\) 则 \(u \to v\) 是重边,否则是轻边。
-
此时操作 \(1\) 等价于将 \(u \to v\) 上的点的权值都赋成一个统一的值;操作 \(2\) 等价于查询 \(u \to v\) 上相邻两点权值相同的无序点对,做法同 luogu P2486 [SDOI2011] 染色 差不多,线段树维护即可。
点击查看代码
struct node { int nxt,to; }e[200010]; int head[200010],c[200010],cc[200010],fa[200010],dep[200010],siz[200010],son[200010],dfn[200010],top[200010],cnt=0,tot=0; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } struct SMT { struct SegmentTree { int l,r,lazy,lc,rc,ans; }tree[800010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { tree[rt].ans=tree[lson(rt)].ans+tree[rson(rt)].ans+(tree[lson(rt)].rc==tree[rson(rt)].lc); tree[rt].lc=tree[lson(rt)].lc; tree[rt].rc=tree[rson(rt)].rc; } void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; tree[rt].lazy=0; if(l==r) { tree[rt].lc=tree[rt].rc=cc[l]; tree[rt].ans=0; return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void pushdown(int rt) { if(tree[rt].lazy!=0) { tree[lson(rt)].lc=tree[lson(rt)].rc=tree[rt].lazy; tree[rson(rt)].lc=tree[rson(rt)].rc=tree[rt].lazy; tree[lson(rt)].ans=tree[lson(rt)].r-tree[lson(rt)].l+1-1; tree[rson(rt)].ans=tree[rson(rt)].r-tree[rson(rt)].l+1-1; tree[lson(rt)].lazy=tree[rson(rt)].lazy=tree[rt].lazy; tree[rt].lazy=0; } } void update(int rt,int x,int y,int val) { if(x<=tree[rt].l&&tree[rt].r<=y) { tree[rt].lc=tree[rt].rc=tree[rt].lazy=val; tree[rt].ans=tree[rt].r-tree[rt].l+1-1; return; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)/2; if(x<=mid) { update(lson(rt),x,y,val); } if(y>mid) { update(rson(rt),x,y,val); } pushup(rt); } SegmentTree query(int rt,int x,int y) { if(x<=tree[rt].l&&tree[rt].r<=y) { return tree[rt]; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)/2; SegmentTree p,q,ans; if(y<=mid) { return query(lson(rt),x,y); } else { if(x>mid) { return query(rson(rt),x,y); } else { p=query(lson(rt),x,y); q=query(rson(rt),x,y); ans.ans=p.ans+q.ans+(p.rc==q.lc); ans.lc=p.lc; ans.rc=q.rc; return ans; } } } }T; void dfs1(int x,int father) { siz[x]=1; fa[x]=father; dep[x]=dep[father]+1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { dfs1(e[i].to,x); siz[x]+=siz[e[i].to]; son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x]; } } } void dfs2(int x,int id) { top[x]=id; tot++; dfn[x]=tot; cc[tot]=c[x]; if(son[x]!=0) { dfs2(son[x],id); for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa[x]&&e[i].to!=son[x]) { dfs2(e[i].to,e[i].to); } } } } void update1(int u,int v,int val) { while(top[u]!=top[v]) { if(dep[top[u]]>dep[top[v]]) { T.update(1,dfn[top[u]],dfn[u],val); u=fa[top[u]]; } else { T.update(1,dfn[top[v]],dfn[v],val); v=fa[top[v]]; } } if(dep[u]<dep[v]) { T.update(1,dfn[u],dfn[v],val); } else { T.update(1,dfn[v],dfn[u],val); } } int query1(int u,int v) { int ans=0; while(top[u]!=top[v]) { if(dep[top[u]]>dep[top[v]]) { ans+=T.query(1,dfn[top[u]],dfn[u]).ans+(T.query(1,dfn[top[u]],dfn[top[u]]).lc==T.query(1,dfn[fa[top[u]]],dfn[fa[top[u]]]).lc); u=fa[top[u]]; } else { ans+=T.query(1,dfn[top[v]],dfn[v]).ans+(T.query(1,dfn[top[v]],dfn[top[v]]).lc==T.query(1,dfn[fa[top[v]]],dfn[fa[top[v]]]).lc); v=fa[top[v]]; } } if(dep[u]<dep[v]) { ans+=T.query(1,dfn[u],dfn[v]).ans; } else { ans+=T.query(1,dfn[v],dfn[u]).ans; } return ans; } int main() { int t,n,m,pd,u,v,i,j; scanf("%d",&t); for(j=1;j<=t;j++) { cnt=tot=0; memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); memset(son,0,sizeof(son)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { c[i]=i; } for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,0); dfs2(1,1); T.build(1,1,n); for(i=1;i<=m;i++) { scanf("%d%d%d",&pd,&u,&v); if(pd==1) { update1(u,v,n+i); } else { printf("%d\n",query1(u,v)); } } } return 0; }
\(G\) luogu P3605 [USACO17JAN] Promotion Counting P
- 题解
\(H\) luogu P7394 「TOCO Round 1」History
\(I\) luogu P7671 [GDOI2016] 疯狂动物城
\(J\) CF915E Physical Education Lessons
- 题解
\(K\) CF19D Points
-
离散化后线段树套
set即可。 -
叶子节点只保留 \(y\) 坐标的最大值然后进行线段树上二分。
点击查看代码
int x[200010],y[200010],xx[200010],yy[200010]; char pd[200010][8]; set<int>s[200010]; struct SMT { struct SegmentTree { int l,r,maxx; }tree[800010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { tree[rt].maxx=max(tree[lson(rt)].maxx,tree[rson(rt)].maxx); } void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; if(l==r) { s[l].insert(-0x7f7f7f7f); tree[rt].maxx=-0x7f7f7f7f; return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(int rt,int pos,int val) { if(tree[rt].l==tree[rt].r) { tree[rt].maxx=val; return; } int mid=(tree[rt].l+tree[rt].r)/2; if(pos<=mid) { update(lson(rt),pos,val); } else { update(rson(rt),pos,val); } pushup(rt); } int query(int rt,int x,int y,int val) { if(tree[rt].maxx<val) { return -1; } if(tree[rt].l==tree[rt].r) { return tree[rt].l; } int mid=(tree[rt].l+tree[rt].r)/2,p,q; if(y<=mid) { return query(lson(rt),x,y,val); } else { if(x>mid) { return query(rson(rt),x,y,val); } else { p=query(lson(rt),x,y,val); if(p!=-1) { return p; } q=query(rson(rt),x,y,val); if(q!=-1) { return q; } return -1; } } } }T; int main() { int n,ans,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s%d%d",(pd[i]+1),&x[i],&y[i]); xx[i]=x[i]; yy[i]=y[i]; } sort(xx+1,xx+1+n); sort(yy+1,yy+1+n); xx[0]=unique(xx+1,xx+1+n)-(xx+1); yy[0]=unique(yy+1,yy+1+n)-(yy+1); T.build(1,1,xx[0]); for(i=1;i<=n;i++) { x[i]=lower_bound(xx+1,xx+1+xx[0],x[i])-xx; y[i]=lower_bound(yy+1,yy+1+yy[0],y[i])-yy; if(pd[i][1]=='a') { ans=*--s[x[i]].end(); s[x[i]].insert(y[i]); if(ans!=*--s[x[i]].end()) { T.update(1,x[i],*--s[x[i]].end()); } } if(pd[i][1]=='r') { ans=*--s[x[i]].end(); s[x[i]].erase(s[x[i]].find(y[i])); if(ans!=*--s[x[i]].end()) { T.update(1,x[i],*--s[x[i]].end()); } } if(pd[i][1]=='f') { if(x[i]+1<=xx[0]) { ans=T.query(1,x[i]+1,xx[0],y[i]+1); if(ans==-1) { printf("-1\n"); } else { printf("%d %d\n",xx[ans],yy[*s[ans].upper_bound(y[i])]); } } else { printf("-1\n"); } } } return 0; }
\(L\) CF193D Two Segments
\(M\) CF1983F array-value
\(N\) [ABC371F] Takahashi in Narrow Road
- 题解
\(O\) CF1304F2 Animal Observation (hard version)
\(P\) CF946G Almost Increasing Array
\(Q\) CF718C Sasha and Array
-
容易有 \(\begin{bmatrix} Fib_{n} & Fib_{n+1} \end{bmatrix}=\begin{bmatrix} Fib_{n-1} & Fib_{n} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) 。
-
建树时暴力算斐波那契数,修改时维护 \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) 的指数增加量标记,区间和维护矩阵加法即可。
- 本质上应用了矩阵的结合律 \(A \times B+A \times C=A \times (B+C)\) 。
-
为方便重载运算符,将原 \(F\) 矩阵写作 \(\begin{bmatrix} Fib_{n} & Fib_{n+1} \\ 0 & 0 \end{bmatrix}\) 。
点击查看代码
const ll p=1000000007; struct Matrix { ll ma[3][3]; Matrix() { memset(ma,0,sizeof(ma)); } Matrix operator + (const Matrix &another) const { Matrix ans; for(ll i=1;i<=2;i++) { for(ll j=1;j<=2;j++) { ans.ma[i][j]=(ma[i][j]+another.ma[i][j])%p; } } return ans; } Matrix operator * (const Matrix &another) const { Matrix ans; for(ll i=1;i<=2;i++) { for(ll j=1;j<=2;j++) { for(ll h=1;h<=2;h++) { ans.ma[i][j]=(ans.ma[i][j]+ma[i][h]*another.ma[h][j]%p)%p; } } } return ans; } bool operator == (const Matrix &another) const { for(ll i=1;i<=2;i++) { for(ll j=1;j<=2;j++) { if(ma[i][j]!=another.ma[i][j]) { return false; } } } return true; } }base,I; ll a[100010]; Matrix qpow(Matrix a,ll b,ll p) { Matrix ans; for(ll i=1;i<=2;i++) { ans.ma[i][i]=1; } while(b) { if(b&1) { ans=ans*a; } b>>=1; a=a*a; } return ans; } struct SMT { struct SegmentTree { ll l,r; Matrix sum,lazy; }tree[400010]; ll lson(ll x) { return x*2; } ll rson(ll x) { return x*2+1; } void pushup(ll rt) { tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum; } void build(ll rt,ll l,ll r) { tree[rt].l=l; tree[rt].r=r; tree[rt].lazy=I; if(l==r) { tree[rt].sum.ma[1][1]=tree[rt].sum.ma[2][1]=tree[rt].sum.ma[2][2]=0; tree[rt].sum.ma[1][2]=1; tree[rt].sum=tree[rt].sum*qpow(base,a[l],p); return; } ll mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void pushdown(ll rt) { if(!(tree[rt].lazy==I)) { tree[lson(rt)].sum=tree[lson(rt)].sum*tree[rt].lazy; tree[rson(rt)].sum=tree[rson(rt)].sum*tree[rt].lazy; tree[lson(rt)].lazy=tree[lson(rt)].lazy*tree[rt].lazy; tree[rson(rt)].lazy=tree[rson(rt)].lazy*tree[rt].lazy; tree[rt].lazy=I; } } void update(ll rt,ll x,ll y,Matrix val) { if(x<=tree[rt].l&&tree[rt].r<=y) { tree[rt].sum=tree[rt].sum*val; tree[rt].lazy=tree[rt].lazy*val; return; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2; if(x<=mid) { update(lson(rt),x,y,val); } if(y>mid) { update(rson(rt),x,y,val); } pushup(rt); } ll query(ll rt,ll x,ll y) { if(x<=tree[rt].l&&tree[rt].r<=y) { return tree[rt].sum.ma[1][1]; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)/2,ans=0; if(x<=mid) { ans=(ans+query(lson(rt),x,y))%p; } if(y>mid) { ans=(ans+query(rson(rt),x,y))%p; } return ans; } }T; int main() { ll n,m,pd,l,r,x,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } base.ma[1][1]=0; base.ma[1][2]=base.ma[2][1]=base.ma[2][2]=1; I.ma[1][1]=I.ma[2][2]=1; I.ma[1][2]=I.ma[2][1]=0; T.build(1,1,n); for(i=1;i<=m;i++) { cin>>pd>>l>>r; if(pd==1) { cin>>x; T.update(1,l,r,qpow(base,x,p)); } else { cout<<T.query(1,l,r)<<endl; } } return 0; }
\(R\) CF1956F Nene and the Passing Game
\(S\) [ABC351G] Hash on Tree
\(T\) [ARC073F] Many Moves
\(U\) luogu P4719 【模板】"动态 DP"&动态树分治
\(V\) luogu P6348 [PA2011] Journeys
- 题解
\(W\) luogu P2605 [ZJOI2010] 基站选址
- 题解
\(X\) luogu P3521 [POI2011] ROT-Tree Rotations
- 题解
数据结构2
\(A\) luogu B3656 【模板】双端队列 1
-
用
list代替deque。 -
关于
deque和list的空间问题,详见 关于deque和list 。点击查看代码
list<int>q[1000001]; int main() { int n,i,a,x; string pd; cin>>n; for(i=1;i<=n;i++) { cin>>pd; if(pd=="push_back") { cin>>a>>x; q[a].push_back(x); } if(pd=="pop_back") { cin>>a; if(q[a].empty()==0) { q[a].pop_back(); } } if(pd=="push_front") { cin>>a>>x; q[a].push_front(x); } if(pd=="pop_front") { cin>>a; if(q[a].empty()==0) { q[a].pop_front(); } } if(pd=="size") { cin>>a; cout<<q[a].size()<<endl; } if(pd=="front") { cin>>a; if(q[a].empty()==0) { cout<<q[a].front()<<endl; } } if(pd=="back") { cin>>a; if(q[a].empty()==0) { cout<<q[a].back()<<endl; } } } return 0; }
\(B\) luogu P1892 [BOI2003] 团伙
-
考虑扩展域并查集,把一个点 \(x\) 拆成两个节点 \(x_{friend}\) 和 \(x_{enemy}\) 。
-
若 \(x,y\) 是朋友,则合并 \(x_{friend},y_{friend}\) ;否则合并 \(x_{friend},y_{enemy}\) 和 \(x_{enemy},y_{friend}\) 。
点击查看代码
int vis[2010]; struct DSU { int fa[2010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; } } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void merge(int x,int y) { x=find(x); y=find(y); if(x!=y) { fa[x]=y; } } }D; int main() { int n,m,x,y,ans=0,i; char pd; cin>>n>>m; D.init(2*n); for(i=1;i<=m;i++) { cin>>pd>>x>>y; if(pd=='F') { D.merge(x,y); } else { D.merge(x,y+n); D.merge(x+n,y); } } for(i=1;i<=n;i++) { ans+=(vis[D.find(i)]==0); vis[D.find(i)]=1; } cout<<ans<<endl; return 0; }
\(C\) luogu P2502 [HAOI2006] 旅行
\(D\) luogu P3402 可持久化并查集
- 题解
\(E\) luogu P4768 [NOI2018] 归程
\(F\) luogu P5854 【模板】笛卡尔树
\(G\) luogu P2081 [NOI2012] 迷失游乐园
\(H\) luogu P4381 [IOI2008] Island
- 题解 。
\(I\) CF1713E Cross Swapping
\(J\) HDU6403 Card Game
- 题解
\(K\) luogu P6453 [COCI2008-2009#4] PERIODNI
- 多倍经验: SP3734 PERIODNI - Periodni
\(L\) luogu P3765 总统选举
\(M\) CF1920F2 Smooth Sailing (Hard Version)
\(N\) CF1687C Sanae and Giant Robot
\(O\) [AGC003E] Sequential operations on Sequence
\(P\) luogu P3452 [POI2007] BIU-Offices
版权声明:本作品采用 「署名-非商业性使用-相同方式共享 4.0 国际」许可协议(CC BY-NC-SA 4.0) 进行许可。