目前进度：6/6

码量：2785(3957)+2619(4087)+2292(2868)+1202(1351)+1808(2302)+1245

T1 最小公倍数 先离散化，然后分块处理，按A坐标每根号n分一块，块内按B坐标排序，把询问也按B坐标排序

对于每一块，把在该块之前的路径和询问都可以扫一遍加入到并查集中，时间复杂度$O(n)$，共$O(\sqrt{m})$块，总复杂度$O(n\sqrt{m})$。

对于每个询问，把在该块的散块加到新的并查集中。可以建一个“虚并查集”，只保留$\sqrt{n}$个要更改的点，对于每个询问时间复杂度$O(\sqrt{m})$，总复杂度$O(q\sqrt{m})$。

如果一行多于$\sqrt{n}$个特殊处理而不能分块，因为这样要散的点会达到$O(n)$级别。对于这样的行，直接$O(n)$扫一遍，这样的行不会超过$\sqrt{m}$个，总复杂度$O(n\sqrt{m})$。

综上所述，总复杂度$O((n+q)\sqrt{m})$。

#include<bits/stdc++.h>
#define N 100100
using namespace std;struct W{int x,y;};bool an[N],ok[N];
int Q,n,m,o,w,e,ee,i,j,k,I,x,y,X,Y,A,B,ca,cb,nv,id,tw,ta,S=200,va[N],vb[N],sz[N],F[N],sa[N],sb[N],FF[N],SA[N],SB[N],bl[N],xw[N],xa[N],E[N];
struct P{int x,y,A,B,id;}p[N],q[N];bool cmp(P a,P b){return a.B<b.B;}
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
void uni(int x,int y,int A,int B){x=gf(x),y=gf(y);F[x]=y;sa[y]=max(max(sa[y],sa[x]),A);sb[y]=max(max(sb[y],sb[x]),B);}
int fg(int x){return FF[x]==x?x:FF[x]=fg(FF[x]);}
void niu(int x,int y,int A,int B){x=fg(x);y=fg(y);FF[x]=y;SA[y]=max(max(SA[y],SA[x]),A);SB[y]=max(max(SB[y],SB[x]),B);}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d%d",&x,&y,&A,&B),p[i]=P{x,y,A,B},va[i]=A,vb[i]=B;
	sort(va+1,va+m+1);ca=unique(va+1,va+m+1)-va-1;sort(vb+1,vb+m+1);cb=unique(vb+1,vb+m+1)-vb-1;
	for(i=1;i<=m;i++)p[i].A=lower_bound(va+1,va+ca+1,p[i].A)-va,p[i].B=lower_bound(vb+1,vb+cb+1,p[i].B)-vb,sz[p[i].A]++;
	for(sort(p+1,p+m+1,cmp),i=id=1;i<=ca;i++)if(nv+sz[i]<=S)nv+=sz[i],bl[i]=id;else
		if(sz[i]>S){if(nv)id++;bl[i]=id,ok[id++]=1,nv=0;}else nv=sz[i],bl[i]=++id;
	if(!nv)id--;
	for(scanf("%d",&Q),i=1;i<=Q;i++){
		scanf("%d%d%d%d",&x,&y,&A,&B);
		o=lower_bound(va+1,va+ca+1,A)-va;if(va[o]!=A){an[i]=1;continue;}A=o;
		o=lower_bound(vb+1,vb+cb+1,B)-vb;if(vb[o]!=B){an[i]=1;continue;}B=o;
		q[++w]=P{x,y,A,B,i};
	}
	for(sort(q+1,q+w+1,cmp),I=1;I<=id;I++)if(ok[I]){
		for(tw=0,i=1;i<=w;i++)if(bl[q[i].A]==I)xw[++tw]=i;
		for(i=1;i<=n;i++)F[i]=i,sa[i]=sb[i]=0;
		for(i=j=1;i<=tw;i++){
			for(o=xw[i];p[j].B<=q[o].B&&j<=m;j++)if(bl[p[j].A]<=I)uni(p[j].x,p[j].y,p[j].A,p[j].B);
			X=gf(q[o].x);Y=gf(q[o].y);
			if(X!=Y||sa[X]!=q[o].A||sb[Y]!=q[o].B)an[q[o].id]=1;
		}
	}else{
		for(tw=ta=0,i=1;i<=w;i++)if(bl[q[i].A]==I)xw[++tw]=i;
		for(i=1;i<=m;i++)if(bl[p[i].A]==I)xa[++ta]=i;
		for(i=1;i<=n;i++)F[i]=i,sa[i]=sb[i]=0;
		for(i=j=1;i<=tw;i++){
			for(o=xw[i];p[j].B<=q[o].B&&j<=m;j++)if(bl[p[j].A]<I)uni(p[j].x,p[j].y,p[j].A,p[j].B);
			for(e=0,k=1;k<=ta;k++)if(p[xa[k]].A<=q[o].A&&p[xa[k]].B<=q[o].B)E[++e]=gf(p[xa[k]].x),E[++e]=gf(p[xa[k]].y);
			E[++e]=gf(q[o].x);E[++e]=gf(q[o].y);sort(E+1,E+e+1);ee=unique(E+1,E+e+1)-E-1;
			for(k=1;k<=ee;k++)FF[k]=k,SA[k]=sa[E[k]],SB[k]=sb[E[k]];
			for(k=1;k<=ta;k++)if(p[xa[k]].A<=q[o].A&&p[xa[k]].B<=q[o].B)
				niu(lower_bound(E+1,E+ee+1,gf(p[xa[k]].x))-E,lower_bound(E+1,E+ee+1,gf(p[xa[k]].y))-E,p[xa[k]].A,p[xa[k]].B);
			X=fg(lower_bound(E+1,E+ee+1,gf(q[o].x))-E);Y=fg(lower_bound(E+1,E+ee+1,gf(q[o].y))-E);
			if(X==Y&&SA[X]==q[o].A&&SB[Y]==q[o].B)an[q[o].id]=0;else an[q[o].id]=1;
		}
	}
	for(i=1;i<=Q;i++)puts(an[i]?"No":"Yes");
}

T2 网络 对每条链取反即为该链的贡献区间。那么按照时间建线段树，在每个节点上保留贡献区间和贡献值。然后离线对线段树上每个点做一遍扫描线，可以用树状数组完成。空间复杂度$O(mlg^2n)$，时间复杂度$O(nlg^3n)$，常数非常小。

#include<bits/stdc++.h>
#define N 200200
using namespace std;int n,m,i,j,k,x,y,z,e,o,t,w,lv,id,di,ans,tot,c[N],AN[N],fir[N],ne[N],la[N],st[N],to[N],rt[N*3],sz[N],F[N],h[N],hs[N],bl[N];
struct P{int x,y,z,l,r;}p[N];bool cmp(P a,P b){return a.z>b.z;}
struct W{int l,r;bool operator<(W a)const{return a.l>l;}}q[N];bool cp(W a,W b){return a.l<b.l;}
struct E{int l,r,z;bool operator<(E a)const{return a.l>l;}};vector<E>V[N*3];vector<W>QU[N*3];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){sz[x]=1;int i,y;for(i=fir[x];i;i=ne[i])if(F[x]!=la[i]){F[y=la[i]]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];if(sz[y]>sz[hs[x]])hs[x]=y;}}
void dfs2(int x,int f){st[x]=++di;bl[x]=f;if(hs[x])dfs2(hs[x],f);for(int i=fir[x];i;i=ne[i])if(F[x]!=la[i]&&la[i]!=hs[x])dfs2(la[i],la[i]);}
void ins(int k,int l,int r,int x,int y,int L,int R,int z){
	if(x<=l&&r<=y){V[k].push_back(E{L,R,z});return;}int md=l+r>>1;
	if(x<=md)ins(k<<1,l,md,x,y,L,R,z);if(y>md)ins(k<<1|1,md+1,r,x,y,L,R,z);
}
void qu(int k,int l,int r,int x,int y,int z){
	QU[k].push_back(W{y,z});if(l==r)return;int md=l+r>>1;
	if(x<=md)qu(k<<1,l,md,x,y,z);else qu(k<<1|1,md+1,r,x,y,z);
}
void add(int x,int z){for(;x;x-=x&-x)c[x]=max(c[x],z);}
void dda(int x){for(;x;x-=x&-x)c[x]=-1;}
int get(int x){int VV=-1;for(;x<=n;x+=x&-x)VV=max(VV,c[x]);return VV;}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),dfs2(1,1),i=1;i<=m;i++){
		scanf("%d",&o);
		if(!o)scanf("%d%d%d",&x,&y,&z),w++,p[w].x=x,p[w].y=y,p[w].z=z,p[w].l=i,to[i]=w;
		if(o==1)scanf("%d",&x),p[to[x]].r=i;
		if(o==2)scanf("%d",&x),qu(1,1,m,i,st[x],++e);
	}
	for(i=1;i<=w;i++)if(!p[i].r)p[i].r=m;
	for(i=1;i<=w;i++){
		for(x=p[i].x,y=p[i].y,t=0;bl[x]!=bl[y];q[++t].l=st[bl[x]],q[t].r=st[x],x=F[bl[x]])if(h[bl[x]]<h[bl[y]])swap(x,y);
		if(st[x]>st[y])swap(x,y);q[++t].l=st[x];q[t].r=st[y];
		for(sort(q+1,q+t+1,cp),lv=j=1;j<=t;lv=q[j++].r+1)if(lv<=q[j].l-1)ins(1,1,m,p[i].l,p[i].r,lv,q[j].l-1,p[i].z);
		if(lv<=n)ins(1,1,m,p[i].l,p[i].r,lv,n,p[i].z);
	}
	for(i=1;i<=524288;i++)sort(V[i].begin(),V[i].end()),sort(QU[i].begin(),QU[i].end());
	for(i=1;i<=n;i++)c[i]=-1;for(i=1;i<=e;i++)AN[i]=-1;
	for(i=1;i<=524288;i++){
		for(j=k=0;j<QU[i].size();AN[QU[i][j].r]=max(AN[QU[i][j].r],get(QU[i][j].l)),j++)for(;k<V[i].size()&&V[i][k].l<=QU[i][j].l;k++)add(V[i][k].r,V[i][k].z);
		for(j=k=0;j<QU[i].size();j++)for(;k<V[i].size()&&V[i][k].l<=QU[i][j].l;k++)dda(V[i][k].r);
	}
	for(i=1;i<=e;i++)printf("%d\n",AN[i]);
}

T3 树 先对树DFS，每颗子树开一颗线段树，利用儿子进行线段树合并，空间nlgn。对连边重构树，记录连点的父亲和指向位置。省空间，指向位置不递推。对于询问，先找出两点所在树，然后在重构树上找LCA。最后一步暴力，找到指向位置。找到指向位置后求出两点标号，求出标号后再在原树上求LCA。

#include<bits/stdc++.h>
#define N 100100
#define M 2004000
using namespace std;typedef long long LL;LL X,Y,AN,q[N],h[N];
int n,m,Q,i,j,x,y,t,o,id,bx,by,tot,fir[N],ne[N*2],la[N*2],sz[N],F[N][17],G[N][17],d[N],T[N],to[N],bl[N],L[M],R[M],S[M],D[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void bt(int&k,int l,int r,int x){
	S[k=++id]++;if(l==r)return;int md=l+r>>1;
	if(x<=md)bt(L[k],l,md,x);else bt(R[k],md+1,r,x);
}
int mg(int x,int y){
	if(!x||!y)return x|y;int k=++id;S[k]=S[x]+S[y];
	L[k]=mg(L[x],L[y]);R[k]=mg(R[x],R[y]);return k;
}
void dfs(int x){
	int i,y;sz[x]=1;bt(T[x],1,n,x);for(i=1;i<=17;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(la[i]!=F[x][0])y=la[i],F[y][0]=x,d[y]=d[x]+1,dfs(y),T[x]=mg(T[x],T[y]),sz[x]+=sz[y];
}
int C(int k,int l,int r,int z){
	if(l==r)return l;int md=l+r>>1;
	return z<=S[L[k]]?C(L[k],l,md,z):C(R[k],md+1,r,z-S[L[k]]);
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);int t=d[x]-d[y],i;
    for(i=0;i<=16;i++)if(t>>i&1)x=F[x][i];
    for(i=16;~i;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}
int dis(int k,int x,int y){x=C(T[k],1,n,x);y=C(T[k],1,n,y);return d[x]+d[y]-2*d[lca(x,y)];}
int main(){
	for(scanf("%d%d%d",&n,&m,&Q),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(q[t=1]=n,bl[1]=1,dfs(1);m--;){
		scanf("%d%lld",&x,&Y);y=lower_bound(q+1,q+t+1,Y)-q;to[++t]=Y-q[y-1];q[t]=q[t-1]+sz[x];bl[t]=x;
		G[t][0]=y,D[t]=D[y]+1,h[t]=h[y]+d[C(T[bl[y]],1,n,to[t])]-d[bl[y]]+1;
	}
	for(j=1;j<=16;j++)for(i=1;i<=t;i++)G[i][j]=G[G[i][j-1]][j-1];
	for(;Q--;){
		scanf("%lld%lld",&X,&Y);x=lower_bound(q+1,q+t+1,X)-q,bx=X-q[x-1];y=lower_bound(q+1,q+t+1,Y)-q,by=Y-q[y-1];
		if(D[x]<D[y])swap(x,y),swap(bx,by);o=D[x]-D[y]-1;AN=0;
		if(D[x]!=D[y]){
			for(AN+=d[C(T[bl[x]],1,n,bx)]-d[bl[x]]+1,i=16;~i;i--)if(o>>i&1)AN+=h[x]-h[G[x][i]],x=G[x][i];
			bx=to[x];x=G[x][0];
		}
		if(x==y){printf("%lld\n",AN+dis(bl[x],bx,by));continue;}
		for(AN+=d[C(T[bl[x]],1,n,bx)]-d[bl[x]]+d[C(T[bl[y]],1,n,by)]-d[bl[y]]+2,i=16;~i;i--)if(G[x][i]!=G[y][i])AN+=h[x]-h[G[x][i]]+h[y]-h[G[y][i]],x=G[x][i],y=G[y][i];
		bx=to[x];by=to[y];x=G[x][0];printf("%lld\n",AN+dis(bl[x],bx,by));
	}
}

Day1的三道题都不是很难想，T2是一眼题，T3做法也很容易看出，T1想一会也想得出。但都比较难写，T1想20min写70min调70min，T2想5min写60min调30min，T3想10min写80min调45min。总时间差不多是3H+2H+2.5H，要在5小时内AK显然是不太可能的。。不过我写炸了很多地方，调了很久，水平高的选手还是可以当场AK的。考场上想到做法就应该直接上，这种题不做就没题能做了。。

T4 序列 使用莫队算法，考虑端点移动时，统计另一端点到该点的所有区间的贡献。考虑右端点移动的情况，找到每个点$i$左边比他小的第一个数$l[i]$，那么有贡献$(i-l[i])*a[i]$，该点及其之前的点的贡献和即$(i-l[i])*a[i]+L[l[i]]$。但发现有的时候这个贡献会超出当前的区间。于是找出当前区间$[l,r]$最小的值的位置$o$，它管辖的范围一定是$[l,o]$，剩下的前缀和处理一下就可以了。找最小值可以RMQ-ST预处理后$O(1)$查找，于是时间复杂度$O(q\sqrt{n}+nlgn)$。

#include<bits/stdc++.h>
#define N 100100
using namespace std;typedef long long LL;int n,Q,i,j,t,l,r,w,o,S=300,st[N],q[N],gl[N],F[N][17];LL A,a[N],L[N],R[N],AN[N];
struct P{int l,r,id;}p[N];bool cmp(P a,P b){return st[a.l]<st[b.l]||st[a.l]==st[b.l]&&a.r<b.r;}
int qu(){w=gl[r-l+1];return a[F[l][w]]<a[F[r-(1<<w)+1][w]]?F[l][w]:F[r-(1<<w)+1][w];}
LL qr(int x){o=qu();return a[o]*(o-l+1)+L[x]-L[o];}LL ql(int x){o=qu();return a[o]*(r-o+1)+R[x]-R[o];}
int main(){
	for(scanf("%d%d",&n,&Q),i=1;i<=n;i++)scanf("%lld",&a[i]),F[i][0]=i,st[i]=(i-1)/S;
	for(i=1;i<=n;L[i]=a[i]*(i-q[t])+L[q[t]],q[++t]=i++)for(;t&&a[i]<=a[q[t]];t--);
	for(q[t=0]=n+1,i=n;i;R[i]=a[i]*(q[t]-i)+R[q[t]],q[++t]=i--)for(;t&&a[i]<=a[q[t]];t--);
	for(i=2;i<=n;i++)gl[i]=gl[i/2]+1;
	for(j=1;j<=gl[n];j++)for(i=1;i+(1<<j)-1<=n;i++)F[i][j]=a[F[i][j-1]]<a[F[i+(1<<(j-1))][j-1]]?F[i][j-1]:F[i+(1<<(j-1))][j-1];
	for(i=1;i<=Q;i++)scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
	for(sort(p+1,p+Q+1,cmp),l=i=1;i<=Q;AN[p[i].id]=A,i++){
		for(;r<p[i].r;)A+=qr(++r);for(;r>p[i].r;r--)A-=qr(r);
		for(;l<p[i].l;l++)A-=ql(l);for(;l>p[i].l;)A+=ql(--l);
	}
	for(i=1;i<=Q;i++)printf("%lld\n",AN[i]);
}

T5 矿区 先平面图转对偶图，用set做到$O(nlgn)$。然后在对偶图上从根开始DFS一遍，得到以每个节点为根的分母之和和分子之和。对于每组询问，找到询问边在对偶图上切的边，并判断是伸出去的还是伸进来的，如果是伸出去的给答案减去伸出去的值，如果是伸进来的给答案加上伸进来的值，可以证明这样是对的。

#include<bits/stdc++.h>
#define N 2422222
using namespace std;typedef long long LL;LL S,A[N],V[N],fz,fm,u;map<int,int>mp[N];
int n,m,k,i,j,x,y,t,o,w,X,Y,rt,cnt,tot,to[N],q[N],v[N],fir[N],ne[N],la[N],F[N],va[N];bool ok[N];
struct P{int x,y,z;double o;}p[N],e[N];LL operator*(P a,P b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
struct cmp{bool operator()(int a,int b){return e[a].o<e[b].o;}};set<int,cmp>s[N];set<int,cmp>::iterator it;
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;}
void dfs(int x){
	A[x]=V[x]*V[x];
	for(int i=fir[x],y;i;i=ne[i])if(!v[y=la[i]])ok[va[i]]=ok[va[i]^1]=1,v[y]=1,F[y]=x,dfs(y),A[x]+=A[y],V[x]+=V[y];
}
int main(){
	for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
	for(i=0;i<m;i++)scanf("%d%d",&x,&y),e[i*2]=P{x,y,i*2,atan2(p[y].x-p[x].x,p[y].y-p[x].y)},e[i*2+1]=P{y,x,i*2+1,atan2(p[x].x-p[y].x,p[x].y-p[y].y)};
	for(m*=2,i=0;i<m;i++)s[e[i].x].insert(i);
	for(i=0;i<m;i++)if(!v[i]){
		for(q[t=1]=j=i;;q[++t]=j=*it){
			it=s[e[j].y].upper_bound(j^1);
			if(it==s[e[j].y].end())it=s[e[j].y].begin();
			if(*it==i)break;
		}
		for(S=0,j=1;j<=t;j++)S+=p[e[q[j]].x]*p[e[q[j]].y],v[q[j]]=1;
		for(V[++cnt]=S,j=1;j<=t;j++)to[q[j]]=cnt;
		if(S<=0)rt=cnt;
	}
	for(memset(v,0,sizeof v),i=0;i<m;i++)mp[e[i].x][e[i].y]=i;
	for(v[rt]=1,V[rt]=0,i=0;i<m;i++)ins(to[i],to[i^1],i);
	for(dfs(rt);k--;printf("%lld %lld\n",fz,fm),o=fz%n){
		for(scanf("%d",&t),t=(t+o)%n+1,i=1;i<=t;i++)scanf("%d",&w),q[i]=(w+o)%n+1;
		for(q[0]=q[t],fz=fm=0,i=1;i<=t;i++){
			o=mp[q[i-1]][q[i]];X=to[o];Y=to[o^1];if(!ok[o])continue;
			if(F[X]==Y)fz+=A[X],fm+=V[X];else fz-=A[Y],fm-=V[Y];
		}
		if(fz<0)fz=-fz,fm=-fm;fm*=2;u=__gcd(fz,fm);fz/=u,fm/=u;
	}
}

T6 大数 把前缀*10的幂次和求出来，$V[i]=pw[n-i]*s[i]$。发现如果一段区间%M=0就合法。那么再做一遍前缀和，再离散化一下，就变成统计区间有多少对相同的数，直接上莫队即可。时间复杂度$O(n\sqrt{n})$。

注意$2$和$5$的时候求逆会出现问题，特判之。

#include<bits/stdc++.h>
#define N 100100
using namespace std;char s[N];int n,i,M,Q,B=600,cnt,L,R,st[N],pw[N],v[N],V[N],sz[N],zs[N];long long A,ans[N];
struct P{int l,r,id;}q[N];bool cmp(P a,P b){return st[a.l]<st[b.l]||st[a.l]==st[b.l]&&a.r<b.r;}
int main(){
	for(scanf("%d%s",&M,s+1),n=strlen(s+1),pw[0]=i=1;i<=n;i++)pw[i]=1ll*pw[i-1]*10%M,st[i]=(i-1)/B;
	 if(M==2||M==5){
	 	for(i=1;i<=n;i++)if((s[i]-'0')%M==0)sz[i]=i,zs[i]=1;
	 	for(i=1;i<=n;i++)sz[i]+=sz[i-1],zs[i]+=zs[i-1];
	 	for(scanf("%d",&Q);Q--;printf("%lld\n",sz[R]-sz[L-1]-1ll*(zs[R]-zs[L-1])*(L-1)))scanf("%d%d",&L,&R);
	 	return 0;
    }
	for(scanf("%d",&Q),i=1;i<=Q;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+Q+1,cmp);
	for(i=1;i<=n;i++)V[i]=(1ll*pw[n-i]*(s[i]-'0')+V[i-1])%M,v[i]=V[i];
	for(sort(v+1,v+n+2),cnt=unique(v+1,v+n+2)-v-1,i=0;i<=n;i++)V[i]=lower_bound(v+1,v+cnt+1,V[i])-v;
	for(L=i=1;i<=Q;ans[q[i].id]=A,i++){
		for(;R<q[i].r;A+=sz[V[R]])R++,sz[V[R-1]]++,zs[V[R]]++;for(;R>q[i].r;zs[V[R--]]--)A-=sz[V[R]],sz[V[R-1]]--;
		for(;L<q[i].l;zs[V[L++]]--)A-=zs[V[L-1]],sz[V[L-1]]--;for(;L>q[i].l;A+=zs[V[L-1]])L--,sz[V[L-1]]++,zs[V[L]]++;
	}for(i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}

嘴巴上AK辣，开始写吧

• 相关文章推荐
• 全局相关文章