这两种做法（不要在意代码里的\(\dfrac{5}{8}\)，本来想卡个边界的但是好像不卡也行）的时间复杂度都有一点玄学（至少我是这么想的），我最快卡到了 500ms+（数据加强后）
当然也有强者卡进了500ms以内，但毕竟是我的做法大众普及了。。。
也不知道为啥机房里有不少人都在 Hack 我。。。。。
好像这两种做法的结合也可以被卡掉，可以搞一个类似于神经元的图（其实就是链+菊花图）。
或者一种长菊花图（就是让多条链的端点连接到一个节点上）（可fengwu说卡不掉，有异议的请线下解决）
但是这种数据有点难造，所以欢迎各位前来 Hack 。
另外，yspm的线段树做法或者其他的点分治好像也可以。。。
code #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+10; int n,m,las,top; int tot,head[N],nxt[N<<1],ver[N<<1]; int tim,dep[N],topp[N],siz[N],dfn[N],son[N],fa[N]; int cnt,st[N],mxdep; bool flag,vis[N]; struct Node { int pos,tim; }sta[N]; void add_edge(int x,int y) { ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } void dfs1(int x) { mxdep=max(mxdep,dep[x]); siz[x]=1; for(int i=head[x];i;i=nxt[i]) { int to=ver[i]; if(siz[to]) continue; fa[to]=x; dep[to]=dep[x]+1; dfs1(to); siz[x]+=siz[to]; if(siz[to]>siz[son[x]]) son[x]=to; } } void dfs2(int x,int tp) { dfn[x]=++tim; topp[x]=tp; if(son[x]) dfs2(son[x],tp); for(int i=head[x];i;i=nxt[i]) if(!dfn[ver[i]]) dfs2(ver[i],ver[i]); } int LCA(int x,int y) { if(!x||!y) return 0; while(topp[x]^topp[y]) { if(dep[topp[x]]<dep[topp[y]]) swap(x,y); x=fa[topp[x]]; } if(dep[x]>dep[y]) swap(x,y); return x; } int dist(int x,int y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; } void Special_Judge() { for(int i=1,opt,x;i<=m;i++) { opt=read(); x=read(); int pre=cnt; for(int k=las+1;k<=pre;k++) for(int j=head[st[k]];j;j=nxt[j]) { if(!vis[ver[j]]) st[++cnt]=ver[j]; vis[ver[j]]=true; } las=pre; if(opt==2) { memset(vis,false,sizeof(vis)); cnt=las=0; } else if(opt==1) { if(!vis[x]) st[++cnt]=x,vis[x]=true; } else { if(vis[x]) printf("wrxcsd\n"); else printf("orzFsYo\n"); } } exit(0); } signed main() { n=read(); m=read(); for(int i=1,x,y;i<n;i++) { x=read(); y=read(); add_edge(x,y); add_edge(y,x); if(x!=y+1&&y!=x+1) flag=true; } dfs1(1); dfs2(1,1); if(!flag||mxdep>=n*5/8) Special_Judge(); for(int i=1,opt,x;i<=m;i++) { opt=read(); x=read(); if(opt==2) top=0; else if(opt==1) { bool jud=true; for(int j=1;j<=top;j++) if(dist(sta[j].pos,x)<=i-sta[j].tim) { jud=false; break; } if(jud) sta[++top]=(Node){x,i}; } else { bool jud=false; for(int j=1;j<=top;j++) if(dist(sta[j].pos,x)<=i-sta[j].tim) { jud=true; break; } if(jud) printf("wrxcsd\n"); else printf("orzFsYo\n"); } } return 0; } T3 牛半仙的妹子序列 解题思路其实就是极长上升序列。
和之前做的God Kowns几乎是一个题，还是李超线段树或者线段树维护单调栈。。
今天刚打了疫苗有点困，可能口胡说不清，所以不懂的请移步 God Kowns
code #include<bits/stdc++.h> #define int long long #define ls x<<1 #define rs x<<1|1 #define ull unsigned long long #define f() cout<<"Pass"<<endl using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+10,mod=998244353; int n,mx,s[N],q[N<<2]; struct Segment_Tree { int mx,sum; }tre[N<<2]; int work(int x,int l,int r,int num) { if(l==r) { if(tre[x].mx>num) return tre[x].sum%mod; return 0; } int mid=(l+r)>>1; if(tre[rs].mx>num) return (q[ls]+work(rs,mid+1,r,num)%mod)%mod; return work(ls,l,mid,num)%mod; } int query(int x,int l,int r,int L,int R) { if(L<=l&&r<=R) { int temp=work(x,l,r,mx); mx=max(mx,tre[x].mx); return temp%mod; } int mid=(l+r)>>1,sum=0; if(R>mid) sum=query(rs,mid+1,r,L,R)%mod; if(L<=mid) sum=(sum+query(ls,l,mid,L,R)%mod)%mod; return sum%mod; } void update(int x,int l,int r,int pos,int num1,int num2) { if(l==r) { tre[x].sum=q[x]=num1; tre[x].mx=num2; return ; } int mid=(l+r)>>1; if(pos<=mid) update(ls,l,mid,pos,num1,num2); else update(rs,mid+1,r,pos,num1,num2); tre[x].mx=max(tre[ls].mx,tre[rs].mx); q[ls]=work(ls,l,mid,tre[rs].mx)%mod; tre[x].sum=(q[ls]+tre[rs].sum)%mod; } signed main() { n=read(); for(int i=1;i<=n;i++) s[i]=read(); for(int i=1;i<=n;i++) { mx=-1; int val=query(1,0,n+1,0,s[i]-1)%mod; if(!val) val=1; update(1,0,n+1,s[i],val,i); } mx=-1; printf("%lld",query(1,0,n+1,0,n)%mod); return 0; }