jzzx训练记录

7.28

最小斯坦纳树，整体二分，树剖等

2025.07.29【提高A组】模拟赛

题面在u盘中

T1:1257. 海报

原题：P9790 [ROIR 2020] 海报 (Day 2)

算法：动态DP

首先，考虑没有修改应该怎么做。

可以想到 dp，设 dp[i][0/1/2/3] 表示当前 i所在的段的长度，转移很好想

dp[i][0]=max(dp[i-1][0/1/2/3])

dp[i][j]=dp[i-1][j-1]+a[i]

但注意这是一个环，最后几位与开头几位有影响，同时，注意到

n,1,2,3

这几位中只要有一个不选就是合法方案，所以考虑将数组复制一遍，做

4

遍 dp，范围分别是

[1,n-1]

[2,n]

[3,n+1]

[4,n+2]

，最后取 max。

现在有修改，用ddp的思路，将转移写成矩阵，所以有

矩阵为

max,+

矩阵

\begin{bmatrix} dp[i-1][0] & dp[i-1][1] & dp[i-1][2] & dp[i-1][3] \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \end{bmatrix} \otimes \begin{bmatrix} 0 & a[i] & -inf & -inf \\ 0 & -inf & a[i] & -inf \\ 0 & -inf & -inf & a[i] \\ 0 & -inf & -inf & -inf \end{bmatrix}= \begin{bmatrix} dp[i][0] & dp[i][1] & dp[i][2] & dp[i][3] \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}

在加上快速改值，用线段树维护，一样跑四遍，略微卡常

代码:

CPP

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=4e4+10,inf=1e17;
int n,m;
int a[N<<1];
struct Matrix
{
	int a[4][4];
	Matrix()
	{
		memset(a,0,sizeof(a));
	}
	friend Matrix operator *(Matrix a,Matrix b)
	{
		Matrix c;
		c.a[0][0]=max(c.a[0][0],a.a[0][0]+b.a[0][0]);
		c.a[0][0]=max(c.a[0][0],a.a[0][1]+b.a[1][0]);
		c.a[0][0]=max(c.a[0][0],a.a[0][2]+b.a[2][0]);
		c.a[0][0]=max(c.a[0][0],a.a[0][3]+b.a[3][0]);
		c.a[0][1]=max(c.a[0][1],a.a[0][0]+b.a[0][1]);
		c.a[0][1]=max(c.a[0][1],a.a[0][1]+b.a[1][1]);
		c.a[0][1]=max(c.a[0][1],a.a[0][2]+b.a[2][1]);
		c.a[0][1]=max(c.a[0][1],a.a[0][3]+b.a[3][1]);
		c.a[0][2]=max(c.a[0][2],a.a[0][0]+b.a[0][2]);
		c.a[0][2]=max(c.a[0][2],a.a[0][1]+b.a[1][2]);
		c.a[0][2]=max(c.a[0][2],a.a[0][2]+b.a[2][2]);
		c.a[0][2]=max(c.a[0][2],a.a[0][3]+b.a[3][2]);
		c.a[0][3]=max(c.a[0][3],a.a[0][0]+b.a[0][3]);
		c.a[0][3]=max(c.a[0][3],a.a[0][1]+b.a[1][3]);
		c.a[0][3]=max(c.a[0][3],a.a[0][2]+b.a[2][3]);
		c.a[0][3]=max(c.a[0][3],a.a[0][3]+b.a[3][3]);
		c.a[1][0]=max(c.a[1][0],a.a[1][0]+b.a[0][0]);
		c.a[1][0]=max(c.a[1][0],a.a[1][1]+b.a[1][0]);
		c.a[1][0]=max(c.a[1][0],a.a[1][2]+b.a[2][0]);
		c.a[1][0]=max(c.a[1][0],a.a[1][3]+b.a[3][0]);
		c.a[1][1]=max(c.a[1][1],a.a[1][0]+b.a[0][1]);
		c.a[1][1]=max(c.a[1][1],a.a[1][1]+b.a[1][1]);
		c.a[1][1]=max(c.a[1][1],a.a[1][2]+b.a[2][1]);
		c.a[1][1]=max(c.a[1][1],a.a[1][3]+b.a[3][1]);
		c.a[1][2]=max(c.a[1][2],a.a[1][0]+b.a[0][2]);
		c.a[1][2]=max(c.a[1][2],a.a[1][1]+b.a[1][2]);
		c.a[1][2]=max(c.a[1][2],a.a[1][2]+b.a[2][2]);
		c.a[1][2]=max(c.a[1][2],a.a[1][3]+b.a[3][2]);
		c.a[1][3]=max(c.a[1][3],a.a[1][0]+b.a[0][3]);
		c.a[1][3]=max(c.a[1][3],a.a[1][1]+b.a[1][3]);
		c.a[1][3]=max(c.a[1][3],a.a[1][2]+b.a[2][3]);
		c.a[1][3]=max(c.a[1][3],a.a[1][3]+b.a[3][3]);
		c.a[2][0]=max(c.a[2][0],a.a[2][0]+b.a[0][0]);
		c.a[2][0]=max(c.a[2][0],a.a[2][1]+b.a[1][0]);
		c.a[2][0]=max(c.a[2][0],a.a[2][2]+b.a[2][0]);
		c.a[2][0]=max(c.a[2][0],a.a[2][3]+b.a[3][0]);
		c.a[2][1]=max(c.a[2][1],a.a[2][0]+b.a[0][1]);
		c.a[2][1]=max(c.a[2][1],a.a[2][1]+b.a[1][1]);
		c.a[2][1]=max(c.a[2][1],a.a[2][2]+b.a[2][1]);
		c.a[2][1]=max(c.a[2][1],a.a[2][3]+b.a[3][1]);
		c.a[2][2]=max(c.a[2][2],a.a[2][0]+b.a[0][2]);
		c.a[2][2]=max(c.a[2][2],a.a[2][1]+b.a[1][2]);
		c.a[2][2]=max(c.a[2][2],a.a[2][2]+b.a[2][2]);
		c.a[2][2]=max(c.a[2][2],a.a[2][3]+b.a[3][2]);
		c.a[2][3]=max(c.a[2][3],a.a[2][0]+b.a[0][3]);
		c.a[2][3]=max(c.a[2][3],a.a[2][1]+b.a[1][3]);
		c.a[2][3]=max(c.a[2][3],a.a[2][2]+b.a[2][3]);
		c.a[2][3]=max(c.a[2][3],a.a[2][3]+b.a[3][3]);
		c.a[3][0]=max(c.a[3][0],a.a[3][0]+b.a[0][0]);
		c.a[3][0]=max(c.a[3][0],a.a[3][1]+b.a[1][0]);
		c.a[3][0]=max(c.a[3][0],a.a[3][2]+b.a[2][0]);
		c.a[3][0]=max(c.a[3][0],a.a[3][3]+b.a[3][0]);
		c.a[3][1]=max(c.a[3][1],a.a[3][0]+b.a[0][1]);
		c.a[3][1]=max(c.a[3][1],a.a[3][1]+b.a[1][1]);
		c.a[3][1]=max(c.a[3][1],a.a[3][2]+b.a[2][1]);
		c.a[3][1]=max(c.a[3][1],a.a[3][3]+b.a[3][1]);
		c.a[3][2]=max(c.a[3][2],a.a[3][0]+b.a[0][2]);
		c.a[3][2]=max(c.a[3][2],a.a[3][1]+b.a[1][2]);
		c.a[3][2]=max(c.a[3][2],a.a[3][2]+b.a[2][2]);
		c.a[3][2]=max(c.a[3][2],a.a[3][3]+b.a[3][2]);
		c.a[3][3]=max(c.a[3][3],a.a[3][0]+b.a[0][3]);
		c.a[3][3]=max(c.a[3][3],a.a[3][1]+b.a[1][3]);
		c.a[3][3]=max(c.a[3][3],a.a[3][2]+b.a[2][3]);
		c.a[3][3]=max(c.a[3][3],a.a[3][3]+b.a[3][3]);
		return c;
	}
};
struct segment_tree
{
	int l,r;
	Matrix val;
}t[N<<3];
void push_up(int u)
{
	t[u].val=t[u<<1].val*t[u<<1|1].val;
}
void build(int u,int l,int r)
{
	t[u].l=l;
	t[u].r=r;
	if(l==r)
	{
		t[u].val.a[0][1]=t[u].val.a[1][2]=t[u].val.a[2][3]=a[l];
		return ;
	}
	int mid=(t[u].l+t[u].r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}
void update(int u,int x,int val)
{
	if(t[u].l==t[u].r&&t[u].l==x)
	{
		t[u].val.a[0][1]=t[u].val.a[1][2]=t[u].val.a[2][3]=val;
		return ;
	}
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)
		update(u<<1,x,val);
	else if(x>mid)
		update(u<<1|1,x,val);
	push_up(u);
}
Matrix query(int u,int l,int r)
{
	if(l<=t[u].l&&t[u].r<=r)
		return t[u].val;
	int mid=(t[u].l+t[u].r)>>1;
	Matrix res;
	if(l<=mid)
		res=query(u<<1,l,r);
	if(r>mid)
		res=res*query(u<<1|1,l,r);
	return res;
}
Matrix tmp;
int get_ans()
{
	Matrix res=query(1,1,n-1);
	res=tmp*res;
	int ans=0;
	for(int i=0;i<4;i++)
		ans=max(ans,res.a[0][i]);
	res=query(1,2,n);
	res=tmp*res;
	for(int i=0;i<4;i++)
		ans=max(ans,res.a[0][i]);
	res=query(1,3,n+1);
	res=tmp*res;
	for(int i=0;i<4;i++)
		ans=max(ans,res.a[0][i]);
	res=query(1,4,n+2);
	res=tmp*res;
	for(int i=0;i<4;i++)
		ans=max(ans,res.a[0][i]);
	return ans;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<4;i++)	
		for(int j=0;j<4;j++)
			tmp.a[i][j]=-inf;
	tmp.a[0][0]=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],a[i+n]=a[i];
	build(1,1,n<<1);
	cin>>m;
	cout<<get_ans()<<endl;
	for(int i=1,p,q;i<=m;i++)
	{
		cin>>p>>q;
		update(1,p,q);
		update(1,p+n,q);
		cout<<get_ans()<<endl;
	}
	return 0;
}

T2:1256. 概率充电器(charger)

原题：P4284 [SHOI2014] 概率充电器

算法：树形DP

题解

代码:

CPP

#include <bits/stdc++.h>
using namespace std;
#define double long double
const int N=5e5+10;
int n;
int h[N],to[N<<1],ne[N<<1],idx;
double w[N<<1];
double val[N];
double dp[N];
void add(int u,int v,double c)
{
	to[++idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
void dfs1(int u,int f)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs1(v,u);
		dp[u]+=(1-dp[u])*dp[v]*w[i];
	}
}
void dfs2(int u,int f)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		if(1-dp[v]*w[i]==0)
		{
			dfs2(v,u);
			continue;
		}
		double las=(dp[u]-dp[v]*w[i])/(1-dp[v]*w[i]);
		dp[v]+=(1-dp[v])*las*w[i];
		dfs2(v,u);
	}
}
signed main()
{
	freopen("charger.in","r",stdin);
	freopen("charger.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1,u,v,c;i<n;i++)
	{
		cin>>u>>v>>c;
		add(u,v,1.0*c/100.0);
		add(v,u,1.0*c/100.0);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>val[i];
		val[i]/=100.0;
		dp[i]=val[i];
	}
	dfs1(1,0);
	dfs2(1,0);
	double ans=0;
	for(int i=1;i<=n;i++)
		ans+=dp[i];
	cout<<fixed<<setprecision(6)<<ans;
	return 0;
}

T3：1262. 玉米田+

原题OJ已死，但有题解。

这是轮廓线DP的题。

轮廓线DP也是状压DP，但是轮廓线DP记录的状态是这样的：

红色的是状压记录的状态，这样就可以通过上面和左边的状态确定当前点的状态。

题解

代码:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=21,M=120,mod=1e8;
int n,m;
vector<int> S;
bool a[M+1][N+1];
bool check(int num)
{
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(i>0)
		{
			if((num>>i&1)&&(num>>(i-1)&1))
			{
				if(cnt==1)
					return 0;
				cnt++;
			}
		}
	}
	return 1;
}
int id[1<<N],cnt;
int dp[2][130000];
signed main()
{
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=0;i<(1<<n);i++)
		if(check(i))
			S.emplace_back(i),id[i]=cnt++;
	dp[0][id[0]]=1;
	bool op=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++,op^=1)
		{
			for(auto T:S)
				dp[op][id[T]]=0;
			for(auto T:S)
			{
				bool up=(T>>(j-1))&1,lef=(j==1)?0:(T>>(j-2))&1;
				if(i==1&&up)
					continue;
				int nw=T^(1<<(j-1));

				if(up)
				{
					dp[op][id[nw]]+=dp[op^1][id[T]];
					if(dp[op][id[nw]]>=mod)
						dp[op][id[nw]]-=mod;
					continue;
				}
				else if(lef||!a[i][j])
				{
					dp[op][id[T]]+=dp[op^1][id[T]];
					if(dp[op][id[T]]>=mod)
						dp[op][id[T]]-=mod;
					continue;
				}
				dp[op][id[nw]]+=dp[op^1][id[T]];
				if(dp[op][id[nw]]>=mod)
					dp[op][id[nw]]-=mod;
				dp[op][id[T]]+=dp[op^1][id[T]];
				if(dp[op][id[T]]>=mod)
					dp[op][id[T]]-=mod;
			}
		}
	}
	int ans=0;
	for(auto i:S)
	{
		ans+=dp[op^1][id[i]];
		if(ans>mod)
			ans-=mod;
	}
	cout<<ans;
	return 0;
}

T4：1259. 能源网格(power)

原题：P10644 [NordicOI 2022] 能源网格 Power Grid

2025.07.30【提高A组】模拟赛

T1:原题：C题

算法：数据结构。

首先，将 ABCD 转化成 0123，操作1就变为加1模4。

考虑操作二。因为一段内要求单调递增，所以当有相邻两个前面比后面大就一定要插板分割。所以转化为了

k-1

个板，减去必须插入的板数后，其他板随便插的方案数，直接乘组合数即可。

用分块维护，考虑模数很小，直接预处理出所有的加后的状态，散块暴力重构

代码:

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10,len=350,M=290,mod=998244353;
int n,m;
int a[N];
int L[M],R[M],bel[N],laz[M];
struct block
{
	int cnt,l_val,r_val;
}b[4][M];
void build(int i)
{
	laz[i]=0;
	for(int k=0;k<4;k++)
	{
		b[k][i].cnt=0;
		for(int j=L[i]+1;j<=R[i];j++)
			if((a[j]+k)%4<=(a[j-1]+k)%4)
				b[k][i].cnt++;
//		cout<<b[k][i].cnt<<endl;
		b[k][i].l_val=(a[L[i]]+k)%4;
		b[k][i].r_val=(a[R[i]]+k)%4;
	}
}
void update(int l,int r)
{
	if(bel[l]==bel[r])
	{
		for(int i=L[bel[l]];i<=R[bel[l]];i++)
			a[i]=(a[i]+laz[bel[l]])%4;
		for(int i=l;i<=r;i++)
			a[i]++,a[i]%=4;
		build(bel[l]);
		return ;
	}
	for(int i=L[bel[l]];i<=R[bel[l]];i++)
		a[i]=(a[i]+laz[bel[l]])%4;
	for(int i=l;i<=R[bel[l]];i++)
		a[i]++,a[i]%=4;
	build(bel[l]);
	for(int i=L[bel[r]];i<=R[bel[r]];i++)
		a[i]=(a[i]+laz[bel[r]])%4;
	for(int i=L[bel[r]];i<=r;i++)
		a[i]++,a[i]%=4;
	build(bel[r]);
	for(int i=bel[l]+1;i<=bel[r]-1;i++)
	{
		laz[i]++;
		laz[i]%=4;
	}
}
int query(int l,int r)
{
	if(bel[l]==bel[r])
	{
		int cnt=0;
		for(int i=l+1;i<=r;i++)
			if((a[i-1]+laz[bel[l]])%4>=(a[i]+laz[bel[l]])%4)
				cnt++;
		return cnt;
	}
	int cnt=0;
	for(int i=l+1;i<=R[bel[l]];i++)
		if((a[i-1]+laz[bel[l]])%4>=(a[i]+laz[bel[l]])%4)
			cnt++;
	for(int i=L[bel[r]]+1;i<=r;i++)
		if((a[i-1]+laz[bel[r]])%4>=(a[i]+laz[bel[r]])%4)
			cnt++;
	for(int i=bel[l]+1;i<=bel[r]-1;i++)
	{
		cnt+=b[laz[i]][i].cnt;
//		if(i>bel[l]+1)
			cnt+=(b[laz[i]][i].l_val<=b[laz[i-1]][i-1].r_val);
	}
//	cnt+=(b[laz[bel[l]+1]][bel[l]+1].l_val<=(a[R[bel[l]]]+laz[bel[l]])%4);
	cnt+=(b[laz[bel[r]-1]][bel[r]-1].r_val>=(a[L[bel[r]]]+laz[bel[r]])%4);
	return cnt;
}
int fac[N],infac[N];
int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int C(int n,int m)
{
	if(m>n)
		return 0;
	return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
signed main()
{
	freopen("quiz.in","r",stdin);
	freopen("quiz.out","w",stdout);
	cin>>n>>m;
	string s;
	cin>>s;
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	infac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=1;i--)
		infac[i]=infac[i+1]*(i+1)%mod;
	s=" "+s;
	for(int i=1;i<=n;i++)
		a[i]=s[i]-'A';
//	for(int i=1;i<=n;i++)
//		cout<<a[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=n;i++)
		bel[i]=(i-1)/len+1;
	for(int i=1;i<=bel[n];i++)
		L[i]=(i-1)*len+1,R[i]=i*len;
	R[bel[n]]=n;
	for(int i=1;i<=bel[n];i++)
		build(i);
	for(int i=1,op,l,r,k;i<=m;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>l>>r;
			update(l,r);
		}
		else if(op==2)
		{
			cin>>l>>r>>k;
			k--;
			int val=query(l,r);
//			cout<<val<<endl;
			if(k<val||k>(r-l))
				cout<<0<<endl;
			else
				cout<<C(r-l-val,k-val)<<endl;
		}
//		for(int j=1;j<=n;j++)
//			cout<<(a[j]+laz[bel[j]])%4<<" ";
//		cout<<endl;
	}
	return 0;
}

T2：1268. 酱料女王(queen)

原题：D. Dark LaTeX vs. Light LaTeX

题解

2025.08.01【提高A组】模拟赛

T1:1274. 【NOIP2017提高A组模拟9.14】生命之树

看到维护后代集合，直接暴力合并复杂度错误，所以考虑 dsu on tree。

两个字符串的最长公共前缀可以用trie树维护。现在考虑异或，发现可以拆位考虑，所以将乘法换成加法，将字符串对应的trie树上的每一个节点都储存二进制位信息，然后加起来，就和乘上公共前缀的效果一样。

代码:

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10,M=5e5+10;
int n;
int val[N];
struct Trie
{
	int ch[26];
	int siz[20][2];
}trie[M];
int h[N],to[N<<1],ne[N<<1],idx;
string s[N];
void add(int u,int v)
{
	to[++idx]=v;
	ne[idx]=h[u];
	h[u]=idx;
}
int ans[N];
int siz[N],son[N];
int cnt;
int pw[20];
void insert(int u)
{
	int p=0;
	for(int i=0;i<(signed)s[u].size();i++)
	{
		int c=s[u][i]-'a';
		if(!trie[p].ch[c])
			trie[p].ch[c]=++cnt;
		p=trie[p].ch[c];
		for(int j=0;j<20;j++)
			trie[p].siz[j][(val[u]>>j)&1]++;
	}
}
int query(int u)
{
	int p=0;
	int res=0;
	for(int i=0;i<(signed)s[u].size();i++)
	{
		int c=s[u][i]-'a';
		if(!trie[p].ch[c])
			return res;
		p=trie[p].ch[c];
		for(int j=0;j<20;j++)
			res+=pw[j]*trie[p].siz[j][((val[u]>>j)&1)^1];
	}
	return res;
}
void init()
{
	for(int i=0;i<=cnt;i++)
	{
		for(int j=0;j<26;j++)
			trie[i].ch[j]=0;
		for(int j=0;j<20;j++)
			trie[i].siz[j][0]=trie[i].siz[j][1]=0;
	}
	cnt=0;
}
void dfs1(int u,int f)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
}
void dfs3(int u,int f,int &ans)
{
	ans+=query(u);
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs3(v,u,ans);
	}
}
void dfs4(int u,int f)
{
	insert(u);
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs4(v,u);
	}
}
void dfs2(int u,int f,bool k)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f||v==son[u])
			continue;
		dfs2(v,u,0);
		ans[u]+=ans[v];
	}
	if(son[u])
		dfs2(son[u],u,1),ans[u]+=ans[son[u]];
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f||v==son[u])
			continue;
		dfs3(v,u,ans[u]);
		dfs4(v,u);
	}
	ans[u]+=query(u);
	if(!k)
		init();
	else
		insert(u);
}
signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	pw[0]=1;
	for(int i=1;i<20;i++)
		pw[i]=pw[i-1]*2;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>val[i];
	for(int i=1;i<=n;i++)
		cin>>s[i],siz[i]=s[i].size()+1;
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
	return 0;
}

2025.08.03【提高A组】模拟赛

T1：1284. 管道监控

原题：P11179 [ROIR 2018] 管道监控 (Day1)

这个DP的状态较为奇怪，设

dp_{i,j}

表示第

i

个点，有一条向上覆盖了

j

个点的链的最小代价，最后答案就是

dp_{1,0}

。

考虑如何转移，当一个新子树加入时，有

dp_{u,max(j,k)} \ = \ min(dp_{v,k+1}+tmpdp_{u,j}) dp_{u,k}=min(dp_{u,k},dp_{u,j}+trie_{k-j+1})

其中，

tmpdp

表示合并子树之前的

dp_u

的值，

trie

表示在 trie 树上的字符串对应的代价。

同时，因为我们是从下到上合并，所以字符串先反转再插入 trie 树这样 trie 树就是从上到下匹配了

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=500+10,M=1e5+10,L=1e6+10,inf=1e18;
int n,m,t;
int h[N],to[N<<1],ne[N<<1],idx;
char w[N<<1];
struct Trie
{
	int ch[26];
	int w;
	int id;
	bool en;
}trie[L];
int cnt=1;
void insert(string s,int w,int id)
{
	int p=1;
	for(int i=0;i<(signed)s.size();i++)
	{
		int c=s[i]-'a';
		if(!trie[p].ch[c])
			trie[p].ch[c]=++cnt;
		p=trie[p].ch[c];
	}
	if(trie[p].en)
	{
		if(trie[p].w>w)
		{
			trie[p].w=w;
			trie[p].id=id;
		}
	}
	else
	{
		trie[p].en=1;
		trie[p].w=w;
		trie[p].id=id;
	}
}
void add(int u,int v,char c)
{
	to[++idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
pair<int,int> fa[N];
vector<pair<int,int> > id[N][N],tmp_id[N];
int dp[N][N];
int dep[N];
int tmp_dp[N];
void dfs(int u,pair<int,int> f)
{
	fa[u]=f;
	dep[u]=dep[f.first]+1;
	for(int i=1;i<=n;i++)
		dp[u][i]=inf;
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f.first)
			continue;
		dfs(v,make_pair(u,i));
		for(int j=0;j<=n;j++)
			tmp_id[j]=id[u][j],tmp_dp[j]=dp[u][j],dp[u][j]=inf,id[u][j].clear();
		for(int j=0;j<=dep[u];j++)
			for(int k=0;k<=dep[u];k++)
				dp[u][max(j,k)]=min(dp[u][max(j,k)],dp[v][k+1]+tmp_dp[j]);
		for(int j=0;j<=dep[u];j++)
		{
			for(int k=0;k<=dep[u];k++)
			{
				if(dp[u][max(j,k)]<inf&&dp[u][max(j,k)]==dp[v][k+1]+tmp_dp[j]&&id[u][max(j,k)].empty())
				{
					id[u][max(j,k)]=tmp_id[j];
					id[u][max(j,k)].insert(id[u][max(j,k)].end(),id[v][k+1].begin(),id[v][k+1].end());
				}
			}
		}
	}
	for(int de=0,tmp_u=u,tmp_de=0,tmp_p=1;tmp_u&&tmp_p;de++,tmp_p=trie[tmp_p].ch[w[fa[tmp_u].second]-'a'],tmp_u=fa[tmp_u].first)
	{
		if(trie[tmp_p].en)
		{
			if(dp[u][de]>trie[tmp_p].w+dp[u][tmp_de])
			{
				dp[u][de]=trie[tmp_p].w+dp[u][tmp_de];
				id[u][de]=id[u][tmp_de];
				id[u][de].emplace_back(make_pair(u,trie[tmp_p].id));
			}
		}
		if(dp[u][de]<dp[u][tmp_de])
			tmp_de=de;
	}
}
signed main()
{
	cin>>n>>m>>t;
	char c;
	for(int i=2,p;i<=n;i++)
	{
		cin>>p>>c;
		add(i,p,c);
		add(p,i,c);
	}
	string s[M];
	for(int i=1,w;i<=m;i++)
	{
		cin>>w>>s[i];
		reverse(s[i].begin(),s[i].end());
		insert(s[i],w,i);
	}
	dep[0]=-1;
	dfs(1,make_pair(0,0));
	if(t==0)
	{
		if(dp[1][0]>=inf)
			cout<<-1<<endl;
		else
			cout<<dp[1][0]<<endl;
	}
	else
	{
		if(dp[1][0]>=inf)
			cout<<-1<<endl;
		else
		{	
			cout<<dp[1][0]<<endl;
			cout<<id[1][0].size()<<endl;
			for(auto i:id[1][0])
			{
				int k=i.first;
				for(int j=1;j<=(signed)s[i.second].size();j++)
					k=fa[k].first;
				cout<<k<<" "<<i.first<<" "<<i.second<<endl;
			}
		}
	}
	return 0;
}

T2: 1285. 哩哩哩啦哩啦

首先考虑求出了

k

级儿子然后怎么求出

l,r

。

我们可以用线段树维护对于每一个

l

，它们最小的

r

是多少。然后，在每一次加入一个新的

k

级儿子时，将

las+1

到

x

这一段赋值为

x

，然后在每一个限制的

k

级儿子遍历完后将最后一个点到

n

全部赋值为 inf，这样保证了不会选到后面去,最后遍历每一个

l

看最小的

l,r

。

现在的问题是如何快速求出树上

k

级儿子。我们考虑先将问题去重。当一个大问题包含一个小问题时，大问题肯定没有作用，因为满足小问题的答案一定满足大问题。去重后，每一个点只被一个询问包含。

k

级儿子可以用 dsu on tree 来做，对于每一个 dep，都维护一个 set 存储每深度是这个的点，然后就是正常合并。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=2e5+10,inf=1e18;
int n,m;
int h[N],to[N],ne[N],idx;
int x[N],k[N];
vector<int> q[N];
void add(int u,int v)
{
	to[++idx]=v;
	ne[idx]=h[u];
	h[u]=idx;
}
int siz[N],son[N],dep[N],dfn[N],time_stamp,seq[N];
void dfs1(int u,int d)
{
	siz[u]=1;
	dep[u]=d;
	dfn[u]=++time_stamp;
	seq[dfn[u]]=u;
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		dfs1(v,d+1);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])
			son[u]=v;
	}
}
set<int> s[N],s2[N];
struct segment_tree
{
	int l,r,maxx,laz;
}t[N<<2];
void build(int u,int l,int r)
{
	t[u].l=l;
	t[u].r=r;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void push_up(int u)
{
	t[u].maxx=max(t[u<<1].maxx,t[u<<1|1].maxx);
}
void push_down(int u)
{
	if(!t[u].laz)
		return ;
	t[u<<1].laz=max(t[u<<1].laz,t[u].laz);
	t[u<<1|1].laz=max(t[u<<1|1].laz,t[u].laz);
	t[u<<1].maxx=max(t[u].laz,t[u<<1].maxx);
	t[u<<1|1].maxx=max(t[u<<1|1].maxx,t[u].laz);
	t[u].laz=0;
}
void update(int u,int l,int r,int x)
{
	if(l<=t[u].l&&t[u].r<=r)
	{
		t[u].maxx=max(t[u].maxx,x);
		t[u].laz=max(t[u].laz,x);
		return ;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(l<=mid)
		update(u<<1,l,r,x);
	if(r>mid)
		update(u<<1|1,l,r,x);
	push_up(u);
}
int query(int u,int l,int r)
{
	if(l<=t[u].l&&t[u].r<=r)
		return t[u].maxx;
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1,maxx=0;
	if(l<=mid)
		maxx=max(maxx,query(u<<1,l,r));
	if(r>mid)
		maxx=max(maxx,query(u<<1|1,l,r));
	return maxx;
}
int max_dep;
void dfs2(int u,bool keep)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==son[u])
			continue;
		dfs2(v,0);
	}
	if(son[u])
		dfs2(son[u],1);
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==son[u])
			continue;
		for(int j=dfn[v];j<=dfn[v]+siz[v]-1;j++)
			s[dep[seq[j]]].insert(seq[j]),max_dep=max(max_dep,dep[seq[j]]);
	}
	s[dep[u]].insert(u);
	max_dep=max(max_dep,dep[u]);
	for(auto i:q[u])
	{
		if(s2[dep[u]+i].size())
			if(s2[dep[u]+i].lower_bound(dfn[u])!=s2[dep[u]+i].end())
				if((*s2[dep[u]+i].lower_bound(dfn[u]))<=dfn[u]+siz[u]-1)
					continue;
		s2[dep[u]+i].insert(dfn[u]);
		vector<int> id;
		for(auto j:s[dep[u]+i])
			id.emplace_back(j);
		sort(id.begin(),id.end());
		int las=0;
		for(auto j:id)
			update(1,las+1,j,j),las=j;
		update(1,las+1,n,inf);
	}
	if(!keep)
	{
		for(int i=dep[u];i<=max_dep;i++)
			s[i].clear();
		max_dep=0;
	}
}
signed main()
{
	freopen("lirililarila.in","r",stdin);
	freopen("lirililarila.out","w",stdout);
	cin>>n;
	build(1,1,n);
	for(int i=2,p;i<=n;i++)
	{
		cin>>p;
		add(p,i);
	}
	dfs1(1,1);
	cin>>m;
	for(int i=1;i<=m;i++)
		cin>>x[i]>>k[i];
	for(int i=1;i<=m;i++)
		q[x[i]].emplace_back(k[i]);
	dfs2(1,1);
	int minn=inf;
	pair<int,int> id=make_pair(0,0);
	for(int i=1;i<=n;i++)
	{
		int r=query(1,i,i);
		if(r-i+1<minn)
		{
			minn=r-i+1;
			id=make_pair(i,r);
		}
	}
	cout<<id.first<<" "<<id.second;
	return 0;
}

T3:1286. 颜色翻转（color）

原题：P3179 [HAOI2015] 数组游戏

先回顾一下

SG

函数的定义以及

SG

定理。

SG

函数：表示当前局面的胜负状态，0 是必败，其余是必胜。计算定义是后继状态的

mex

SG

定理：一个游戏的

SG

函数等于所有子游戏的

SG

函数的异或和。

其他参见题解

2025.08.05【提高A组】模拟赛

【GDOI2017 day2】小学生语文题

原题：GDOI2017 D2T3

算法：DP

首先，这道题可以倒着DP，因为后面已经匹配好后不会影响答案，所以直接倒着DP

现在考虑如何模拟在前面插入的操作。我们可以将后面的一些字符抽出来，放在一个地方，然后要匹配时从这个地方找

设

dp[i][j]

表示字符串

s

中

[i,n]

个字符与字符串

t

中

[j,n]

的字符相匹配，这种匹配可以长度不相等，因为会从

t

中抽出一些字符。

转移：

dp_{i,j} =\begin{cases} dp_{i+1,j+1} [s_i==t_j] \\ dp_{i+1,j} [在抽出来的数中找到了一个可以匹配的] \\ dp_{i,j+1} [将这一个数抽出来了] \end{cases}

答案就是

dp_{1,1}

现在考虑如何转移方案，我们记录一个数组

id_{i,j}

表示当前状态是怎么转移过来的，只有一种情况数不会被抽出来，打赏标记。从后向前遍历，当这个数有标记并且不相等，这个数一定是新插入的数匹配的，所以就从栈里取出对应的数，最后处理因为插入导致的位置的变化。

代码：

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=2000+10;
int inf;
int dp[N][N];
pair<int,int> id[N][N];
int sum1[N][26];
int sum2[N][26];
string s,t;
bool flg[N];
vector<int> stk[26];
vector<pair<int,int> > ans;
void init()
{
#define m(a) memset(a,0,sizeof(a))
	m(id),m(sum1),m(sum2),m(flg);
	memset(dp,63,sizeof(dp));
	inf=dp[0][0];
	for(int i=0;i<26;i++)
		stk[i].clear();
	ans.clear();
#undef m
}
void solve()
{
	init();
	cin>>s>>t;
	int n=s.size();
	s=" "+s;
	t=" "+t;
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<26;j++)
		{
			sum1[i][j]+=sum1[i+1][j];
			sum2[i][j]+=sum2[i+1][j];
		}
		sum1[i][s[i]-'a']++;
		sum2[i][t[i]-'a']++;
	}
	for(int i=1;i<=n+1;i++)
		dp[n+1][i]=n-i+1;
	for(int i=n;i>=1;i--)
	{
		for(int j=n;j>=1;j--)
		{
			if(dp[i+1][j]!=inf&&sum2[j][s[i]-'a']-sum1[i+1][s[i]-'a']>0&&dp[i][j]>dp[i+1][j])
			{
				dp[i][j]=dp[i+1][j];
				id[i][j]=make_pair(i+1,j);
			}
			if(dp[i+1][j+1]!=inf&&s[i]==t[j]&&dp[i][j]>dp[i+1][j+1])
			{
				dp[i][j]=dp[i+1][j+1];
				id[i][j]=make_pair(i+1,j+1);
			}
			if(dp[i][j+1]!=inf&&dp[i][j]>dp[i][j+1]+1)
			{
				dp[i][j]=dp[i][j+1]+1;
				id[i][j]=make_pair(i,j+1);
			}
		}
	}
	cout<<dp[1][1]<<endl;
	int x=1,y=1;
	while(x!=n+1)
	{
		while(id[x][y].first==x)
			y=id[x][y].second;
		if(y!=id[x][y].second)
			flg[y]=1,y++;
		x++;
	}
	for(int i=1;i<=n;i++)
		if(!flg[i])
			stk[t[i]-'a'].emplace_back(i);
	int j=n;
	for(int i=n;i>=1&&j>=1;i--)
	{
		if(flg[i])
		{
			while(s[j]!=t[i])
			{
				ans.emplace_back(make_pair(stk[s[j]-'a'].back(),i+1));
				stk[s[j]-'a'].pop_back();
				j--;
			}
			j--;
		}
	}
	for(int i=j;i>=1;i--)
	{
		ans.emplace_back(make_pair(stk[s[i]-'a'].back(),1));
		stk[s[i]-'a'].pop_back();
	}
	for(int i=0;i<(signed)ans.size();i++)
	{
		for(int j=i+1;j<(signed)ans.size();j++)
		{
			if(ans[j].first<=ans[i].first&&ans[i].second<=ans[j].first)
				ans[j].first++;
			if(ans[j].second<ans[i].first&&ans[i].second<ans[j].second)
				ans[j].second++;
		}
	}
	for(auto i:ans)
		cout<<i.first<<" "<<i.second<<endl;
}
signed main()
{
	freopen("chinese.in","r",stdin);
	freopen("chinese.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

T2：1297. 前往大都会

原题：P10652 [ROI 2017] 前往大都会 (Day 1)

T3:1295. 志愿者招募

原题: P3980 [NOI2008] 志愿者招募

2025.08.06【提高A组】模拟赛

T1:1303. 凡喵识图

抽象题。因为有三个不同，所以将 64 位数拆成 4 个 16 位数，这样答案与枚举的这个数一定有一个是相同的，枚举哪一个是相同的，暴力判断，注意去重。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=150000+10;
int n;
unsigned long long a[N];
vector<int> mp[4][(1<<16)+10];
const int num=1<<16;
int vst[N];
signed main()
{
	freopen("hashing.in","r",stdin);
	freopen("hashing.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		int ans=0;
		unsigned long long tmp=a[i];
		for(int l=0;l<4;l++)
		{
			int id=tmp%num;
			tmp/=num;
			if(mp[l][id].size())
			{
				for(auto j:mp[l][id])
				{
					if(vst[j]==i)
						continue;
					vst[j]=i;
					if(__builtin_popcountll(a[i]^a[j])==3)
						ans++;
				}
			}
			mp[l][id].emplace_back(i);
		}
		cout<<ans<<endl;
	}
	return 0;
}

T2:1308. 战争游戏

首先，每个点都有固定的答案贡献为

n-1

。然后发现一个强联通分量里的点互相不造成贡献，所以考虑圆方树，所有割点的答案都要加上经过这一个点的路径个数，只要统计出了子树内圆点的个数即可。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=5e4+10,M=1e5+10;
int n,m;
int h1[N],to1[M<<1],ne1[M<<1],idx1;
int h[N<<1],to[N<<2],ne[N<<2],idx;
void add1(int u,int v)
{
	to1[++idx1]=v;
	ne1[idx1]=h1[u];
	h1[u]=idx1;
}
void add(int u,int v)
{
	to[++idx]=v;
	ne[idx]=h[u];
	h[u]=idx;
}
int dfn[N],low[N],time_stamp;
bool gd[N<<1];
stack<int> stk;
int id;
void tarjin(int u)
{
	dfn[u]=low[u]=++time_stamp;
	stk.emplace(u);
	for(int i=h1[u];i;i=ne1[i])
	{
		int v=to1[i];
		if(!dfn[v])
		{
			tarjin(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				gd[u]=1;
				int cur=0;
				id++;
				do{
					cur=stk.top();
					stk.pop();
					add(cur,id);
					add(id,cur);
				}while(cur!=v);
				add(id,u);
				add(u,id);
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}
int siz[N<<1];
void dfs(int u,int f)
{
	siz[u]=(u<=n);
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
int ans[N];
void dfs2(int u,int f)
{
	if(u<=n&&gd[u])
	{
		for(int i=h[u];i;i=ne[i])
		{
			int v=to[i];
			if(v==f)
				continue;
			ans[u]+=(siz[u]-siz[v]-1)*siz[v];
		}
		ans[u]+=(siz[1]-siz[u])*(siz[u]-1)*2;
	}
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)
			continue;	
		dfs2(v,u);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		add1(u,v);
		add1(v,u);
	}
	id=n;
	tarjin(1);
	dfs(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		ans[i]/=2,ans[i]+=n-1;
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
	return 0;
}

T3:1304. 人员雇佣

原题：P1791 [国家集训队] 人员雇佣

这个问题是网络流的最小割问题。

最小割问题的模型就是这个

然后建边。题解说的很清楚。

T4:1305. 迷宫守卫（maze）

原题：P13494 【MX-X14-T4】分门别类

首先，写出

O(N^3)

的

DP

。设

dp_{i,j,k}

表示处理了前

i

种数，有

j

个偶数集合，

k

个奇数集合，是否可行。

考虑优化，发现在固定总集合状态时可以只记录一个，且集合状态符合单调性（

n

越大集合个数显然更大），将状态调整为

dp_{i,j}

表示处理完了前

i

种数，有

j

个长度为奇数的整数集的方是否可行，每次二分总集合个数，看是否合法。

转移：

dp_{i,j} \to dp_{i+1,j+x-(cnt_i-x)}

其中

cnt_i

是离散化后值为

x

的数的个数显然

dp_{i,j} \to dp_{i+1,j+x-(cnt_i-x)} \ = \ dp_{i,j} \to dp_{i+1,j+2*x-cnt-i}

所以就可以转移了。

考虑输出方案怎么做。

记录

g_i

表示转移到

dp_{i}

的

dp_{i-1}

的

j

值，因为

g_i=g_{i-1}+2*x-cnt_i

所以可以解方程得出

x

，所以就可以输出方案了。

代码没有写。

2025.08.08【提高A组】模拟赛

T1：1311. 【江苏小营】有趣的数

原题

题解

T4:1314. 话旧(reminiscence)

原题：P3336 [ZJOI2013] 话旧

2025.08.10【提高A组】模拟赛

T1: 1319. 【NOIP2013模拟联考2】摘取作物(pick)

数据范围很小，但是无法状压，考虑抽象做法，使用网络流建模。

对于每一个行建虚点，每一列建虚点，

s

向行虚点连容量为

2

，费用为

0

的边，列虚点向

t

连容量为

2

费用为

0

的边，中间每一个行虚点向每一个列虚点连容量为

1

，费用为

w_{i,j}

的边，容量代表了选了几个点，跑最大费用最大流，只用将最小费用最大流中的 spfa 的最短路变成最长路。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=30+10,M=900+10,inf=1e15;
int n,m;
int val[N][N];
int cnt=1;
int s,t;
int H[N],L[N];
int h[M*M],to[M*M],ne[M*M],w[M*M],fl[M*M],idx=1;
void add(int u,int v,int W,int c)
{
	to[++idx]=v;
	w[idx]=W;
	fl[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
void Add(int u,int v,int W,int c)
{
	add(u,v,c,W);
	add(v,u,-c,0);
}
int dis[M*M];
bool vst[M*M];
bool spfa()
{
	for(int i=1;i<=cnt;i++)
	{
		dis[i]=-inf;
		vst[i]=0;
	}
	dis[s]=0;
	queue<int> q;
	q.emplace(s);
	vst[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vst[u]=0;
		for(int i=h[u];i;i=ne[i])
		{
			int v=to[i];
			if(fl[i]&&dis[v]<dis[u]+w[i])
			{
				dis[v]=dis[u]+w[i];
				if(!vst[v])
				{
					q.emplace(v);
					vst[v]=1;
				}
			}
		}
	}
	return (dis[t]!=(-inf)&&dis[t]>=0);
}
int cur[M*M];
int res;
int dfs(int u,int flow)
{
	if(u==t||!flow)
		return flow;
	vst[u]=1;
	int tmp=0;
	for(int &i=cur[u];i;i=ne[i])
	{
		int v=to[i];
		if(dis[v]==dis[u]+w[i]&&fl[i]&&!vst[v])
		{
			int d=dfs(v,min(fl[i],flow-tmp));
			if(d)
			{
				res+=w[i]*d;
				fl[i]-=d;
				fl[i^1]+=d;
				tmp+=d;
				if(tmp==flow)
					break;
			}	
		}
	}
	vst[u]=0;
	return tmp;
}
int long_dinic()
{
	int ans=0;
	while(spfa())
	{
		for(int i=1;i<=cnt;i++)
			cur[i]=h[i];
		int d=dfs(s,inf);
		while(d)
		{
			ans+=d;
			d=dfs(s,inf);
		}
	}
	return ans;
}
signed main()
{
	freopen("pick.in","r",stdin);
	freopen("pick.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>val[i][j];
	s=1;
	t=2;
	cnt=2;
	for(int i=1;i<=n;i++)
		H[i]=++cnt,
		Add(s,H[i],2,0);
	for(int i=1;i<=m;i++)
		L[i]=++cnt,
		Add(L[i],t,2,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			Add(H[i],L[j],1,val[i][j]);
	long_dinic();
	cout<<res<<endl;
	return 0;
}

T2：1320. 互补约数

求

\sum_{n=1}^{N} \sum_{d|n} \gcd(d,\frac nd)

枚举两个数使它们乘起来小于等于

N

，这种转化与枚举所有因数是等价的，相当于改枚举约数为枚举倍数。

= \sum_{x*y \le N} \gcd(x,y)

因为有

\sum_{d|n} \varphi(d) =n

所以

=\sum_{x*y \le N} \sum_{d| \gcd (x,y)} \varphi(d)

将

d

提前

= \sum_{d=1}^{N} \varphi(d) \sum_{d|x} \sum_{d|y} [x*y \le N]

容易发现

\min(x,y) \le \sqrt N

所以

\gcd(x,y) \le \sqrt N

所以

d \le \sqrt N

所以有

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{d|x} \sum_{d|y} [x*y \le \sqrt N]

枚举倍数，有

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{x=1}^{\lfloor \frac nd \rfloor} \sum_{y=1}^{\lfloor \frac nd \rfloor} [xyd^2 \le N]

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{x=1}^{\lfloor \frac nd \rfloor} \sum_{y=1}^{\lfloor \frac nd \rfloor} [xy \le \lfloor \frac N {d^2} \rfloor ]

枚举

xy

的值，设为

t

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{t=1}^{\frac {N^2}{d^2}} [t \le \lfloor \frac N {d^2} \rfloor]

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{t=1}^{\frac {N}{d^2}} [t \le \lfloor \frac N {d^2} \rfloor]

\sum_{d=1}^{\sqrt N} \varphi(d) \sum_{t=1}^{\frac {N}{d^2}} \lfloor \frac N {td^2} \rfloor

两层数论分块，时间复杂度

O(n^{\frac 34})

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e6+10;
int n;
int phi[N];
vector<int> primes;
bitset<N> st;
void init(int n)
{
	st[1]=1;
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!st[i])
		{
			primes.emplace_back(i);
			phi[i]=i-1;
		}
		for(auto j:primes)
		{
			if(i*j>n)
				break;
			st[i*j]=1;
			if(i%j==0)
			{
				phi[i*j]=phi[i]*j;
				break;
			}
			phi[i*j]=phi[i]*phi[j];
		}
	}
}
signed main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	cin>>n;
	int limit=sqrt(n);
	init(limit);
	int ans=0;
	for(int i=1;i<=limit;i++)
	{
		int num=n/i/i;
		int tmp=0;
		for(int l=1,r=0;l<=num;l=r+1)
		{
			r=num/(num/l);
			tmp+=(num/l)*(r-l+1);
		}
		ans+=phi[i]*tmp;
	}
	cout<<ans;
	return 0;
}

T3:1321. 【NOIP2013模拟联考2】公路维护(road)

原题

吉司机线段数板子，注意维护好标记。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10,inf=1e15;
int n,m;
int a[N];
struct segment_tree
{
	int l,r;
	int minn,min_pos,max_tag,cmin;
	int laz;
	bool fl;
}t[N<<2];
void push_up(int u)
{
	t[u].fl=t[u<<1].fl|t[u<<1|1].fl;
	if(t[u<<1].minn<t[u<<1|1].minn)
	{
		t[u].minn=t[u<<1].minn;
		t[u].cmin=min(t[u<<1].cmin,t[u<<1|1].minn);
		t[u].min_pos=t[u<<1].min_pos;
	}
	else if(t[u<<1].minn==t[u<<1|1].minn)
	{
		t[u].minn=t[u<<1].minn;
		t[u].cmin=min(t[u<<1].cmin,t[u<<1|1].cmin);
		t[u].min_pos=t[u<<1].min_pos;
	}
	else
	{
		t[u].minn=t[u<<1|1].minn;
		t[u].cmin=min(t[u<<1].minn,t[u<<1|1].cmin);
		t[u].min_pos=t[u<<1|1].min_pos;
	}
}
void build(int u,int l,int r)
{
	t[u].l=l;
	t[u].r=r;
	t[u].max_tag=inf;
	if(l==r)
	{
		t[u].minn=a[l];
		t[u].min_pos=l;
		t[u].cmin=inf;
		return ;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}
void change_max(int u,int val)
{
	if(t[u].minn>=val)
		return ;
	t[u].minn=val;
	t[u].max_tag=val;
}
void change_sum(int u,int val)
{
	t[u].laz+=val;
	t[u].minn+=val;
	if(t[u].max_tag!=inf)
		t[u].max_tag+=val;
	if(t[u].cmin!=inf)
		t[u].cmin+=val;
}
void push_down(int u)
{
	if(t[u].laz)
	{
		change_sum(u<<1,t[u].laz);
		change_sum(u<<1|1,t[u].laz);
		t[u].laz=0;
	}
	if(t[u].max_tag!=inf)
	{
		change_max(u<<1,t[u].max_tag);
		change_max(u<<1|1,t[u].max_tag);
		t[u].max_tag=inf;
	}
}
void update_max(int u,int l,int r,int val)
{
	if(t[u].minn>=val)
		return ;
	if(l<=t[u].l&&t[u].r<=r&&t[u].cmin>val)
	{
		change_max(u,val);
		return ;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(l<=mid)
		update_max(u<<1,l,r,val);
	if(r>mid)
		update_max(u<<1|1,l,r,val);
	push_up(u);
}
void update_sum(int u,int l,int r,int val)
{
	if(l<=t[u].l&&t[u].r<=r)
	{
		change_sum(u,val);
		return ;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(l<=mid)
		update_sum(u<<1,l,r,val);
	if(r>mid)
		update_sum(u<<1|1,l,r,val);
	push_up(u);
}
void update_dian(int u,int x)
{
	if(t[u].l==t[u].r&&t[u].l==x)
	{
		t[u].fl=1;
		t[u].minn=inf;
		return ;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)
		update_dian(u<<1,x);
	else
		update_dian(u<<1|1,x);
	push_up(u);
}
bool query1(int u,int l,int r)
{
	if(l<=t[u].l&&t[u].r<=r)
		return t[u].fl;
	int mid=(t[u].l+t[u].r)>>1;
	bool res=0;
	if(l<=mid)
		res|=query1(u<<1,l,r);
	if(r>mid)
		res|=query1(u<<1|1,l,r);
	return res;
}
pair<int,int> query2(int u,int l,int r)
{
	if(l<=t[u].l&&t[u].r<=r)
		return make_pair(t[u].minn,t[u].min_pos);
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	pair<int,int> res=make_pair(inf,0);
	if(l<=mid)
		res=query2(u<<1,l,r);
	if(r>mid)
	{
		auto tmp=query2(u<<1|1,l,r);
		if(tmp.first<res.first)
			res=tmp;
	}
	return res;
}
signed main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	int l=0,ans=0;
	cin>>n>>m>>l;
	for(int i=1;i<=n;i++)
		a[i]=l;
	build(1,1,n);
	for(int i=1,op,s,t,d;i<=m;i++)
	{
		cin>>op>>s>>t>>d;
		if(op==1)
		{
			if(query1(1,s,t))
				continue;
			ans++;
			update_sum(1,s,t,-d);
			while(query2(1,s,t).first<=0)
				update_dian(1,query2(1,s,t).second);
		}
		else if(op==2)
			update_sum(1,s,t,d);
		else if(op==3)
			update_max(1,s,t,d);
	}
	cout<<ans<<endl;
	return 0;
}

2025.08.12【提高A组】模拟赛

T1:1329. 距离(dis)

这道题容易打出暴力，发现暴力复杂度大的原因是当一个点值较小时，暴力跳时会很多，所以考虑优化。

容易发现网格图上的路径一定是一条折线。

当一个值小于

\sqrt n

时，维护一个数组

f

表示向左或向上的第一个拐点在哪里，暴力跳，复杂度

O(n \sqrt n)

。查询时，先暴力跳到由预处理的行/列上，然后再在预处理上一起跳，最后在同一行/列上就直接减。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=1e5+10,M=400+10;
int n,m;
int f1[M][N],f2[N][M];//（i，j）这个点向前/上最远能跳到哪里。
int a[N],b[N];
int id1[N],id2[N],cnt;
int limit;
void calc(int x,int y,bool op)//0:向左 1:向右
{
	if(x<1||y<1)
		return ;
	if(!op)
	{
		int id=1;
		for(int i=1;i<=n;i++)
		{
			if(a[x]>b[i]) 
				id=i;
			f1[id1[x]][i]=id;
		}
	}
	else
	{
		int id=1;
		for(int i=1;i<=n;i++)
		{
			if(a[i]<b[y]) 
				id=i;
			f2[i][id2[y]]=id;
		}
	}
}
map<pair<int,int>,int>  vst;
int ans=0;
bool check(int x,int y)
{
	if(a[x]<=limit||b[y]<=limit)
		return 0;
	return 1;
}
int dep(int x,int y)
{
	return x+y-1;
}
bool check2(int x,int y,int p,int q)
{
	if(a[x]<=limit&&a[p]<=limit&&a[x]==a[p]&&f1[id1[x]][y]==f1[id1[p]][q])
		return 0;
	if(b[y]<=limit&&b[q]<=limit&&b[y]==b[q]&&f2[x][id2[y]]==f2[p][id2[q]])
		return 0;
	if(x==p&&y==q)
		return 0;
	return 1;
}
pair<int,int> jump(int x,int y,int p,int q)
{
	while(check(x,y)||check(p,q))
	{
		if(dep(x,y)<dep(p,q)) 
			swap(x,p),swap(y,q);
		if(!check(x,y))
			swap(x,p),swap(y,q);
		if(x==p&&y==q)
			return make_pair(x,y);
		if(a[x]>b[y])
			x--;
		else
			y--;
	}
//	cout<<-1;
	while(check2(x,y,p,q))
	{
		int topx1=0,topx2=0;
		if(a[x]<=limit&&f1[id1[x]][y]!=y)
			topx1=x,topx2=f1[id1[x]][y];
		else
			topx1=f2[x][id2[y]],topx2=y;
		int topp1=0,topp2=0;
		if(a[p]<=limit&&f1[id1[p]][q]!=q)
			topp1=p,topp2=f1[id1[p]][q];
		else
			topp1=f2[p][id2[q]],topp2=q;
		if(dep(topx1,topx2)<dep(topp1,topp2))
			swap(x,p),swap(y,q);
		if(a[x]<=limit&&f1[id1[x]][y]!=y)
			y=f1[id1[x]][y];
		else
			x=f2[x][id2[y]];
	}
	if(dep(x,y)<dep(p,q))
		return make_pair(x,y);
	else
		return make_pair(p,q);
}
signed main()
{
	freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	limit=sqrt(n<<1);
	for(int i=1;i<=n;i++)
		if(a[i]<=limit)
			id1[i]=++cnt;
	cnt=0;
	for(int i=1;i<=n;i++)
		if(b[i]<=limit)
			id2[i]=++cnt;
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=limit)
			calc(i,n,0);
		if(b[i]<=limit)
			calc(n,i,1);
	}
	cin>>m;
	for(int i=1,x,y,p,q;i<=m;i++)
	{
		cin>>x>>y>>p>>q;
		ans=0;
		auto lca=jump(x,y,p,q);
//		cout<<lca.first<<" "<<lca.second<<endl;
		cout<<dep(x,y)+dep(p,q)-(dep(lca.first,lca.second)<<1)<<endl;
	}
	return 0;
}

2025.08.13【提高A组】模拟赛

T1:1338. 【GDKOI2016】项链

可以发现，这个问题的答案就是两个回文串拼起来，对称轴就是回文中心的连线。

现在考虑怎样求出回文串，Manacher处理出每一个位置的最长回文半径的长度，设有两个回文中心

i,j(i<j)

，当满足

j-i \le n

且

j+len[j]-1 \ge i-len[i]+1

，用线段树维护最小的

i

即可。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 5000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=2e5+10;
int n;
string s,s1;
int rl[N<<1];
bool flg[N<<1];
int seg[N*8];
void update(int u,int l,int r,int x,int val)
{
	if(l==r)
	{
		flg[val]=1;
		seg[u]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		update(u<<1,l,mid,x,val);
	else
		update(u<<1|1,mid+1,r,x,val);
	seg[u]=max(seg[u<<1],seg[u<<1|1]);
}
int query(int u,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
		return seg[u];
	int mid=(l+r)>>1,res=0;
	if(L<=mid)
		res=query(u<<1,l,mid,L,R);
	if(R>mid)
		res=max(res,query(u<<1|1,mid+1,r,L,R));
	return res;
}
signed main()
{
	cin>>s1;
	n=s1.size();
	s1=" "+s1+s1;
	s=" }{";
	for(int i=1;i<(signed)s1.size();i++)
	{
		s.push_back(s1[i]);
		s.push_back('{');
	}
	int len=s.size();
	int maxr=0,pos=0;
	for(int i=1;i<(signed)s.size();i++)
	{
		if(i<maxr)
			rl[i]=min(rl[pos*2-i],maxr-i);
		else
			rl[i]=1;
		while(s[i+rl[i]]==s[i-rl[i]]&&1<=i-rl[i]&&(signed)s.size()>i+rl[i])
			rl[i]++;
		if(maxr<i+rl[i])
		{
			maxr=i+rl[i];
			pos=i;
		}			
	}
	for(int i=1;i<=n;i++)
		update(1,0,len,i-rl[i]+1,i);
	int ans=0;
	for(int i=1;i<len-n;i++)
	{
		ans=max(ans,query(1,0,len,0,i+rl[i]-1)-i);
		if(!flg[i])
			update(1,0,len,i-rl[i+1]+1,0);
		update(1,0,len,i+1+n-rl[i+1+n]+1,i+1+n);
	}
	cout<<ans;
	return 0;
}

T2:1339. 「BJOI2018」二进制

首先，

3

的二进制表示是

(11)_2

，

21

的二进制表示是

(10101)_2

，而且在合法的一段二进制表示前面或后面添

0

是不影响合法性的，所以所有

1

的个数为偶数或者

1

的个数为奇数且

0

的个数大于等于

2

的

01

串是合法的。

现在直接维护不好维护，考虑维护不合法的序列个数，后见题解。

题解

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10;
int n,m;
int a[N];
struct segment_tree
{
	int l,r;
	int dl[2][2],dr[2][2];
	int fl[3],fr[3];
	int l0,r0,s0,s1,ans;
	segment_tree()
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				dl[i][j]=dr[i][j]=0;
		for(int i=0;i<3;i++)
			fl[i]=fr[i]=0;
		l0=r0=s0=s1=ans=0;
	}
	void pre(int x)
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				dl[i][j]=dr[i][j]=0;
		for(int i=0;i<3;i++)
			fl[i]=fr[i]=0;
		l0=r0=s0=s1=ans=0;
		if(x==1)
		{
			dl[0][1]=dr[0][1]=1;
			fl[0]=fr[0]=1;
			s1=ans=1;
		}
		else
		{
			dl[1][0]=dr[1][0]=1;
			l0=r0=s0=1;
		}
	}
}t[N<<2];
#define data segment_tree
#define s ans
#define A a
#define B b
segment_tree merge(const segment_tree &a,const segment_tree &b)
{
	segment_tree c;
	c.l=a.l;
	c.r=b.r;
	c.l0=a.l0;
	c.r0=b.r0;
	if(a.s1==0)
		c.l0+=b.l0;
	if(b.s1==0)
		c.r0+=a.r0;
	c.s0=a.s0+b.s0;
	c.s1=a.s1+b.s1;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			c.dl[i][j]+=a.dl[i][j];
			if(i>=a.s0)
				c.dl[i][j]+=b.dl[i-a.s0][j^(a.s1&1)];
			c.dr[i][j]+=b.dr[i][j];
			if(i>=b.s0)
				c.dr[i][j]+=a.dr[i-b.s0][j^(b.s1&1)];
		}
	}
	for(int i=0;i<3;i++)
	{
		c.fl[i]+=a.fl[i];
		if(a.s1==0)
			c.fl[min(2ll,i+a.s0)]+=b.fl[i];
		c.fr[i]+=b.fr[i];
		if(b.s1==0)
			c.fr[min(2ll,i+b.s0)]+=a.fr[i];
	}
	if(a.s1==1&&b.l0)
		c.fl[min(2ll,a.s0+b.l0)]+=1,c.fl[2]+=b.l0-1;
	if(b.s1==1&&a.r0)
		c.fr[min(2ll,b.s0+a.r0)]+=1,c.fr[2]+=a.r0-1;
	c.ans+=a.ans+b.ans;
	c.ans+=a.dr[0][0]*(b.dl[0][1]+b.dl[1][1]);
	c.ans+=a.dr[0][1]*(b.dl[0][0]+b.dl[1][0]);
	c.ans+=a.dr[1][0]*b.dl[0][1];
	c.ans+=a.dr[1][1]*b.dl[0][0];
	if(b.l0)
		c.ans+=b.l0*(a.fr[0]+a.fr[1]+a.fr[2])-a.fr[0];
	if(a.r0)
		c.ans+=a.r0*(b.fl[0]+b.fl[1]+b.fl[2])-b.fl[0];
	return c;
}
//data merge(data A,data B)
//{
//	data c;
//	c.l=A.l;
//	c.r=B.r;
//	for(int i=0;i<2;++i)
//		for(int j=0;j<2;++j)
//		{
//			c.dl[i][j]+=A.dl[i][j];
//			c.dr[i][j]+=B.dr[i][j];
//			if(i>=A.s0)c.dl[i][j]+=B.dl[i-A.s0][j^(A.s1&1)];
//			if(i>=B.s0)c.dr[i][j]+=A.dr[i-B.s0][j^(B.s1&1)];
//		}
//	for(int i=0;i<3;++i)
//	{
//		c.fl[i]+=A.fl[i];c.fr[i]+=B.fr[i];
//		if(!A.s1)c.fl[min(2ll,i+A.s0)]+=B.fl[i];
//		if(!B.s1)c.fr[min(2ll,i+B.s0)]+=A.fr[i];
//	}
//	if(A.s1==1&&B.l0)c.fl[min(2ll,A.s0+B.l0)]+=1,c.fl[2]+=B.l0-1;
//	if(B.s1==1&&A.r0)c.fr[min(2ll,B.s0+A.r0)]+=1,c.fr[2]+=A.r0-1;
//	c.l0=(A.s1==0)?A.l0+B.l0:A.l0;
//	c.r0=(B.s1==0)?B.r0+A.r0:B.r0;
//	c.s0=A.s0+B.s0;c.s1=A.s1+B.s1;
//	
//	c.s=A.s+B.s;
//	c.s+=A.dr[0][0]*(B.dl[0][1]+B.dl[1][1]);
//	c.s+=A.dr[0][1]*(B.dl[0][0]+B.dl[1][0]);
//	c.s+=A.dr[1][0]*B.dl[0][1];
//	c.s+=A.dr[1][1]*B.dl[0][0];
//	if(B.l0)c.s+=B.l0*(A.fr[0]+A.fr[1]+A.fr[2])-A.fr[0];
//	if(A.r0)c.s+=A.r0*(B.fl[0]+B.fl[1]+B.fl[2])-B.fl[0];
//	return c;
//}
void push_up(int u)
{
	t[u]=merge(t[u<<1],t[u<<1|1]);
}
void build(int u,int l,int r)
{
	t[u].l=l;
	t[u].r=r;
	if(l==r)
	{
		t[u].pre(a[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}
void update(int u,int x)
{
	if(t[u].l==t[u].r&&t[u].l==x)
	{
		t[u].pre(a[x]);
		return ;
	}
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)
		update(u<<1,x);
	else
		update(u<<1|1,x);
	push_up(u);
}
segment_tree query(int u,int l,int r)
{
	if(l<=t[u].l&&t[u].r<=r)
		return t[u];
	int mid=(t[u].l+t[u].r)>>1;
	segment_tree res1,res2;
	int cnt=0;
	if(l<=mid)
		res1=query(u<<1,l,r),cnt+=1;
	if(r>mid)
		res2=query(u<<1|1,l,r),cnt+=2;
	if(cnt==3)
		return merge(res1,res2);
	else if(cnt==1)
		return res1;
	else
		return res2;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	cin>>m;
	for(int i=1,op,l,r;i<=m;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>l;
			a[l]^=1;
			update(1,l);
		}
		else
		{
			cin>>l>>r;
			int ans=(r-l+2)*(r-l+1)/2;
			cout<<ans-query(1,l,r).ans<<endl;
		}
	}
	return 0;
}

2025.08.15【提高A组】模拟赛

T1:1346. 【NOIP2013模拟】理科男

pdf 题解写的比较清楚，注意乘法会爆 long long以及分数先化简。

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int __int128
const int N=1e5+10;
int A,B,K;
int a[N];
unordered_map<long long,long long> mp;
void init()
{
	mp.clear();
	memset(a,0,sizeof(a));
}
int get_phi(int num)
{
	int phi=num;
	for(int i=2;i*i<=num;i++)
	{
		if(num%i==0)
		{
			phi=phi/i*(i-1);
			while(num%i==0)
				num/=i;
		}
	}
	if(num>1)
		phi=phi/num*(num-1);
	return phi;
}
int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=(res%B*a%B)%B;
		a=(a%B*a%B)%B;
		b>>=1;
	}
	return res%B;
}
void solve()
{
	init();
	cin>>A>>B>>K;
	int g=__gcd(A,B);
	A/=g,B/=g;
	a[1]=A;
	mp[a[1]]=1;
	for(int i=2;i<=100000;i++)
	{
		a[i]=(K*a[i-1])%B;
		if(a[i]==0)
		{
			cout<<i-1<<" "<<0<<endl;
			return ;
		}
		if(mp.find(a[i])!=mp.end())
		{
			cout<<mp[a[i]]-1<<" "<<i-mp[a[i]]<<endl;
			return ;
		}
		mp[a[i]]=i;
	}
	int cnt=0,id=2,G=1;
	while(__gcd(B,K)>1)
	{
		int g=__gcd(a[id]/G,B);
		B/=g;
		G*=g;
		a[id]/=G;
		id++,cnt++;
	}
	if(B==1)
	{
		cout<<cnt<<" "<<0<<endl;
		return ;
	}
	int x=get_phi(B);
	vector<int> fac;
	int tmp=x;
	for(int i=2;i*i<=tmp;i++)
	{
		if(tmp%i==0)
		{
			fac.emplace_back(i);
			while(tmp%i==0)
				tmp/=i;
		}
	}
	for(auto i:fac)
		while(x%i==0&&qpow(K,x/i)==1)
			x/=i;
	cout<<cnt<<" "<<x<<endl;
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

T2：1347. Theresa与数据结构

三维 KD-tree 板子.

代码

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
#define lson t[k].ls
#define rson t[k].rs
using namespace std;
const int N=1e5+15;
struct node
{
	int x,y,z,w;
}p[N];
int cnt;
struct kdtree
{
	int lx,ly;
	int rx,ry;
	int lz,rz;
	int ls,rs;
	int sum;
	kdtree(int lx=0,int ly=0,int rx=0,int ry=0,int lz=0,int rz=0,int ls=0,int rs=0,int sum=0) : 
	lx(lx),ly(ly),rx(rx),ry(ry),lz(lz),rz(rz),ls(ls),rs(rs),sum(sum) {}
}t[N];
int n,id,rt;
int m;
bool cmp1(const node &l,const node &r)
{
	if(l.x!=r.x)
		return l.x<r.x;
	else if(l.y!=r.y)
		return l.y<r.y;
	else
		return l.z<r.z;
}
bool cmp2(const node &l,const node &r)
{
	if(l.y!=r.y)
		return l.y<r.y;
	else if(l.z!=r.z) 
		return l.z<r.z;
	else
		return l.x<r.x;
}
bool cmp3(const node &l,const node &r)
{
	if(l.z!=r.z)
		return l.z<r.z;
	else if(l.y!=r.y)
		return l.y<r.y;
	else
		return l.x<r.x;
}
void push_up(int k)
{
	t[k].lx=min({t[lson].lx,t[rson].lx,p[k].x});
	t[k].rx=max({t[lson].rx,t[rson].rx,p[k].x});
	t[k].ly=min({t[lson].ly,t[rson].ly,p[k].y});
	t[k].ry=max({t[lson].ry,t[rson].ry,p[k].y});
	t[k].lz=min({t[lson].lz,t[rson].lz,p[k].z});
	t[k].rz=max({t[lson].rz,t[rson].rz,p[k].z});
	t[k].sum=t[lson].sum+t[rson].sum+p[k].w;
}
int build(const int l,const int r,const int opt)
{
	if(l>r)
		return 0;
	int mid=(l+r)>>1;
	int k=mid;
	if(l==r)
		t[k]=kdtree(p[l].x,p[l].y,p[l].x,p[l].y,p[l].z,p[l].z,0,0,p[k].w);
	if(opt==0)
		nth_element(p+l,p+mid,p+r+1,cmp2);
	else if(opt==1)
		nth_element(p+l,p+mid,p+r+1,cmp1);
	else if(opt==2)
		nth_element(p+l,p+mid,p+r+1,cmp3);
	t[k].ls=build(l,mid-1,(opt+1)%3);
	t[k].rs=build(mid+1,r,(opt+1)%3);
	push_up(k);
	return k;
}
int xht;
int query(const int k,const int lx,const int rx,const int ly,const int ry,const int lz,const int rz)
{
	if(!k||ry<t[k].ly||ly>t[k].ry||rx<t[k].lx||lx>t[k].rx||rz<t[k].lz||lz>t[k].rz)
		return 0;
	if(ly<=t[k].ly&&t[k].ry<=ry&&lx<=t[k].lx&&t[k].rx<=rx&&lz<=t[k].lz&&t[k].rz<=rz)
		return t[k].sum;
	xht++;
	int res=0;
	if(lx<=p[k].x&&p[k].x<=rx&&ly<=p[k].y&&p[k].y<=ry&&lz<=p[k].z&&p[k].z<=rz)
		res+=p[k].w;
	res+=query(lson,lx,rx,ly,ry,lz,rz);
	res+=query(rson,lx,rx,ly,ry,lz,rz);
	return res;
}
signed main()
{
	cin>>n;
	for(int i=1,x,y,z;i<=n;i++)
	{
		cin>>x>>y>>z;
		p[++cnt]={x,y,z,1};
	}
	id=cnt;
	t[0]=kdtree(1000000000,1000000000,0,0,1000000000,0,0,0,0);
	rt=build(1,cnt,0);
	cin>>m;
	string op;
	vector<node> v;
	for(int j=1,x,y,z,r;j<=m;j++)
	{
		cin>>op;
		if(op=="ADD")
		{
			int x,y,z;
			cin>>x>>y>>z;
			v.push_back({x,y,z,-1});
			p[++cnt]={x,y,z,1};
			if((cnt-id)*(cnt-id)>20*(cnt))
			{
				id=cnt;
				rt=build(1,cnt,0);
			}
		}
		if(op=="QUERY")
		{
			cin>>x>>y>>z>>r;
			int ans=query(rt,x,x+r,y,y+r,z,z+r);
			for(int i=id+1;i<=cnt;i++)
				if(x<=p[i].x&&p[i].x<=x+r&&y<=p[i].y&&p[i].y<=y+r&&z<=p[i].z&&p[i].z<=z+r)
					ans+=p[i].w;
			cout<<ans<<endl;
		}
		if(op=="CANCEL")
		{
			auto tmp=v.back();
			v.pop_back();
			p[++cnt]=tmp;
			if((cnt-id)*(cnt-id)>20*(cnt))
			{
				id=cnt;
				rt=build(1,cnt,0);
			}
		}
	}
}

文章操作