每个点能爆炸到的是个区间，线段树优化建图，并求出SCC进行缩点。
剔除所有不含任何$n$个点的SCC之后，最小价钱为每个入度为$0$的SCC中最小点权之和，用set维护即可。
时间庞大度$O(n\log n)$。
#include<cstdio> #include<algorithm> #include<set> using namespace std; typedef pair<int,int>P; const int N=1000010,M=8000000; int n,m,i,j,x,y;long long ans; struct E{ int p,r,c; }a[N]; P b[N]; int root,l[N],r[N],tot; set<P>T[N]; int g[2][N],nxt[2][M],v[2][M],ed,f[N],q[N],t,vis[N],ban[N]; inline void add(int x,int y){ v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed; v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed; } inline void ADD(int x,int y){ v[1][++ed]=y;nxt[1][ed]=g[1][x];g[1][x]=ed; } int build(int a,int b){ int x; if(a==b)x=::b[a].second; else x=++tot; if(a==b)return x; int mid=(a+b)>>1; l[x]=build(a,mid); r[x]=build(mid+1,b); add(x,l[x]); add(x,r[x]); return x; } void ins(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){ add(p,x); return; } int mid=(a+b)>>1; if(c<=mid)ins(l[x],a,mid,c,d,p); if(d>mid)ins(r[x],mid+1,b,c,d,p); } inline int askl(int x){//min >=x int l=1,r=n,mid,t; while(l<=r){ mid=(l+r)>>1; if(b[mid].first>=x)r=(t=mid)-1;else l=mid+1; } return t; } inline int askr(int x){//max <=x int l=1,r=n,mid,t; while(l<=r){ mid=(l+r)>>1; if(b[mid].first<=x)l=(t=mid)+1;else r=mid-1; } return t; } void dfs1(int x){ vis[x]=1; for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]); q[++t]=x; } void dfs2(int x,int y){ vis[x]=0;f[x]=y; for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y); } void dfs3(int x){ if(ban[x])return; ban[x]=1; for(int i=g[1][x];i;i=nxt[1][i])dfs3(v[1][i]); } inline void solve(int x){ if(vis[x])return; vis[x]=1; for(int i=g[1][x];i;i=nxt[1][i])dfs3(v[1][i]); } int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].p,&a[i].r,&a[i].c),b[i]=P(a[i].p,i); sort(b+1,b+n+1); tot=n; root=build(1,n); for(i=1;i<=n;i++){ int l=askl(a[i].p-a[i].r); int r=askr(a[i].p+a[i].r); ins(root,1,n,l,r,i); } for(t=0,i=1;i<=tot;i++)if(!vis[i])dfs1(i); for(i=tot;i;i--)if(vis[q[i]])dfs2(q[i],q[i]); ed=0; for(i=1;i<=tot;i++)g[1][i]=0; for(i=1;i<=tot;i++)for(j=g[0][i];j;j=nxt[0][j])if(f[i]!=f[v[0][j]])ADD(f[i],f[v[0][j]]); for(i=1;i<=n;i++)solve(f[i]); for(i=1;i<=n;i++)if(!ban[f[i]])T[f[i]].insert(P(a[i].c,i)); for(i=1;i<=tot;i++)if(!ban[i]&&f[i]==i)ans+=T[i].begin()->first; while(m--){ scanf("%d%d",&x,&y); if(!ban[f[x]]){ ans-=T[f[x]].begin()->first; T[f[x]].erase(P(a[x].c,x)); T[f[x]].insert(P(a[x].c=y,x)); ans+=T[f[x]].begin()->first; } printf("%lld\n",ans); } }
B. Balls
用set维护所有球和墙的坐标，操纵1显然。
对付操纵2，删除最左的坐标，将所有坐标减去$1$，然后插手墙的坐标，可以通过记录全局减去几多来实现。
时间庞大度$O(n\log n)$。
#include<cstdio> #include<set> using namespace std; int n,q,p,op,x,tag,i,a[1000000];set<int>T; int main(){ scanf("%d%d%d",&n,&q,&p); T.insert(p); while(n--)scanf("%d",&x),T.insert(x); while(q--){ scanf("%d",&op); if(op==1){ scanf("%d",&x); x+=tag; T.insert(x); }else{ T.erase(T.begin()); tag++; T.insert(p+tag); } } n=0; for(set<int>::iterator it=T.begin();it!=T.end();it++)a[++n]=(*it)-tag; for(i=1;i<n;i++)printf("%d ",a[i]); }
C. Flip a Coin
设$f[i][j]$暗示与$A$串KMP指针为$i$，与$B$串KMP指针为$j$的概率，高斯消元即可。
时间庞大度$O(n^6)$。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=25,M=505; const double eps=1e-10; int n,m,i,j,k,ga[N][2],gb[N][2],cnt,id[N][N];char a[N],b[N]; double g[M][M],x[M],ans[3]; void getnxt(char*a,int n,int g[][2]){ static int nxt[N]; for(int j=0,i=2;i<=n;nxt[i++]=j){ while(j&&a[j+1]!=a[i])j=nxt[j]; if(a[j+1]==a[i])j++; } for(int i=0;i<n;i++){ for(int j=0;j<2;j++){ char t=j==0?‘H‘:‘T‘; int k=i; while(k&&a[k+1]!=t)k=nxt[k]; if(a[k+1]==t)k++; g[i][j]=k; } } } int main(){ scanf("%s",a+1); n=strlen(a+1); scanf("%s",b+1); m=strlen(b+1); getnxt(a,n,ga); getnxt(b,m,gb); for(i=0;i<=n;i++)for(j=0;j<=m;j++)id[i][j]=++cnt; for(i=1;i<=cnt;i++)g[i][i]=1; for(i=0;i<n;i++)for(j=0;j<m;j++){ for(k=0;k<2;k++){ int x=ga[i][k],y=gb[j][k]; g[id[x][y]][id[i][j]]-=0.5; } } g[1][cnt+1]=1; for(i=1;i<=cnt;i++){ for(k=j=i;j<=cnt;j++)if(fabs(g[j][i])>fabs(g[k][i]))k=j; for(j=i;j<=cnt+1;j++)swap(g[i][j],g[k][j]); for(j=i+1;j<=cnt;j++){ double t=g[j][i]/g[i][i]; for(k=i;k<=cnt+1;k++)g[j][k]-=g[i][k]*t; } } for(x[cnt]=g[cnt][cnt+1]/g[cnt][cnt],i=cnt-1;i;i--){ for(x[i]=g[i][cnt+1],j=cnt;j>i;j--)x[i]-=x[j]*g[i][j]; x[i]/=g[i][i]; } for(i=0;i<=n;i++)for(j=0;j<=m;j++){ if(i==n&&j<m)ans[0]+=x[id[i][j]]; if(i<n&&j==m)ans[1]+=x[id[i][j]]; if(i==n&&j==m)ans[2]+=x[id[i][j]]; } for(i=0;i<3;i++)printf("%.15f\n",ans[i]); }
D. Octagons
若相邻两步形如$aa$，说明前进又撤退退却，可以消去。
若持续5步形如$ababa$，，说明在某个八边形上顺时针/逆时针走了5步，可以用$bab$替代，即反标的目的走3步。
如此重复迭代措置惩罚惩罚，若能消完则说明是关闭路径。
时间庞大度$O(n)$。