NOIP2023未来共同体 模拟九

永恒恩典。

A. 幽咽弱起（piano）

题目简介

给定一个长度为 的模式串以及 个匹配串 ，每个匹配串有一个权值 与颜色 。

若 在 中作为子串出现（设出现位置为 ），那么你可以将 染成 ，并获得 的贡献。同一个格子可以被染色多次，贡献重复计算形式为 表示在 。

要求任意两个不同颜色的格子距离大于 ，求出最大贡献。

数据范围：

首先我们将字符串抛出掉，我们可以把问题转化为：存在若干线段，颜色为 ，权值为 ，选择一些线段使得不同色的线段距离大于 ，且权值最大。

这里的线段个数与 同阶。

设 表示 染色之后的最大贡献，那么有：

$$f_r\leftarrow\max f_{l-k-1}+g_{l,r,c}$$

其中 表示所有颜色为 且区间在 内的线段的总贡献。

至于 ，我们可以维护线段树在 时间内预处理出来，之后的转移为 的。

然后我们考虑将颜色设入状态，并倒叙枚举，记 表示当前 中，且位置 为颜色 时的最大贡献。然后将所有线段按照右端点从大到小依次转移。有：

$$f_{l_i,c_i}\leftarrow\max\{\max_{j\in[r_i+k+1,n]}f_{j,c'},\max_{j\in[l_i,n]}f_{j,c_i}\}+w_i$$

然后你发现这个问题是可以通过线段树维护的，所以维护 棵线段树查后缀 ，做到 。

AC Code

#include <bits/stdc++.h>
#define fi first 
#define se second 

using std :: cin;
using std :: min; 
using std :: max; 
using std :: cout; 
using std :: vector; 

constexpr int M = 1e5 + 5, mod = 998244353; 
constexpr int INF = 0x3f3f3f3f; 

typedef long long ll; 
typedef unsigned long long ull;
typedef double db; 
typedef unsigned int ui; 
typedef std :: pair < int, int > pii; 

//char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
//#define getchar() (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)? EOF : *p1++

inline int read() { 
	int f = 1, s = 0; char ch = getchar(); 
	while(!isdigit(ch)) (ch == '-') && (f = -1), ch = getchar(); 
	while(isdigit(ch)) s = s * 10 + ch - '0', ch = getchar(); 
	return f * s; 
}

namespace Solver {
	using std :: string; 
	int n, m, K, id, ln[35]; 
	string t[35], s; int val[35], col[35];
	int w[M]; ll dp[M][35]; 
	vector < int > P[M]; int nx[M]; 
	template < typename T > bool chkmx(T &x, const T &y) {return x < y ? x = y, 1 : 0;}
	inline void KMP(string t, int m, int id) {
		nx[0] = -1; 
		for(int i = 1, j = -1; i < m; ++i) {
			while(~j && t[j + 1] != t[i]) j = nx[j]; if(t[j + 1] == t[i]) ++j;
			nx[i] = j; 
		}
		for(int i = 0, j = -1; i < n; ++i) {
			while(~j && t[j + 1] != s[i]) j = nx[j]; if(t[j + 1] == s[i]) ++j;
			if(j == m - 1) P[i + 1].push_back(id), j = nx[j]; 
		}
	}
	inline void mian() {
		n = read(), m = read(), K = read(), id = read(); cin >> s;
		for(int i = 1; i <= n; ++i) w[i] = read();
		for(int i = 1; i <= m; ++i) {
			cin >> t[i] >> val[i] >> col[i];
			KMP(t[i], ln[i] = t[i].length(), i);
		}
		memset(dp, -0x3f, sizeof(dp)); for(int i = 0; i <= m; ++i) dp[0][i] = 0; ll ans = 0; 
		for(int i = 1; i <= n; ++i) {
			for(int j = 0; j <= m; ++j) dp[i][j] = dp[i - 1][j];
			int s = P[i].size(); if(!s) continue ; 
			std :: sort(P[i].begin(), P[i].end(), [](int x, int y) {return (col[x] ^ col[y]) ? col[x] < col[y] : ln[x] < ln[y];}); 
			for(int l = 0, r; l < s; l = r + 1) {
				r = l; while(r + 1 < s && col[P[i][r + 1]] == col[P[i][r]]) ++r; 
				ll c = 0; int f = col[P[i][l]]; 
				for(int j = l; j <= r; ++j) {
					int x = P[i][j]; c += w[i - ln[x] + 1] + val[x]; 
					chkmx(dp[i][f], dp[i - 1][f] + c); 
					for(int k = 0; k <= m; ++k) if(k != f) chkmx(dp[i][f], dp[max(0, i - ln[x] - K)][k] + c); 
				}
			}
		}
		for(int i = 0; i <= m; ++i) chkmx(ans, dp[n][i]); 
		cout << ans; 
	}
}

int main() 
{
	freopen("piano.in", "r", stdin); 
	freopen("piano.out", "w", stdout); 
	Solver :: mian(); 
	return 0; 
}   

---

B. 颜色限制（restriction）

题目简介

给定一个有 个结点 条无向边的图，每一条边有一个颜色（共 种），对每个颜色求出当该颜色的边都被删除后，整个图是否连通，是否是树。

数据范围：

线段树分治板板，但是没有看出来。

直接设颜色为 的边出现时间为 ，然后分治线段树维护可撤销并查集即可，查询连通只需要查祖先子树是否等于 ，如果是，再判断剩下的边数是否为 即可。

时间复杂度 。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXM=3e5+10;
int N,M,K,nowk;
int ans1,ans2,Col[MAXN];
bool ans[MAXN];
struct DSU
{
	int Rt[MAXN],Siz[MAXN];
	int Stk[MAXN],Top;
	inline void build(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(Rt[x]!=x) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
}Dsu;
struct Edges
{ int fr,to; }Ed[MAXM];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	std::vector<Edges>val;
}Tr[MAXN<<2];
void modifyAdd(int p,int l,int r,int id)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val.push_back(Ed[id]),void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyAdd(ls,l,r,id);
	if(mid<r) modifyAdd(rs,l,r,id);
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].val.clear();
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void solve(int p,int l,int r)
{
	int tp=Dsu.Top;
	for(auto x:Tr[p].val) Dsu.merge(x.fr,x.to);
	if(l==r)
	{
		// write(l,'\n');
		// for(int i=1;i<=N;++i) write(Dsu.Rt[i],' ');
		// puts("");
		ans[l]=Dsu.Siz[Dsu.getRt(1)]==N;
		Dsu.back(tp);
		return ;
	}
	int mid=(l+r)>>1;
	solve(ls,l,mid),solve(rs,mid+1,r);
	Dsu.back(tp);
}
int main()
{
	freopen("restriction.in","r",stdin);
	freopen("restriction.out","w",stdout);
	read(N,M,K);Dsu.build(N);
	build(1,1,K);
	for(int i=1,u,v,c;i<=M;++i)
	{
		read(u,v,c);++c;++Col[c];
		Ed[i]=(Edges){u,v};
		if(c>1) modifyAdd(1,1,c-1,i);
		if(c<K) modifyAdd(1,c+1,K,i);
	}
	solve(1,1,K);
	for(int k=1;k<=K;++k)
	{
		ans1+=ans[k];
		if(ans[k]) ans2+=(M-Col[k])==N-1;
	}
	write(ans1,' ',ans2,'\n');
	return 0;
}
/*

*/

---

C. wap（wap）

题目简介

给定序列 ，现在强制操作 次交换 ，最大化：

$$\sum_{i=1}^{n}|a_i-b_i|$$

数据范围：

发现 特别大，那么我们假定一定可以换到最优去，而之后我们只需要调整在最优解和次优解之间跳动即可。

我们考虑当前操作 ，原本的贡献为 ，交换后得到 ，那么当 的 同时小于 时一定不优。也就等效区间 不交，此时交换 会更优。增加 。那么我们将 分别排序求和即可。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x<0?-x:x; }
const int MAXN=5e5+10;
int N,K;
ll a[MAXN],b[MAXN],Maxi[MAXN],Mini[MAXN];
int main()
{
	freopen("wap.in","r",stdin);
	freopen("wap.out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) read(a[i]);
	for(int i=1;i<=N;++i) read(b[i]);
	if(N==2)
	{
		if(K&1) std::swap(a[1],a[2]);
		write(abs(a[1]-b[1])+abs(a[2]-b[2]));
		return 0;
	}
	ll ans=0;
	for(int i=1;i<=N;++i)
	{
		ans+=abs(a[i]-b[i]);
		Maxi[i]=std::max(a[i],b[i]);
		Mini[i]=std::min(a[i],b[i]);
	}
	std::sort(Maxi+1,Maxi+N+1),std::sort(Mini+1,Mini+N+1);
	for(int i=1;i<=N&&i<=K;++i) ans+=std::max(2ll*(Mini[N-i+1]-Maxi[i]),0ll);
	write(ans);
	return 0;
}
/*

*/

---

D. 防洪预警（rprfq）

题目简介

给定 个连续的位置，每个位置初始堆有 个 的方块，你可以向其中形如山谷的地方进行灌水，具体定义，存在 时，你可以在 处灌一个单位的水。要求维护 次操作：

• 区间加 ；
• 在 处都没有水的前提下，最多存在多少体积的水。

强制在线。

数据范围：

水的意义是填补所有的空缺，那么最后对于这个区间，一定会形成一个单峰，也就是由一段非严格单调递增和一段非严格单调递减构成，我们把这个单峰序列称为轮廓，所以我们得到了一个 的朴素做法。

考虑分块，维护每个块：

• 块端点及长度， 的和，最大值，及轮廓和；
• 轮廓的单调不降前缀和，单调不升后缀和；
• 区间加标记。

对于修改，可以直接暴力修改，复杂度 。

查询时，我们分别计算每个块内对答案的贡献和块间对答案的贡献。对于块内贡献，我们直接利用维护好的东西即可。对于块间贡献，如下图所示：

按照块内 最大值从大到小的顺序枚举每一个块。设当前正在枚举的块的 最大值为 ，如果这个块的左边（指这个块形成的轮廓的单调不降的那部分，下同）和这个块的右边（同理，指单调不升的那部分，下同）均被标记过，则直接跳过这个块（因为这个块对其他块的贡献一定被之前枚举到的某个块“覆盖”掉了）。

如果这个块的左边没被标记过，则我们从这个块开始向左遍历每个块，直到某个块的 。此时我们在相应的块的右边使用二分查找找到恰好 ，的位置并统计贡献（即上图中的蓝色部分），同时也要将从相应的块的右边到这个块的左边的所有部分都标记为已访问过。

同理，如果这个块的右边没被标记过，则我们需要向右遍历每个块并做类似操作。由于每一个块最多被访问一次，这部分的时间复杂度为 。当 时算法效率最优为 。

但这并不能完全解决这个问题，所以还需要进一步优化：

使用线段树代替分块，单侧递归维护：

• 块内 的最大值及其位置；
• 块内最大值左侧水的体积和右侧水的体积和。
• 块内 和。

考虑合并两个区间时，不妨设左区间最大值大于右区间最大值。此时大区间最大值左侧水体积一定是左区间的左侧水体积。考虑大区间的右侧水体积如何计算。

类似“楼房重建”，大区间的右侧水体积相当于原来左区间的右侧水体积被右区间最大值“挡住”了一下，于是可以在左区间上使用类似楼房重建的做法二分到恰好被右区间挡住的位置，这个位置前采用原来的右侧水体积，这个位置后被右区间最大值覆盖。

时间复杂度 。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=5e5+5,inf=1e18;
int ID_;
int n,m,T;
int a[N];
#define ls (d*2)
#define rs (d*2+1)
#define mid ((l+r)/2)
struct sgt{
	int len[N*4],sum[N*4],mx[N*4],tag[N*4],ans0[N*4],ans1[N*4];
	bool leaf[N*4];
	void f(int d,int nw){
		sum[d]+=len[d]*nw;
		mx[d]+=nw;
		tag[d]+=nw;
	}
	void pushdown(int d){
		if(tag[d]){
			f(ls,tag[d]);
			f(rs,tag[d]);
			tag[d]=0;
		}
	}
	int qval(int d,int nw,int op){
		if(leaf[d]){
			return max(nw,mx[d])-mx[d];
		}
		pushdown(d);
		if(!op){
			if(mx[ls]>nw){
				return ans0[d]-ans0[ls]+qval(ls,nw,op);
			}
			else{
				return nw*len[ls]-sum[ls]+qval(rs,nw,op);
			}
		}
		else{
			if(mx[rs]>nw){
				return ans1[d]-ans1[rs]+qval(rs,nw,op);
			}
			else{
				return nw*len[rs]-sum[rs]+qval(ls,nw,op);
			}
		}
	}
	void pushup(int d){
		mx[d]=max(mx[ls],mx[rs]);
		sum[d]=sum[ls]+sum[rs];
		ans0[d]=ans0[ls]+qval(rs,mx[ls],0);
		ans1[d]=ans1[rs]+qval(ls,mx[rs],1);
	}
	void build(int d,int l,int r){
		len[d]=r-l+1;
		if(l==r){
			leaf[d]=1;
			mx[d]=sum[d]=a[l];
			tag[d]=ans0[d]=ans1[d]=0;
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(d);
	}
	void add(int d,int l,int r,int nl,int nr,int nw){
		if(nl<=l && r<=nr){
			f(d,nw);
			return;
		}
		pushdown(d);
		if(nl<=mid){
			add(ls,l,mid,nl,nr,nw);
		}
		if(nr>mid){
			add(rs,mid+1,r,nl,nr,nw);
		}
		pushup(d);
	}
	int qmx(int d,int l,int r,int nl,int nr){
		if(nl<=l && r<=nr){
			return mx[d];
		}
		pushdown(d);
		int res=-inf;
		if(nl<=mid){
			res=max(res,qmx(ls,l,mid,nl,nr));
		}
		if(nr>mid){
			res=max(res,qmx(rs,mid+1,r,nl,nr));
		}
		return res;
	}
	int qpos(int d,int l,int r,int nl,int nr,int nw){
		if(nl<=l && r<=nr){
			if(mx[d]!=nw){
				return -1;
			}
			if(l==r){
				return l;
			}
		}
		pushdown(d);
		if(nl<=mid){
			int Get=qpos(ls,l,mid,nl,nr,nw);
			if(Get!=-1){
				return Get;
			}
		}
		return qpos(rs,mid+1,r,nl,nr,nw);
	}
	void qans(int d,int l,int r,int nl,int nr,int &nw,int &Ans,bool op){
		if(nl<=l && r<=nr){
			Ans+=qval(d,nw,op);
			nw=max(nw,mx[d]);
			return;
		}
		pushdown(d);
		if(!op){
			if(nl<=mid){
				qans(ls,l,mid,nl,nr,nw,Ans,op);
			}
			if(nr>mid){
				qans(rs,mid+1,r,nl,nr,nw,Ans,op);
			}
		}
		else{
			if(nr>mid){
				qans(rs,mid+1,r,nl,nr,nw,Ans,op);
			}
			if(nl<=mid){
				qans(ls,l,mid,nl,nr,nw,Ans,op);
			}
		}
	}
}Tr;
#undef ls
#undef rs
#undef mid
void Input(){
	cin>>ID_;
	cin>>n>>m>>T;
	rep(i,1,n){
		cin>>a[i];
	}
}
void solve(){
	Tr.build(1,1,n);
	int lst=0;
	rep(i,1,m){
		int op;cin>>op;
		if(op==1){
			int l,r,w;cin>>l>>r>>w;
			l^=lst,r^=lst;
			Tr.add(1,1,n,l,r,w);
		}
		else{
			int l,r;cin>>l>>r;
			l^=lst,r^=lst;
			int mx=Tr.qmx(1,1,n,l,r);
			int pos=Tr.qpos(1,1,n,l,r,mx);
			int w0=-inf,w1=-inf,ans=0;
			Tr.qans(1,1,n,l,pos,w0,ans,0);
			Tr.qans(1,1,n,pos,r,w1,ans,1);
			cout<<ans<<'\n';
			lst=ans*T;
		}
	}
}
signed main(){
	freopen("rprfq.in","r",stdin);
	freopen("rprfq.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	Input();
	solve();
	return 0;
}

---