3.11

闲话

  • @wkh2008 和 @lty_ylzsx 被 \(miaomiao\) 从 \(1\) 机房赶到 \(3\) 机房了。
  • 不知道为啥 \(field\) 来催了下改模拟赛的题，可能为了缓解尴尬（？）。

做题纪要

tgHZOJ 2893. 混乱邪恶

luogu P1412 经营与开发

  • 发现顺序枚举存在后效性，考虑倒序枚举。

  • 设 \(f_{i}\) 表示截止到第 \(i\) 个星球时 \(1\) 能力值能获得的最大金钱，状态转移方程为 \(f_{i}= \begin{cases} \max(f_{i+1},(1-0.01k)f_{i+1}+x_{i}) & type_{i}=1 \\ \max(f_{i+1},(1+0.01c)f_{i+1}-x_{i}) & type_{i}=2 \end{cases}\) 。

    点击查看代码 

    int pd[200000];
double x[200000],f[200000];
int main()
{
	int n,i;
	double k,c,w;
	cin>>n>>k>>c>>w;
	for(i=1;i<=n;i++)
	{
		cin>>pd[i]>>x[i];
	}
	for(i=n;i>=1;i--)
	{
		f[i]=max(f[i+1],(pd[i]==1)?f[i+1]*(1-0.01*k)+x[i]:f[i+1]*(1+0.01*c)-x[i]);
	}
	printf("%.2lf\n",f[1]*w);
	return 0;
}

3.12

闲话

  • 貌似调考成绩算回原班级，已经在想象调考后以前课任老师上来 \(D\) 人了。

做题纪要

[ABC343G] Compress Strings

  • 多倍经验： CF25E Test

  • 由于 \(\sum\limits_{i=1}^{n} |S_{i}|\) 极大且不需要记录路径，所以 luogu P2322 [HNOI2006] 最短母串问题 的枚举所有可能的字符串 \(T\) 进行判断不可做。

  • 设 \(f_{i,j}\) 表示当“字符串包含状态”对应的二进制数为 \(i\) 时，且结尾为 \(j\) 时的最小长度，状态转移方程为 \(f_{i,j}= \min\limits_{j \ne k,(i \gg k) \And 1 \ne 0}^{} \{f_{i-(1 \ll j),k}-g_{k,j}+|S_{j}| \}\) ，其中 \(g_{k,j}\) 表示 \(S_{k}\) 的后缀和 \(S_{j}\) 的前缀匹配的最长长度，使用 \(KMP\) 维护即可。

  • 注意去重和删去在其他字符串中已被包含的字符串。

    点击查看代码 

    int nxt[200010],f[(1<<22)+10][22],g[22][22];
string s[22],ss[22],t;
int main()
{
	int m,n=0,ans=0x7f7f7f7f,flag,i,j,k,x,y;
	cin>>m;
	memset(f,0x3f,sizeof(f));
	for(i=0;i<=m-1;i++)
	{
		cin>>ss[i];
	}
	sort(ss+0,ss+m);
	m=unique(ss+0,ss+m)-ss;
	for(i=0;i<=m-1;i++)
	{
		flag=0;
		for(j=0;j<=m-1;j++)
		{
			if(i!=j&&ss[j].find(ss[i])!=string::npos)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			s[n]=ss[i];
			n++;
		}
	}
	for(x=0;x<=n-1;x++)
	{
		for(y=0;y<=n-1;y++)
		{
			if(x!=y)
			{
				t=' '+s[y]+'#'+s[x];
				for(i=2,nxt[1]=j=0;i<t.size();i++)
				{
					while(j>=1&&t[i]!=t[j+1])
					{
						j=nxt[j];
					}
					j+=(t[i]==t[j+1]);
					nxt[i]=j;
				}
				g[x][y]=nxt[t.size()-1];
			}
		}
	}
	for(i=0;i<=n-1;i++)
	{
		f[(1<<i)][i]=s[i].size();
	}
	for(i=0;i<=(1<<n)-1;i++)
	{
		for(j=0;j<=n-1;j++)
		{
			if((i>>j)&1)
			{
				for(k=0;k<=n-1;k++)
				{
					if(j!=k&&((i>>k)&1))
					{
						f[i][j]=min(f[i][j],f[i-(1<<j)][k]-g[k][j]+(int)s[j].size());
					}
				}
			}
		}
	}
	for(i=0;i<=n-1;i++)
	{
		ans=min(ans,f[(1<<n)-1][i]);
	}
	cout<<ans<<endl;
	return 0;
}

3.13

闲话

  • 下午到机房的时候，发现电脑在今天上午 \(11:30\) 的时候死机了，浏览记录多了个 tgHZOJ 。
  • 因和 \(miaomiao\) 交涉失败，下午要去博艺馆开中考百日誓师大会，占了下午第 \(8,9\) 节课。因有家长和老师参与，故 \(25,26,27\) 班只能坐在过道。洗脑痕迹明显。
  • 开完大会说让回班让班主任开班会，但现班主任出差了，代班主任连上周日的班会都没开，索性直接来机房了。
  • 晚上回班后发现那节课改公自了。

做题纪要

luogu P3214 [HNOI2011] 卡农

  • 简化题意

    • 给定 \(n,m\) 。求在集合 \(S= \{ 1,2,3, \dots ,n \}\) 中选出 \(m\) 个子集，且这 \(m\) 个子集满足以下三个性质的无序集合方案数。
      • 性质 \(1\) ：选出的 \(m\) 个子集中每个子集都不能为空。
      • 性质 \(2\) ：选出的 \(m\) 个子集中不存在两个相同的子集。
      • 性质 \(3\) ：选出的 \(m\) 个子集中 \(1 \sim n\) 的每个数的总出现次数必须是偶数。

  • 设 \(f_{i}\) 表示到当前枚举到第 \(i\) 个子集时，满足三个性质的有序集合方案数，状态转移方程为 \(f_{i}= \begin{cases} 1 & i=0 \\ A_{2^{n}-1}^{i-1}-f_{i-1}-f_{i-2} \times A_{i-1}^{1} \times A_{2^{n}-1-(i-2)}^{1} & i \ne 0 \end{cases}\) 。

    • 假设当前已确认了前 \(i-1\) 个子集，且前 \(i-1\) 个子集满足三个性质。
    • 加上第 \(i\) 个子集后满足性质 \(3\) 的共有 \(A_{2^{n}-1}^{i-1}\) 种方案。
      • 从二进制下异或和的角度分析，该结论显然。
    • 加上第 \(i\) 个子集后满足性质 \(3\) ，但不满足性质 \(1\) ，即第 \(i\) 个子集为空的共有 \(f_{i-1}\) 种方案。
    • 加上第 \(i\) 个子集后满足性质 \(3\) ，但不满足性质 \(2\) ，即第 \(i\) 个子集在前 \(i-1\) 个子集中已经出现过一次的共有 \(f_{i-2} \times A_{i-1}^{1} \times A_{2^{n}-1-(i-2)}^{1}\) 种方案。

  • 由 \(A_{n}^{m} \times \frac{1}{n-m+1}=A_{n}^{m-1}\) ，有 \(A_{n}^{m}=A_{n}^{m-1} \times (n-m+1)\) 。

  • 最终，有 \(\frac{f_{m}}{A_{m}^{m}}\) 即为所求。

    点击查看代码 

    const ll p=100000007;
ll inv[1000010],jc[1000010],jc_inv[1000010],a[1000010],f[1000010];
void A1(ll n,ll m,ll p)
{
	a[0]=1;
	for(ll i=1;i<=m;i++)
	{
		a[i]=a[i-1]*(n-i+1)%p;
	}
}
ll A2(ll n,ll m,ll p)
{   
	return (n>=m&&n>=0&&m>=0)?((m==1)?n:jc[n]*jc_inv[n-m]%p):0;
}
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
int main()
{
	ll n,m,sum,i;
	cin>>n>>m;
	sum=(qpow(2,n,p)-1+p)%p;
	A1(sum,m,p);
	inv[1]=1;
	jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1;
	for(i=2;i<=max(n,m);i++)
	{
		inv[i]=(p-p/i)*inv[p%i]%p;
		jc[i]=jc[i-1]*i%p;
		jc_inv[i]=jc_inv[i-1]*inv[i]%p;
	}
	f[0]=1;
	for(i=1;i<=m;i++)
	{
		f[i]=((a[i-1]-f[i-1]+p)%p-(f[i-2]*A2(i-1,1,p)%p)*A2(sum-(i-2),1,p)%p+p)%p;
	}
	cout<<f[m]*qpow(A2(m,m,p),p-2,p)%p<<endl;
	return 0;
}

luogu P4884 多少个 1？

  • \(\begin{matrix}n 个 1 \\ \overbrace{11 \dots 1}\end{matrix} \equiv b \pmod{p}\) 等价于 \(\frac{10^{n}-1}{9} \equiv b \pmod{p}\) ，移项得 \(10^{n} \equiv (9b+1) \pmod{p}\) 。

    点击查看代码 

    #define ll __int128_t
ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar((x%10)+'0');
}
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
ll bsgs(ll a,ll b,ll p)
{
	if(1%p==b%p)
	{
		return 0;
	}
	else
	{
		map<ll,ll>vis;
		ll k=sqrtl(p)+1,i,sum;
		for(i=0;i<=k-1;i++)
		{
			vis[b*qpow(a,i,p)%p]=i;
		}
		a=qpow(a,k,p);
		for(i=0;i<=k;i++)
		{
			sum=qpow(a,i,p);
			if(vis.find(sum)!=vis.end())
			{
				if(i*k-vis[sum]>=0)
				{
					return i*k-vis[sum];
				}
			}
		}
		return -1;
	}
}
int main()
{
	ll b,p;
	b=read();
	p=read();
	write(bsgs(10,9*b+1,p));
	return 0;
}

luogu P4454 [CQOI2018] 破解D-H协议

  • 由 原根 定义，有 \(\gcd(g,p)=1\) 。

    点击查看代码 

    #define ll __int128_t
ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar((x%10)+'0');
}
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
ll bsgs(ll a,ll b,ll p)
{
	if(1%p==b%p)
	{
		return 0;
	}
	else
	{
		map<ll,ll>vis;
		ll k=sqrtl(p)+1,i,sum;
		for(i=0;i<=k-1;i++)
		{
			vis[b*qpow(a,i,p)%p]=i;
		}
		a=qpow(a,k,p);
		for(i=0;i<=k;i++)
		{
			sum=qpow(a,i,p);
			if(vis.find(sum)!=vis.end())
			{
				if(i*k-vis[sum]>=0)
				{
					return i*k-vis[sum];
				}
			}
		}
		return -1;
	}
}
int main()
{
	ll g,p,n,a,b,i;
	g=read();
	p=read();
	n=read();
	for(i=1;i<=n;i++)
	{
		a=read();
		b=read();
		write(qpow(a,bsgs(g,b,p),p));
		cout<<endl;
	}
	return 0;
}

3.14

闲话

  • 早上到机房的时候，发现电脑在今天凌晨 \(2:10\) 的时候死机了，以后走的时候索性直接关机了。
  • 回班的时候看见 \(miaomiao\) 坐在靠门的位置摆弄 \(NOI \ Linux \ 2.0\) ，但他为什么不坐在教师机的位置呢。
  • \(miaomiao\) 下午 \(14:00 \sim 18:05\) 安排了一场模拟赛，可能以后都是周四有模拟赛。
  • 下午 \(14:06\) 的时候 @jijidawang 才到机房，然后被 \(miaomiao\) \(D\) 了。
  • 晚上代班主任说周五第一节课调到下午上，成功少了一节仅有 \(40min\) 的奥赛课。

做题纪要

luogu P5025 [SNOI2017] 炸弹

  • 设 \([L_{i},R_{i}]\) 表示第 \(i\) 颗炸弹所能引爆的炸弹区间。

  • 处理出第 \(i\) 颗炸弹的实际引爆半径 \(r_{i}’\) ，然后分别对左右端点进行转移即可。

    点击查看代码 

    const ll p=1000000007;
ll x[500010],r[500010],L[500010],R[500010];
int main()
{
	ll n,ans=0,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x[i]>>r[i];
		L[i]=R[i]=i;
	}
	for(i=1;i<=n;i++)
	{
		while(L[i]-1>=1&&x[i]-r[i]<=x[L[i]-1])
		{
			r[i]=max(r[i],x[L[i]-1]+r[L[i]-1]-x[i]);
			L[i]=L[L[i]-1];
		}
	}
	for(i=n;i>=1;i--)
	{
		while(R[i]+1<=n&&x[i]+r[i]>=x[R[i]+1])
		{
			L[i]=min(L[i],L[R[i]+1]);
			R[i]=R[R[i]+1];
		}
	}
	for(i=1;i<=n;i++)
	{
		ans=(ans+(R[i]-L[i]+1)*i%p)%p;
	}
	cout<<ans<<endl;
	return 0;
}

CF56E Domino Principle

  • 将多米诺骨牌压倒转化为炸弹爆炸即可，注意只更新右端点。

    点击查看代码 

    struct node
{
	int x,r,L,R,id;
}a[100010];
bool cmp1(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(node a,node b)
{
	return a.id<b.id;
}
int main()
{
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].r;
		a[i].r--;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp1);
	for(i=1;i<=n;i++)
	{
		a[i].L=a[i].R=i;
	}
	for(i=n;i>=1;i--)
	{
		while(a[i].R+1<=n&&a[i].x+a[i].r>=a[a[i].R+1].x)
		{
			a[i].r=max(a[i].r,a[a[i].R+1].x+a[a[i].R+1].r-a[i].x);
			a[i].R=a[a[i].R+1].R;
		}
	}
	for(i=n;i>=1;i--)
	{
		while(a[i].R+1<=n&&a[i].x+a[i].r>=a[a[i].R+1].x)
		{
			a[i].R=max(a[i].R,a[a[i].R+1].R);
		}
	}
	sort(a+1,a+1+n,cmp2);
	for(i=1;i<=n;i++)
	{
		cout<<a[i].R-a[i].L+1<<" ";
	}
	return 0;
}

LibreOJ 6277. 数列分块入门 1

  • 维护整块的增量标记 \(add_{i}\) 即可。

  • 块长取 \(\sqrt{n}\) 。

    点击查看代码 

    ll a[50010],add[50010],L[50010],R[50010],pos[50010],klen,ksum;
void init(ll n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=min(R[i-1]+klen,n);
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
	}
}
void update(ll l,ll r,ll val)
{
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			a[i]+=val;
		}
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			a[i]+=val;
		}
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			add[i]+=val;
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			a[i]+=val;
		}
	}
}
ll ask(ll l)
{
	return a[l]+add[pos[l]];
}
int main()
{
	ll n,pd,l,r,val,i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	init(n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&pd,&l,&r,&val);
		if(pd==0)
		{
			update(l,r,val);
		}
		else
		{
			printf("%lld\n",ask(r));
		}
	}
	return 0;
}

HDU1166 敌兵布阵

  • 块长取 \(\sqrt{n}\) 。

    点击查看代码 

    int a[50010],sum[50010],L[50010],R[50010],pos[50010],klen,ksum;
void init(int n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(int i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(int i=1;i<=ksum;i++)
	{
		sum[i]=0;
		for(int j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
			sum[i]+=a[j];
		}
	}
}
void update(int l,int val)
{
	a[l]+=val;
	sum[pos[l]]+=val;
}
int query(int l,int r)
{
	int ans=0;
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
		{
			ans+=a[i];
		}
	}
	else
	{
		for(int i=l;i<=R[pos[l]];i++)
		{
			ans+=a[i];
		}
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
		{
			ans+=sum[i];
		}
		for(int i=L[pos[r]];i<=r;i++)
		{
			ans+=a[i];
		}
	}
	return ans;
}
int main()
{
	int t,n,l,r,i,j;
	char pd[10];
	scanf("%d",&t);
	for(j=1;j<=t;j++)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		init(n);
		printf("Case %d:\n",j);
		while(scanf("%s",pd+1))
		{
			if(pd[1]=='E')
			{
				break;
			}
			scanf("%d%d",&l,&r);
			if(pd[1]=='A')
			{
				update(l,r);
			}
			if(pd[1]=='S')
			{
				update(l,-r);
			}
			if(pd[1]=='Q')
			{
				printf("%d\n",query(l,r));
			}
		}
	}
	return 0;
}

LibreOJ 6280. 数列分块入门 4

  • 维护整块的增量标记 \(add_{i}\) 即可。

  • 块长取 \(\sqrt{n}\) 。

    点击查看代码 

    ll a[50010],sum[50010],add[50010],L[50010],R[50010],pos[50010],klen,ksum;
void init(ll n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
			sum[i]+=a[j];
		}
	}
}
void update(ll l,ll r,ll val)
{
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			a[i]+=val;
		}
		sum[pos[l]]+=val*(r-l+1);
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			a[i]+=val;
		}
		sum[pos[l]]+=val*(R[pos[l]]-l+1);
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			add[i]+=val;
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			a[i]+=val;
		}
		sum[pos[r]]+=val*(r-L[pos[r]]+1);
	}
}
ll query(ll l,ll r,ll p)
{       
	ll ans=0;
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			ans=(ans+a[i]%p)%p;
		}
		ans=(ans+(add[pos[l]]%p)*(r-l+1)%p)%p;
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			ans=(ans+a[i]%p)%p;
		}
		ans=(ans+(add[pos[l]]%p)*(R[pos[l]]-l+1)%p)%p;
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			ans=((ans+sum[i]%p)%p+(add[i]%p)*(klen%p)%p)%p;
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			ans=(ans+a[i]%p)%p;
		}
		ans=(ans+(add[pos[r]]%p)*(r-L[pos[r]]+1)%p)%p;
	}
	return ans;
}
int main()
{
	ll n,pd,l,r,val,i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	init(n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&pd,&l,&r,&val);
		if(pd==0)
		{
			update(l,r,val);
		}
		else
		{
			printf("%lld\n",query(l,r,val+1));
		}
	}
	return 0;
}

UVA12003 Array Transformer

  • 多倍经验：SP3261 RACETIME – Race Against Time | SP18185 GIVEAWAY – Give Away

  • 对于在整块内找小于给出的数的所有元素个数，容易想到对块内元素进行排序，然后二分查找得到答案。

    点击查看代码 

    ll a[50010],b[50010],L[50010],R[50010],pos[50010],klen,ksum;
void init(ll n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
		sort(b+L[i],b+R[i]+1);
	}
}
void update(ll l,ll val)
{
	b[lower_bound(b+L[pos[l]],b+R[pos[l]]+1,a[l])-b]=val;
	a[l]=val;
	sort(b+L[pos[l]],b+R[pos[l]]+1);
}
ll query(ll l,ll r,ll val)
{
	ll ans=0;
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			ans+=(a[i]<=val);
		}
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			ans+=(a[i]<=val);
		}
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			ans+=lower_bound(b+L[i],b+R[i]+1,val)-b-L[i];
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			ans+=(a[i]<=val);
		}
	}
	return ans;
}
int main()
{
	ll n,m,u,l,r,val,p,i;
	char pd;
	cin>>n>>m>>u;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	init(n);
	for(i=1;i<=m;i++)
	{
		cin>>l>>r>>val>>p;
		update(p,u*query(l,r,val)/(r-l+1));
	}
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<endl;
	}
	return 0;
}

3.15

闲话

  • 吃完早饭 @Vsinger_洛天依 给我说 \(miaomiao\) 问他报不报 \(APIO\) ，他说报，然后 \(miaomiao\) 就把他报上去了，但 \(miaomiao\) 根本没和我们说这件事。

做题纪要

LibreOJ 6278. 数列分块入门 2

  • 多倍经验： luogu P2801 教主的魔法

  • 对于整块的修改操作，其相对大小顺序不变，故维护整块的增量标记 \(add_{i}\) 即可。

    点击查看代码 

    ll a[50010],b[50010],add[50010],L[50010],R[50010],pos[50010],klen,ksum;
void init(ll n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
		sort(b+L[i],b+R[i]+1);
	}
}
void update(ll l,ll r,ll val)
{
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[l]];i<=R[pos[l]];i++)//因是区间修改，所以直接复制过来即可
		{
			b[i]=a[i];
		}
		sort(b+L[pos[l]],b+R[pos[l]]+1);
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[l]];i<=R[pos[l]];i++)
		{
			b[i]=a[i];
		}
		sort(b+L[pos[l]],b+R[pos[l]]+1);
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			add[i]+=val;
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[r]];i<=R[pos[r]];i++)
		{
			b[i]=a[i];
		}
		sort(b+L[pos[r]],b+R[pos[r]]+1);
	}
}
ll query(ll l,ll r,ll val)
{
	ll ans=0;
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			ans+=(a[i]+add[pos[l]]<val);
		}
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			ans+=(a[i]+add[pos[l]]<val);
		}
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			ans+=lower_bound(b+L[i],b+R[i]+1,val-add[i])-b-L[i];
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			ans+=(a[i]+add[pos[r]]<val);
		}
	}
	return ans;
}
int main()
{
	ll n,pd,l,r,val,i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	init(n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&pd,&l,&r,&val);
		if(pd==0)
		{
			update(l,r,val);
		}
		else
		{
			printf("%lld\n",query(l,r,val*val));
		}
	}
	return 0;
}

LibreOJ 6279. 数列分块入门 3

  • 注意在找整块时把增量标记 \(add\) 加回来。

    点击查看代码 

    ll a[100010],b[100010],add[100010],L[100010],R[100010],pos[100010],klen,ksum;
void init(ll n)
{
	klen=sqrt(n);
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
		sort(b+L[i],b+R[i]+1);
	}
}
void update(ll l,ll r,ll val)
{
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[l]];i<=R[pos[l]];i++)
		{
			b[i]=a[i];
		}
		sort(b+L[pos[l]],b+R[pos[l]]+1);
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[l]];i<=R[pos[l]];i++)
		{
			b[i]=a[i];
		}
		sort(b+L[pos[l]],b+R[pos[l]]+1);
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			add[i]+=val;
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			a[i]+=val;
		}
		for(ll i=L[pos[r]];i<=R[pos[r]];i++)
		{
			b[i]=a[i];
		}
		sort(b+L[pos[r]],b+R[pos[r]]+1);
	}
}
ll query(ll l,ll r,ll val)
{
	ll ans=-0x7f7f7f7f;
	if(pos[l]==pos[r])
	{
		for(ll i=l;i<=r;i++)
		{
			ans=max(ans,(a[i]+add[pos[l]]<val)?a[i]+add[pos[l]]:-0x7f7f7f7f);
		}
	}
	else
	{
		for(ll i=l;i<=R[pos[l]];i++)
		{
			ans=max(ans,(a[i]+add[pos[l]]<val)?a[i]+add[pos[l]]:-0x7f7f7f7f);
		}
		for(ll i=pos[l]+1;i<=pos[r]-1;i++)
		{
			ans=max(ans,(lower_bound(b+L[i],b+R[i]+1,val-add[i])-b-1>=L[i])?b[lower_bound(b+L[i],b+R[i]+1,val-add[i])-b-1]+add[i]:-0x7f7f7f7f);
		}
		for(ll i=L[pos[r]];i<=r;i++)
		{
			ans=max(ans,(a[i]+add[pos[r]]<val)?a[i]+add[pos[r]]:-0x7f7f7f7f);
		}
	}
	return (ans==-0x7f7f7f7f)?-1:ans;
}
int main()
{
	ll n,pd,l,r,val,i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	init(n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&pd,&l,&r,&val);
		if(pd==0)
		{
			update(l,r,val);
		}
		else
		{
			printf("%lld\n",query(l,r,val));
		}
	}
	return 0;
}

LibreOJ 6281. 数列分块入门 5

LibreOJ 6282. 数列分块入门 6

LibreOJ 6283. 数列分块入门 7

LibreOJ 6284. 数列分块入门 8

LibreOJ 6285. 数列分块入门 9

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。