A. Three Arrays

枚举每个$a_i$，双指针出$b$和$c$的范围，对于$b$中每个预先双指针出$c$的范围，那么对于每个$b$，在对应$c$的区间加$1$，在$a$处区间求和即可。

树状数组维护，时间复杂度$O(n\log n)$。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

B. Expected Shopping

高精度。

 

C. Cover the Paths

贪心，按照LCA的深度从深到浅选择。

#include
     
      #include
      
       using namespace std;const int N=100010,M=262150;int Case,cas,n,m,q,i,op,x,y,z;int g[N],v[N<<1],nxt[N<<1],ed;int size[N],son[N],f[N],d[N],st[N],top[N],dfn;int val[M];int ans,choose[N];struct E{int x,y,z;}e[N];inline bool cmp(const E&a,const E&b){return d[a.z]
       
        size[son[x]])son[x]=v[i];    }}void dfs2(int x,int y){    st[x]=++dfn;top[x]=y;    if(son[x])dfs2(son[x],y);    for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);}void build(int x,int a,int b){    val[x]=0;    if(a==b)return;    int mid=(a+b)>>1;    build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void change(int x,int a,int b,int c){    val[x]++;    if(a==b)return;    int mid=(a+b)>>1;    if(c<=mid)change(x<<1,a,mid,c);    else change(x<<1|1,mid+1,b,c);}int ask(int x,int a,int b,int c,int d){    if(c<=a&&b<=d)return val[x];    int mid=(a+b)>>1,t=0;    if(c<=mid)t=ask(x<<1,a,mid,c,d);    if(d>mid)t+=ask(x<<1|1,mid+1,b,c,d);    return t;}inline int lca(int x,int y){    for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]
       
      
     

　　

D. Elevator

若$t_i<t_j$且$a_i\leq a_j$，那么$j$可以顺手带走$i$，故可以剔除这些$i$使得$a$严格递减。

设$f_i$表示前$i$个人分组的最短时间，则$f_i=\min(\max(f_j,t_i)+2a_{j+1})$，其中$0\leq j<i$，且$f_j<t_{i+1}$，不然不能将$i$和$i+1$分开。

讨论$\max$的来源，Treap维护即可。

时间复杂度$O(n\log n)$。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=200010;const ll inf=1LL<<60;int n,m,i;ll f[N];struct P{	ll t,a;}a[N],q[N];inline bool cmp(const P&a,const P&b){	return a.t
        
         mi,r->mi));	}}*blank=new(node),*root[2],pool[N*2],*cur;inline void Rotatel(node*&x){node*y=x->r;x->r=y->l;x->up();y->l=x;y->up();x=y;}inline void Rotater(node*&x){node*y=x->l;x->l=y->r;x->up();y->r=x;y->up();x=y;}void Ins(node*&x,ll p,ll v){	if(x==blank){		x=new(node);		x->val=p;		x->dp=x->mi=v;		x->l=x->r=blank;		x->p=rand();		return;	}	x->mi=min(x->mi,v);	if(p==x->val){		x->dp=min(x->dp,v);		return;	}	if(p
         
          val){		Ins(x->l,p,v);		if(x->l->p>x->p)Rotater(x);	}else{		Ins(x->r,p,v);		if(x->r->p>x->p)Rotatel(x);	}}ll Ask(node*x,ll a,ll b,ll c,ll d){	if(x==blank)return inf;	if(c<=a&&b<=d)return x->mi;	ll t=c<=x->val&&x->val<=d?x->dp:inf;	if(c
          
           val)t=min(t,Ask(x->l,a,x->val-1,c,d)); if(d>x->val)t=min(t,Ask(x->r,x->val+1,b,c,d)); return t;}inline void ins(int x){ if(f[x]>=inf)return; Ins(root[0],f[x],q[x+1].a); Ins(root[1],f[x],f[x]+q[x+1].a);}int main(){ blank->l=blank->r=blank; while(~scanf("%d",&n)){ for(i=1;i<=n;i++)scanf("%lld%lld",&a[i].t,&a[i].a),a[i].a*=2; sort(a+1,a+n+1,cmp); m=0; for(i=1;i<=n;i++){ while(m&&q[m].a<=a[i].a)m--; q[++m]=a[i]; } q[m+1].t=inf; root[0]=root[1]=blank; ins(0); for(i=1;i<=m;i++){ f[i]=min(Ask(root[0],0,inf,0,q[i].t)+q[i].t,Ask(root[1],0,inf,q[i].t,q[i+1].t-1)); ins(i); } printf("%lld\n",f[m]); }}
          
         
        
       
      
     

　　

E. Code-Cola Plants

对于集合$a$，要满足除$a$以外每个点恰有一条入边，对于集合$b$，要满足除$b$以外每个点恰有一条出边。

建立二分图，左边$2n-2$个点，分别表示每个点需要入边和出边，右边$m$个点，表示原图一条边，那么右边每个点可以供给左边至多两个点。

Hopcroft求最大匹配即可通过。

时间复杂度$O(n\sqrt{n})$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N= 1e6 + 10;int n1, n2;vector
         
           g[N];int mx[N], my[N];int que[N*5];int head,tail;int dx[N], dy[N];bool vis[N];bool find(int u){	for(int i = 0; i < g[u].size(); i ++)		if(! vis[g[u][i]] && dy[g[u][i]] == dx[u] + 1){			vis[g[u][i]] = true;			if(! my[g[u][i]] || find(my[g[u][i]])){				mx[u] = g[u][i];				my[g[u][i]] = u;				return true;			}		}	return false;}int matching(){	memset(mx, 0, (n1 + 5) << 2);	memset(my, 0, (n2 + 5) << 2);	int ans = 0;	while(true){		bool flag = false;		head=1,tail=0;		memset(dx, 0, (n1 + 5) << 2);		memset(dy, 0, (n2 + 5) << 2);		for(int i = 1; i <= n1; i ++)			if(! mx[i])que[++tail]=i;		while(head<=tail){			int u = que[head++];			for(int i = 0; i < g[u].size(); i ++)				if(! dy[g[u][i]]){					dy[g[u][i]] = dx[u] + 1;					if(my[g[u][i]]){						dx[my[g[u][i]]] = dy[g[u][i]] + 1;						que[++tail]=my[g[u][i]];					}					else flag = true;				}		}		if(! flag) break;		memset(vis, 0, max(n1,n2)+5);		for(int i = 1; i <= n1; i ++)			if(! mx[i] && find(i)) ans ++;	}	return ans;}int n, m, a, b;int main(){	while(~ scanf("%d%d%d%d", &n, &m, &a, &b)){		n1 = m; n2 = 2 * n ;		for(int i = 1; i <= m; i ++){			int x, y;			scanf("%d%d", &x, &y);			g[i].clear();			if(a != y) g[i].push_back(y);			if(b != x)g[i].push_back(x + n);			}		int ans = matching();		if(ans == 2 * n - 2){			puts("YES");			for(int i = 1; i <= n; i ++){				if(i != a) printf("%d ", my[i]);			}puts("");			for(int i = n + 1; i <= n + n ; i ++){				if(i != b + n) printf("%d ", my[i]);			}puts("");		}		else puts("NO");			}	}/*4 7 1 41 21 21 42 32 33 43 44 3 1 21 22 44 35 8 3 13 25 23 44 54 12 13 53 1*/
         
        
       
      
     

　　

F. GCD

即保留至少$m-k$个数使得$\gcd$最大，因为$k\leq\frac{n}{2}$，故每个数属于最优解的概率至少为$\frac{1}{2}$。

多次随机选择一个数，认为它必选，那么将其分解质因数，高维前缀和统计每个约数是多少个数的约数即可。

在$10^{18}$内约数个数最大值不超过$200000$，故可以通过。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int C=2730,S=5;const int N=222222;int n,m,i,j,k;int len[N];ll pr[N][30][2];ll pool[N];ll ans;int cnt;ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}ll mul(ll a, ll b, ll n){return (a * b - (ll)(a / (long double) n * b + 1e-3) * n + n) % n;}ll pow(ll a, ll b, ll n){	ll d = 1;	a %= n;	while(b){		if(b & 1) d = mul(d, a, n);		a = mul(a, a, n);		b >>= 1;	}	return d;}bool check(ll a, ll n){	ll m = n - 1, x, y; int i, j = 0;	while(! (m & 1)) m >>= 1, j ++;	x = pow(a, m, n);	for(i = 1; i <= j; x = y, i ++){		y = pow(x, 2, n);		if((y == 1) && (x != 1) && (x != n - 1)) return 1;	}	return y != 1;}bool miller_rabin(int times, ll n){	ll a;	if(n == 1) return 0;	if(n == 2) return 1;	if(! (n & 1)) return 0;	while(times --) if(check(rand() % (n - 1) + 1, n)) return 0;	return 1;}ll pollard_rho(ll n, int c){	ll i = 1, k = 2, x = rand() % n, y = x, d;	while(1){		i ++, x = (mul(x, x, n) + c) % n, d = gcd(y - x, n);		if(d > 1 && d < n) return d;		if(y == x) return n;		if(i == k) y = x, k <<= 1;	}}void findfac(ll n, int c){	if(n == 1) return;	if(miller_rabin(S, n)){		pool[++cnt]=n;		return;	}	ll m = n;	while(m == n) m = pollard_rho(n, c --);	findfac(m, c), findfac(n / m, c);}ll num[222222];ll nowp[50];ll pw[50][100];int lim[50];int tot;int now[50];int cntdiv;ll divisor[3000000];int f[3000000];void dfs(int x,ll y){	if(x==tot){		divisor[++cntdiv]=y;		return;	}	for(int i=0;i<=lim[x];i++)dfs(x+1,y*pw[x][i]);}inline int getid(ll x){return lower_bound(divisor+1,divisor+cntdiv+1,x)-divisor;}void solve(int S){	int i,j,k;	if(num[S]==1)return;	cnt=0;	findfac(num[S],C);	sort(pool+1,pool+cnt+1);len[S]=0;	for(j=1;j<=cnt;j=k){		for(k=j;k<=cnt&&pool[j]==pool[k];k++);		pr[S][len[S]][0]=pool[j];		pr[S][len[S]][1]=k-j;		len[S]++;	}	tot=len[S];	for(j=0;j
        
         goal)k--;			f[k]+=f[j];		}	}	for(i=1;i<=cntdiv;i++)if(f[i]>=m)ans=max(ans,divisor[i]);}int main(){	scanf("%d%d",&n,&m);	m=n-m;//keep >=m numbers	for(i=1;i<=n;i++){		ll x;		scanf("%lld",&x);		num[i]=x;		/*cnt=0;		findfac(x,C);		sort(pool+1,pool+cnt+1);		for(j=1;j<=cnt;j=k){			for(k=j;k<=cnt&&pool[j]==pool[k];k++);			pr[i][len[i]][0]=pool[j];			pr[i][len[i]][1]=k-j;			len[i]++;		}*/	}	ans=1;	for(int ___=8;___;___--){		int x=rand()%n+1;		solve(x);	}	printf("%lld",ans);}
        
       
      
     

　　

G. Berland Post

二分$T$，差分约束判负环。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1010,M=2010,LIM=1000000000;const double eps=1e-8;int n,m,i,unsure[N],a[N];int e[M][3];double L,R,ans,MID;char s[100];double d[N];bool in[N];int vis[N];int q[10000010],h,t;int g[N],v[M],nxt[M],ed;double w[M];inline void add(int x,int y,double z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}bool check(double T){	int i,j,x;	ed=0;	for(i=1;i<=n;i++)g[i]=0;	for(i=1;i<=m;i++)add(e[i][1],e[i][0],T-e[i][2]);	for(i=1;i<=n;i++)if(unsure[i])d[i]=LIM;else d[i]=a[i];	for(h=1,t=0,i=1;i<=n;i++)in[i]=1,q[++t]=i,vis[i]=0;	while(h<=t){		x=q[h++];		for(i=g[x];i;i=nxt[i])if(d[x]+w[i]+eps
        
         3100)return 0;				q[++t]=v[i];			}		}		in[x]=0;	}	for(i=1;i<=n;i++){		if(d[i]+eps<-LIM)return 0;		if(!unsure[i]&&fabs(d[i]-a[i])>eps)return 0;	}	return 1;}int main(){	while(~scanf("%d%d",&n,&m)){		for(i=1;i<=n;i++){			scanf("%s",s);			if(s[0]=='?')unsure[i]=1;else{				unsure[i]=0;				sscanf(s,"%d",&a[i]);			}		}		for(i=1;i<=m;i++)scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);		L=0,R=LIM;		for(int i=77;i--;){			MID=(L+R)/2;			if(check(MID))R=(ans=MID);else L=MID;		}		check(ans);		printf("%.10f\n",ans);		for(i=1;i<=n;i++)printf("%.10f ",d[i]);		puts("");	}}
        
       
      
     

　　

H. Compressed Spanning Subtrees

对于每个点$i$询问除它之外$n-1$个点的虚树大小即可判断出$i$是否是叶子。

选择某个叶子$x$作为根，枚举一个叶子$y$以及一个非叶子$z$，询问$x,y,z$的虚树大小即可判断出$y$是否在$z$的子树中，并可以以此计算每个点子树中的叶子个数。

因为题目保证不存在度数为$2$的点，故每个叶子往上到根路径上每个点的子树内叶子数严格递增，排序即可完成构造。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=110;int n,i,j,is[N],root,size[N];vector
        
         pre[N];int fa[N],vis[N],ans[N];inline bool cmp(int x,int y){return size[x]>size[y];}void dfs(int x,int y){	if(vis[x])return;	vis[x]=1;	ans[x]=y;	for(int i=1;i<=n;i++)if(fa[i]==x)dfs(i,x);	if(fa[x])dfs(fa[x],x);}int main(){	scanf("%d",&n);	if(n==2)return puts("! 1"),0;	for(i=1;i<=n;i++){		printf("? %d",n-1);		for(j=1;j<=n;j++)if(i!=j)printf(" %d",j);		puts("");		fflush(stdout);		scanf("%d",&is[i]);		is[i]=is[i]==n-1;		if(is[i])root=i;	}	size[root]=N;	for(i=1;i<=n;i++)if(!is[i])for(j=1;j<=n;j++)if(j!=root&&is[j]){		printf("? 3 %d %d %d\n",root,i,j);		fflush(stdout);		int t;		scanf("%d",&t);		if(t==3)size[i]++,pre[j].push_back(i);	}	for(i=1;i<=n;i++)if(i!=root&&is[i]){		pre[i].push_back(root);		pre[i].push_back(i);		sort(pre[i].begin(),pre[i].end(),cmp);		for(j=1;j
        
       
      
     

　　

I. Prefix-free Queries

对于一个$k$个子串的询问，将这些串按照字典序排序，那么可以用栈建出前缀关系的树结构，然后就是经典树形DP。

时间复杂度$O(k\log k\log n)$。

#include
     
      #include
      
       using namespace std;typedef pair
       
        E;const int N=400010,SEED=233,SEED2=13331,MO1=998244353,MO2=1000000007;int n,m,i,k,mo,q[N],cnt[N],t,g[N],nxt[N],dp[N];char a[N];int f[N],p[N];struct P{	int l,r,len;}b[N];inline int get(int l,int r){return ((f[r]-1LL*f[l-1]*p[r-l+1])%MO1+MO1)%MO1;}inline int lcp(int a,int b,int c,int d){	int l=1,r=min(b-a+1,d-c+1),mid,t=0;	while(l<=r){		mid=(l+r)>>1;		if(get(a,a+mid-1)==get(c,c+mid-1))l=(t=mid)+1;else r=mid-1;	}	//printf("[%d,%d] [%d,%d] %d\n",a,b,c,d,t);	return t;}inline bool cmp(const P&_a,const P&_b){//a
        
         %d\n",x,y);nxt[y]=g[x];g[x]=y;}void dfs(int x){	dp[x]=1;	for(int i=g[x];i;i=nxt[i]){		dfs(i);		dp[x]=1LL*dp[x]*dp[i]%mo;	}	dp[x]=(dp[x]+cnt[x])%mo;	//printf("dp[%d]=%d\n",x,dp[x]);}int main(){	scanf("%d%d%s",&n,&m,a+1);	for(p[0]=i=1;i<=n;i++){		p[i]=1LL*p[i-1]*SEED%MO1;		f[i]=(1LL*f[i-1]*SEED+a[i])%MO1;	}	while(m--){		scanf("%d%d",&k,&mo);		for(i=1;i<=k;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].len=b[i].r-b[i].l+1;		sort(b+1,b+k+1,cmp);		for(i=0;i<=k;i++)g[i]=0;		cnt[0]=1;		for(t=0,i=1;i<=k;i++){			if(t&&equal(b[q[t]],b[i])){				cnt[q[t]]++;				continue;			}			while(t&&!isprefix(b[q[t]],b[i]))t--;			add(q[t],i);			q[++t]=i;			cnt[i]=1;		}		//for(i=1;i<=k;i++)printf("cnt[%d]=%d\n",i,cnt[i]);				dfs(0);		printf("%d\n",((dp[0]-1)%mo+mo)%mo);	}}/*10 100aabbaacaba5 20 1 2 3 4 5 6 7 8 9 10*/
        
       
      
     

　　

J. Subsequence Sum Queries

分治，预处理出$mid$到$[l,r]$每个点的背包，然后利用这个信息处理所有经过$mid$的询问。

时间复杂度$O((nm+q)\log n+qm)$。

#include
     
      #include
      
       using namespace std;typedef vector
       
        V;const int N=200010,M=25,P=1000000007;int n,m,Q,i,a[N],f[N][M],g[N][M],e[N][3];inline void up(int&a,int b){a=a+b
        
         r||!v.size())return;	int mid=(l+r)/2;	//[i..mid] [mid+1..i]	for(int i=l;i<=mid+1;i++)for(int j=0;j
         
          =l;i--){		for(int j=0;j
          
           mid)vr.push_back(x); else if(e[x][1]
          
         
        
       
      
     

　　

K. Consistent Occurrences

将询问按长度分组，则最多只有$O(\sqrt{n})$种长度，对于每种长度$O(n\log n)$计算答案即可。

#include
     
      #include
      
       #include
       
        #include
        
       
      
     

　　

L. Increasing Costs

建出最短路图后，将每条边拆点，那么答案就是每条边代表的点在Dominator Tree中的子树大小。

#include
     
      typedef long long ll;const int N=500010,M=1000010,K=22;const ll inf=1LL<<60;int n,m,S,cnt,i,x,deg[N],g[N],v[M],w[M],nxt[M],ed;int size[N],sum[N],id[N],h,t,q[N],dep[N],f[N][K],G[N],NXT[N],V[N];ll d[N];struct E{int x,y,w;}a[M>>1];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void addedge(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}inline void add(int x,int y){deg[y]++;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void addtree(int x,int y){V[++ed]=y;NXT[ed]=G[x];G[x]=ed;}struct PI{  ll x;int y;  PI(){}  PI(ll _x,int _y){x=_x,y=_y;}  inline PI operator+(const PI&b){return x<=b.x?PI(x,y):b;}}val[2222222];void build(int x,int a,int b){  val[x]=PI(inf,a);  if(a==b)return;  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}inline void change(int x,int a,int b,int c,ll d){  if(a==b){val[x].x=d;return;}  int mid=(a+b)>>1;  c<=mid?change(x<<1,a,mid,c,d):change(x<<1|1,mid+1,b,c,d);  val[x]=val[x<<1]+val[x<<1|1];}inline int lca(int x,int y){  int i;  if(dep[x]
      
       =dep[y])x=f[x][i];  if(x==y)return x;  for(i=K-1;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];  return f[x][0];}void dfs(int x){  for(int i=G[x];i;i=NXT[i])dfs(V[i]),size[x]+=size[V[i]];  sum[id[x]]=size[x];}int main(){  read(n),read(m);  for(i=1;i<=m;i++){    read(a[i].x),read(a[i].y),read(a[i].w);    addedge(a[i].x,a[i].y,a[i].w);    addedge(a[i].y,a[i].x,a[i].w);  }  S=1;  for(i=1;i<=n;i++)d[i]=inf;  build(1,1,n),change(1,1,n,S,d[S]=0);  while(val[1].x