今天开始换湖南的题了,前几天一直在考山东的省队集训,感觉之前题目非常毒瘤而且不给部分分,没有写题解的欲望。
T1
给出一棵n个点的树,支持换根、子树权值加、求子树权值和,查询LCA,n<=3e5。
如果不涉及LCA,那么只要求出DFS序之后讨论一下即可。
对于换根求LCA,我们只需要先求u和root的lca还有v和root的lca,如果不同,则u和v一定处于root到原来根的路径上的两棵子树,这时候我们只需要找到较深的那个即可。如果相同,则为u和v的lca,之后这道题就做完了。
另外,如果想用LCT求LCA,只需要access(u),然后在access(v)后的那个splay根就是答案。为什么?模拟一下就好了。但是这样因为常数太大而无法通过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
#include <bits/stdc++.h> #define mxn 300005 #define ll long long using namespace std; #ifndef local char ibuf[65536],*ih,*it; #define getc() ((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++) #else #define getc() getchar() #endif inline int read(){ int s=0,f=1; char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc(); return s*f; } struct edge{ int v,nxt; }e[2*mxn]; int prv[mxn],tot,n,q,ov[mxn],ox[mxn],oy[mxn],oz[mxn],w[mxn],rid[mxn]; int dep[mxn],sz[mxn],son[mxn],fa[mxn],top[mxn],idx,lo[mxn],hi[mxn]; inline void dfs1(int u,int ft){ dep[u]=dep[ft]+1,sz[u]=1,fa[u]=ft; for(int i=prv[u];i;i=e[i].nxt) if(e[i].v!=ft) { dfs1(e[i].v,u); sz[u]+=sz[e[i].v]; if(sz[son[u]]<sz[e[i].v]) son[u]=e[i].v; } } inline void dfs2(int u,int tp){ top[u]=tp,lo[u]=++idx,rid[idx]=u; if(son[u]) dfs2(son[u],tp); for(int i=prv[u];i;i=e[i].nxt) if(!top[e[i].v]) dfs2(e[i].v,e[i].v); hi[u]=idx; } inline int lca(int u,int v){ int f1=top[u],f2=top[v]; while(f1!=f2){ if(dep[f1]>dep[f2]) u=fa[f1],f1=top[u]; else v=fa[f2],f2=top[v]; } return dep[u]<dep[v]?u:v; } ll sumv[mxn<<2],addv[mxn<<2],res; int ql,qr,val; inline void build(int o,int l,int r){ if(l==r) sumv[o]=w[rid[l]],addv[o]=0; else { int m=l+r>>1; build(o<<1,l,m),build(o<<1|1,m+1,r); sumv[o]=sumv[o<<1]+sumv[o<<1|1],addv[o]=0; } } inline void pushdown(int o,int l,int r){ if(addv[o]) { int m=l+r>>1; addv[o<<1]+=addv[o],addv[o<<1|1]+=addv[o]; sumv[o<<1]+=addv[o]*(m-l+1),sumv[o<<1|1]+=addv[o]*(r-m); addv[o]=0; } } inline void update(int o,int l,int r){ if(l!=r) pushdown(o,l,r); if(ql<=l&&r<=qr) addv[o]+=val,sumv[o]+=1ll*val*(r-l+1); else { int m=l+r>>1; if(ql<=m) update(o<<1,l,m); if(m<qr) update(o<<1|1,m+1,r); sumv[o]=sumv[o<<1]+sumv[o<<1|1]; } } inline void query(int o,int l,int r){ if(l!=r) pushdown(o,l,r); if(ql<=l&&r<=qr) res+=sumv[o]; else { int m=l+r>>1; if(ql<=m) query(o<<1,l,m); if(m<qr) query(o<<1|1,m+1,r); } } int root=1; int f[20][mxn],bit[32]; inline void dfs(int u,int ft){ f[0][u]=ft; for(int i=1;bit[i]<=dep[u];++i) f[i][u]=f[i-1][f[i-1][u]]; for(int i=prv[u];i;i=e[i].nxt) if(e[i].v!=ft) dfs(e[i].v,u); } inline int ganc(int u,int v){ for(int i=19;i>=0;--i) if(f[i][v]&&dep[f[i][v]]>dep[u]) v=f[i][v]; return v; } inline bool in(int x,int y=root){ return lo[y]<=lo[x]&&lo[x]<=hi[y]; } inline int dis(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } inline int llca(int u,int v){ if(u==v) return u; int l1=lca(u,root),l2=lca(v,root),l3=lca(u,v); if(l1!=l2) { if(dep[l1]>dep[l2]) return l1; else return l2; } return l3; } inline void work(){ for(int i=0;i<=30;++i) bit[i]=1<<i; dfs(1,0); register int u,v; ll ans; for(int i=1;i<=q;++i) { if(ov[i]==1) { root=ox[i]; } else if(ov[i]==2) { u=ox[i],v=oy[i]; u=llca(u,v); if(u==root) { ql=1,qr=n,val=oz[i],update(1,1,n); } else if((lo[root]<=lo[u]&&hi[u]<=hi[root])||(hi[u]<lo[root]||lo[u]>hi[root])) { ql=lo[u],qr=hi[u],val=oz[i],update(1,1,n); } else { v=ganc(u,root),val=oz[i]; ql=1,qr=lo[v]-1; if(ql<=qr) update(1,1,n); ql=hi[v]+1,qr=n; if(ql<=qr) update(1,1,n); } } else if(ov[i]==3) { u=ox[i]; if(u==root) { ql=1,qr=n,res=0,query(1,1,n); ans=res; } else if((lo[root]<=lo[u]&&hi[u]<=hi[root])||(hi[u]<lo[root]||lo[u]>hi[root])) { ql=lo[u],qr=hi[u],res=0,query(1,1,n); ans=res; } else { v=ganc(u,root),ans=0; ql=1,qr=lo[v]-1; if(ql<=qr) res=0,query(1,1,n),ans+=res; ql=hi[v]+1,qr=n; if(ql<=qr) res=0,query(1,1,n),ans+=res; } printf("%lld\n",ans); } } } int main(){ n=read(),q=read(); for(int i=1;i<=n;++i) w[i]=read(); register int u,v; for(int i=1;i<n;++i) { u=read(),v=read(); e[++tot]=(edge){v,prv[u]},prv[u]=tot; e[++tot]=(edge){u,prv[v]},prv[v]=tot; } dfs1(1,0),dfs2(1,1); build(1,1,n); bool flag1=1,flag2=1,flag3=1; for(int i=1;i<=q;++i) { ov[i]=read(); if(ov[i]==1) ox[i]=read(),flag1=0; else if(ov[i]==2) { ox[i]=read(),oy[i]=read(),oz[i]=read(); flag2=0; if(ox[i]!=oy[i]) flag3=0; } else if(ov[i]==3) ox[i]=read(); } work(); } |
T2
题意略。
首先,对于询问(x,y),答案为\(f(x,y)=min_{i}{sum(y)-sum(i)+(x-y)\,S(i)+i\,S(i)}\)。
之后,发现这是个斜率优化的式子,就是令\(b=f - sum(y)\),\(y=i\,S(i) - sum(i)\),\(x=S(i)\),我们想最大化截距。
把每个决策点看成点(x,y),那么对于两个决策点i和j,如果i<j且s(i)>s(j),那么i一定不优,因此我们需要保证点的横坐标单调递增,且需要形成一个下凸包,维护就好了。
计算答案的时候直接在凸包上三分或者二分就好了。因为精度问题,我选择了差积判断凸包以及三分凸包算答案的方法,这样做不设计斜率的计算,精度也就有了保证,虽然三分会慢一些。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define ll long long #define mxn 500005 using namespace std; #ifndef local char ibuf[65536],*ih,*it; #define getc() ((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++) #else #define getc() getchar() #endif inline int read(){ int s=0,f=1; char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc(); return s*f; } struct que{int x,id;}; ll ans[mxn],sum[mxn]; vector<que> vc[mxn]; int n,m,s[mxn],qh,qt; struct data{ ll x,y; int p; }q[mxn]; inline data operator + (const data &a,const data &b){return (data){a.x+b.x,a.y+b.y};} inline data operator - (const data &a,const data &b){return (data){a.x-b.x,a.y-b.y};} inline bool judge(data a,data b){return 1.0L*a.x*b.y<=1.0L*a.y*b.x;} inline void gmin(ll &a,ll b){if(a>b)a=b;} inline ll calc(data d,int x,int y){return sum[y]+d.y+(x-y)*d.x;} int main(){ n=read(); for(int i=1;i<=n;++i) s[i]=read(),sum[i]=sum[i-1]+s[i]; m=read(); register int x,y; for(int i=1;i<=m;++i) { x=read(),y=read(); vc[y].push_back((que){x,i}); } qt=0; for(int i=1;i<=n;++i) { data cur=(data){s[i],1ll*i*s[i]-sum[i],i}; while((qt&&s[q[qt].p]>=s[i])||(qt>1&&judge(q[qt]-q[qt-1],cur-q[qt-1]))) --qt; q[++qt]=cur; for(auto j:vc[i]) { ll res=1ll<<60; int L=1,M,R=qt,P1,P2,pl=(j.x>=i?1:i-j.x+1); ll V1,V2; while(R>L){ M=L+R>>1; if(q[M].p>=pl) R=M; else L=M+1; } L=R,R=qt; while(R-L>=5){ P1=(L*2+R)/3,P2=(L+R*2)/3; V1=calc(q[P1],j.x,i),V2=calc(q[P2],j.x,i); if(V1<=V2) gmin(res,V1),R=P2-1; else gmin(res,V2),L=P1+1; } for(int k=L;k<=R;++k) gmin(res,calc(q[k],j.x,i)); ans[j.id]=res; } } for(int i=1;i<=m;++i) printf("%lld\n",ans[i]); } |
T3
另序列B表示序列A的前缀按位或和,计算在A中元素小于2^k且B单调递增的情况下的A的个数。
首先如果我们直接令f[i][j]表示i个数用了j位(考虑空位),那么我们就可以通过NTT优化到O(nklogk),获得59分。
之后,可以改一下DP数组的定义,我们不需要考虑没有使用的空位,只需要维护数位之间的相对标号即可,这样转移的话可以倍增进行,转移的式子就是\(f[a+b][x]=\sum_{i=0}^{x-1}f[a][i]*f[b][x-i]*C_{x}^{i}2^{bi}\)。复杂度O(klognlogk)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define ll long long #define P 998244353 #define mod 998244353 #define mxn 65539 using namespace std; inline ll qpow(ll a,ll b=mod-2){ ll ret=1; while(b){ if(b&1) ret=ret*a%mod; a=a*a%mod,b>>=1; } return ret; } ll G[2][mxn],mxl; int rev[mxn]; inline void ntt_init(){ register ll w=1,wn=qpow(3,(P-1)/mxl); for(int i=0;i<=mxl;++i,w=w*wn%P) G[0][i]=w; } inline void ntt_prep(int n){ for(int i=0;i<n;++i) { if(i&1) rev[i]=(rev[i>>1]>>1)|(n>>1); else rev[i]=rev[i>>1]>>1; } } inline void ntt(int *s,int n,int o){ register int i,j,l,m,t,u; for(i=0,j=0;i<n;++i) if(i>rev[i]) swap(s[i],s[rev[i]]); for(l=2,m=1;l<=n;m=l,l<<=1) { for(i=0;i<m;++i) G[1][i]=G[0][o==1?(mxl/l*i):(mxl-mxl/l*i)]; for(i=0;i<n;i+=l) for(j=0;j<m;++j) { t=s[i+j],u=G[1][j]*s[i+j+m]%mod; s[i+j]=t+u,s[i+j+m]=t-u; s[i+j]>=mod?s[i+j]-=mod:0; s[i+j+m]<0?s[i+j+m]+=mod:0; } } if(o==-1) { register ll inv=qpow(n); for(i=0;i<n;++i) s[i]=s[i]*inv%mod; } } ll fac[mxn],inv[mxn],pw[mxn]; inline ll C(int N,int M){ if(M>N) return 0; return fac[N]*inv[M]%mod*inv[N-M]%mod; } int n,m,f[32][mxn],g[mxn],a[mxn],b[mxn],bit[32]; signed main(){ scanf("%d%d",&n,&m); fac[0]=inv[0]=pw[0]=1; register int lim=max(n,m); for(int i=1;i<=lim;++i) fac[i]=fac[i-1]*i%mod,pw[i]=pw[i-1]<<1,pw[i]>=mod?pw[i]-=mod:0; inv[lim]=qpow(fac[lim]); for(int i=lim-1;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod; register int c=0,p=1; mxl=65536,ntt_init(); int len=1; while(len<(m<<1)) len<<=1; ntt_prep(len); for(int i=1;i<=m;++i) f[0][i]=1; int lm=0; for(int i=0;i<=30;++i) bit[i]=1<<i; for(int i=1,t=2;t<=n;++i,t<<=1) { ++lm; for(int j=0;j<len;++j) a[j]=b[j]=0; register ll p2=pw[t>>1],cp=p2; for(int j=1;j<=m;++j) a[j]=f[i-1][j]*inv[j]%P*cp%P,cp=cp*p2%P,b[j]=f[i-1][j]*inv[j]%P; b[0]=0; ntt(a,len,1),ntt(b,len,1); for(int j=0;j<len;++j) a[j]=1ll*a[j]*b[j]%P; ntt(a,len,-1); for(int j=1;j<=m;++j) f[i][j]=a[j]*fac[j]%P; } bool fd=0; for(int i=0,t;bit[i]<=n;++i) if(n&bit[i]) { if(!fd) { memcpy(g,f[i],sizeof(g)),fd=1; continue; } t=bit[i]; for(int j=0;j<len;++j) a[j]=b[j]=0; register ll p2=pw[t],cp=p2; for(int j=1;j<=m;++j) a[j]=g[j]*cp%P*inv[j]%P,cp=cp*p2%P,b[j]=f[i][j]*inv[j]%P; b[0]=0; ntt(a,len,1),ntt(b,len,1); for(int j=0;j<len;++j) a[j]=1ll*a[j]*b[j]%P; ntt(a,len,-1); for(int j=0;j<=m;++j) g[j]=a[j]*fac[j]%P; } g[0]=0; int ans=0; for(int i=0;i<=m;++i) ans+=C(m,i)*g[i]%mod,ans>=mod?ans-=mod:0; printf("%d",ans); } |
叨叨几句... NOTHING