【题解】蓝桥算法双周赛 第一场

D. 健身

题意：在未来 \(1\sim n\) 天中可以安排健身计划。有 \(m\) 个健身计划，第 \(i\) 个计划需要连续的 \(2^{k_i}\) 天，增益为 \(s_i\)。一个计划可以多次完成并获得多次增益，但一天不能同时进行多个计划。在 \(1\sim n\) 天中有 \(q\) 天有其它安排，不能健身。问能获得的最大增益。

\(1\le q\le n \le 2\times 10^5\)，\(1\le m \le 50\)，\(1\le s_i \le 10^9\)，\(0\le k \le 20\)。

对于相同的 \(k\)，显然只需要保留增益最大的 \(s_i\)。

令 \(w_k\) 表示锻炼 \(2^k\) 天能得到的最大增益值。

令 \(dp_i\) 表示锻炼到 \(i\) 天可以得到的最大增益，那么： \[dp_i=\max(dp_{i-1},dp_{i-2^k}+w_k)\] 转移的前提是第 \(i-2^k+1\) 天到第 \(i\) 天必须空闲。

判断一段时间是否空闲可以用前缀和 \(O(1)\) 判断。

时间复杂度 \(O(nk)\)。

Code

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;


void solve()
{
	int n=read(),m=read(),q=read();
	vector<int> sum(n+1);
	for(int i=1;i<=q;++i) {
		int x=read();
		sum[x]++;
	}
	for(int i=1;i<=n;++i) {
		sum[i]+=sum[i-1];
	}
	vector<int> val(30);
	for(int i=1;i<=m;++i) {
		int k=read(),s=read();
		val[k]=max(val[k],s);
	}
	vector<int> dp(n+1);
	for(int i=1;i<=n;++i) {
		dp[i]=dp[i-1];
		for(int k=0;k<22;++k) {
			int step=1<<k;
			if(i-step>=1 && sum[i]-sum[i-step]==0) {
				dp[i]=max(dp[i],dp[i-step]+val[k]);
			}
		}
	}
	printf("%lld\n",dp[n]);
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}

E. 契合匹配

题意：用一个首尾相接的由英文字母组成的字符串表示一个齿轮。两个齿轮是契合的当且仅当每个对应位是同一个字母的大小写，如 AbCDeFgh 和 aBcdEfGH 。齿轮是环形的，问第一个齿轮 \(S\) 至少旋转多少位能与第二个齿轮 \(T\) 完全契合，或无论如何都不能契合。

\(1\le |S|,|T|\le 10^6\)。

套路：破环成链。

以题例为例，\(S=\text{AbCDeFgh}\)，延长一倍后变成 \(S=\text{AbCDeFghAbCDeFgh}\)。

另外，可以将 \(S\) 大小写反转，变成纯粹的字符串匹配问题，如反转后：

\(S=\text{aBcdEfGHaBcdEfGH}\)，\(T=\text{aBcdEfGH}\)

那么假设 \(T\) 在 \(S\) 中出现的首位为 \(p\)，则 \(ans=\min(p-1,n-p+1)\)。

利用 KMP 算法匹配字符串，时间复杂度 \(O(n)\)。

Code

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;


void solve()
{
	int n=read();
	string a,b;
	cin>>a>>b;
	a+=a;
	for(int i=0;i<a.size();++i) {
		if(islower(a[i])) {
			a[i]=toupper(a[i]);
		} else {
			a[i]=tolower(a[i]);
		}
	}
	// find b in a
	vector<int> ans;
	auto KMP = [&] (string a,string b) {
		int ha=a.size();
		int hb=b.size();
		if(a[0]==' ') {
			ha--;
		} else {
			a=' '+a;
		}
		if(b[0]==' ') {
			hb--;
		} else {
			b=' '+b;
		}
		vector<int> nxt(hb+1);
		for(int i=2,p=0;i<=hb;++i) {
			while(p && b[i]!=b[p+1]) {
				p=nxt[p];
			}
			if(b[i]==b[p+1]) {
				p++;
			}
			nxt[i]=p;
		}
		for(int i=1,p=0;i<=ha;++i) {
			while(p && a[i]!=b[p+1]) {
				p=nxt[p];
			}
			if(a[i]==b[p+1]) {
				p++;
			}
			if(p==hb) {
				ans.push_back(i-hb+1);
				p=nxt[p];
			}
		}
		return nxt;
	};
	KMP(a,b);
	if(ans.empty()) {
		puts("No");
		return ;
	}
	puts("Yes");
	int res=inf;
	for(auto k:ans) {
		res=min(res,k-1);
		res=min(res,n-(k-1));
	}
	printf("%lld\n",res);
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}

F. 奇怪的线段

题意：数轴上给定 \(n\) 个线段 \([l_i,r_i]\)。\(q\) 次询问两个点 \(a,b\) 问有多少个线段包含 \(a\) 而不含 \(b\)。

\(1\le n,q,a_i,b_i \le 2 \times 10^5\)，\(1\le l_i < r_i \le 2\times 10^5\)。

先考虑只有条件 “ 有多少个线段包含 \(a\) ” 怎么做。

用一个 vector 存以 \(i\) 为左端点的线段的右端点是哪些。

从左到右扫，每遇到一个左端点就把右端点插进线段树（单点加一），每遇到一个右端点就把该点从线段树中删掉（单点减一），遇到 \(a\) 时查询线段树中的节点数量（区间求和）就是答案。

ps. 数轴上的一个点可能是多个线段的左/右端点，所以实际上我们是减去对应 vector 的大小。

但现在是 " 包含 \(a\) 而不包含 \(b\) " 。

改进方法是：查询局部区间和而不是全局区间和。

具体的：

1. 如果 \(a=b\)，答案为 \(0\) 。
2. 如果 \(a<b\)，从左到右扫描，遇到左端点把右端点插进线段树；遇到右端点则将右端点从线段树中移除，扫描到 \(a\) 时，查询 \([a,b)\) 区间和即为答案。
3. 如果 \(a>b\)，从右到左扫描，遇到右端点把左端点插进线段树；遇到左端点则将左端点从线段树中移除，扫描到 \(a\) 时，查询 \((b,a]\) 区间和即为答案。

预处理出 \(2,3\) 两种情况对应的询问，扫两次即可。

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

Code 线段树版本

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;

struct SegmentTree {
	int n,modp;
	vector<int> tree;
	vector<int> lazy_add;
	vector<int> lazy_mul;
	SegmentTree(int size,int MOD = LLONG_MAX) {
		n = size;
		modp = MOD;
		tree.resize(4*n+1,0);
		lazy_add.resize(4*n+1,0);
		lazy_mul.resize(4*n+1,1);
	}
	inline void pushup(int p) {
		tree[p] = (tree[p<<1] + tree[p<<1|1]) % modp;
	}
	inline void pushdown(int p,int left,int right) {
		if(lazy_mul[p]!=1) {
			lazy_mul[p<<1]   = lazy_mul[p<<1]   * lazy_mul[p] % modp;
			lazy_mul[p<<1|1] = lazy_mul[p<<1|1] * lazy_mul[p] % modp;
			lazy_add[p<<1]   = lazy_add[p<<1]   * lazy_mul[p] % modp;
			lazy_add[p<<1|1] = lazy_add[p<<1|1] * lazy_mul[p] % modp;
			tree[p<<1]       = tree[p<<1]       * lazy_mul[p] % modp;
			tree[p<<1|1]     = tree[p<<1|1]     * lazy_mul[p] % modp;
			lazy_mul[p] = 1;	
		}
		if(lazy_add[p]) {
			int mid = left + right >> 1;
			lazy_add[p<<1]   = (lazy_add[p<<1]   + lazy_add[p]) % modp;
			lazy_add[p<<1|1] = (lazy_add[p<<1|1] + lazy_add[p]) % modp;			
			tree[p<<1]       = (tree[p<<1]   + (mid-left+1)  * lazy_add[p] % modp) % modp;
			tree[p<<1|1]     = (tree[p<<1|1] + (right-mid)   * lazy_add[p] % modp) % modp;
			lazy_add[p] = 0;
		}
	}
	void in_build(int p,int left,int right,vector<int> &nums) {
		if(left == right) {
			tree[p] = nums[left];
		} else {
			int mid = left + right >> 1;
			in_build(p<<1,left,mid,nums);
			in_build(p<<1|1,mid+1,right,nums);
			pushup(p);
		}
	}
	void submit_change(int p, int left, int right, vector<int> &nums) {
    	if (left == right) {
        	nums[left] += tree[p];
    	} else {
        	pushdown(p,left,right);
        	int mid = left + right >> 1;
        	submit_change(p<<1,left,mid,nums);
        	submit_change(p<<1|1,mid+1,right,nums);
        	pushup(p);
    	}
	}
	void update_add(int p,int left,int right,int ql,int qr,int val) {
		if(ql <= left && qr >= right) {
			tree[p]     = (tree[p]     + (right-left+1) * val % modp) % modp;
			lazy_add[p] = (lazy_add[p] + val) % modp;
		} else {
			pushdown(p,left,right);
			int mid = left + right >> 1;
			if(ql <= mid) update_add(p<<1,left,mid,ql,qr,val);
			if(qr > mid) update_add(p<<1|1,mid+1,right,ql,qr,val);
			pushup(p);
		}
	}
	void update_mul(int p,int left,int right,int ql,int qr,int val) {
		if(ql <= left && qr >= right) {
			tree[p]     = tree[p]     * val % modp;
			lazy_add[p] = lazy_add[p] * val % modp;
			lazy_mul[p] = lazy_mul[p] * val % modp;
		} else {
			pushdown(p,left,right);
			int mid = left + right >> 1;
			if(ql <= mid) update_mul(p<<1,left,mid,ql,qr,val);
			if(qr > mid) update_mul(p<<1|1,mid+1,right,ql,qr,val);
			pushup(p);
		}
	}
	void update_change(int p,int left,int right,int ql,int qr,int val) {
        if (ql <= left && qr >= right) {
            tree[p] = (val * (right - left + 1)) % modp;
            lazy_add[p] = val;
            lazy_mul[p] = 0;
        } else {
            pushdown(p,left,right);
            int mid = left + right >> 1;
            if (ql <= mid) update_change(p<<1,left,mid,ql,qr,val);
            if (qr > mid) update_change(p<<1|1,mid+1,right,ql,qr,val);
            pushup(p);
        }
    }
	int range_query(int p,int left,int right,int ql,int qr) {
		if(ql <= left && qr >= right) {
			return tree[p] % modp;
		}
		pushdown(p,left,right);
		int mid = left + right >> 1;
		int res = 0;
		if(ql <= mid) res = (res + range_query(p<<1,left,mid,ql,qr) ) % modp;
		if(qr > mid) res = (res + range_query(p<<1|1,mid+1,right,ql,qr) ) % modp;
		return res;
	}
	void build(vector<int> &nums) {
		in_build(1,1,n,nums);
	}
	void submit(vector<int> &nums) {
    	submit_change(1,1,n,nums);
    }
	void add(int ql,int qr,int val) {
		update_add(1,1,n,ql,qr,val);
	}
	void mul(int ql,int qr,int val) {
		update_mul(1,1,n,ql,qr,val);
	}
	void change(int ql, int qr, int val) {
        update_change(1,1,n,ql,qr,val);
    }
	int query(int ql,int qr) {
		return range_query(1,1,n,ql,qr);
	}
};
const int N = 2e5+10;

void solve()
{
	int n=read(),q=read();
	vector<vector<int>> pl(N),pr(N);
	for(int i=1;i<=n;++i) {
		int l=read(),r=read();
		pl[r].push_back(l);
		pr[l].push_back(r);
	}

	vector<array<int,3>> ql,qr;
	vector<int> ans(q+1);
	for(int i=1;i<=q;++i) {
		int a=read(),b=read();
		if(a<b) {
			ql.push_back({a,b,i});
		} else if(a>b) {
			qr.push_back({a,b,i});
		}
	}

	SegmentTree segl(N);
	vector<int> tmp(N);
	segl.build(tmp);
	sort(ql.begin(),ql.end());
	int pos=1;
	for(auto [a,b,id]:ql) {
		for(int i=pos;i<=a;++i) {
			for(auto k:pr[i]) {
				segl.add(k,k,1);
			}
			segl.add(i,i,-pl[i].size());
		}
		pos=a+1;
		segl.add(a,a,pl[a].size());
		ans[id]=segl.query(a,b-1);
		segl.add(a,a,-pl[a].size());
	}

	SegmentTree segr(N);
	segr.build(tmp);
	sort(qr.begin(),qr.end());
	reverse(qr.begin(),qr.end());
	pos=2e5;
	for(auto [a,b,id]:qr) {
		for(int i=pos;i>=a;--i) {
			for(auto k:pl[i]) {
				segr.add(k,k,1);
			}
			segr.add(i,i,-pr[i].size());
		}
		pos=a-1;
		segr.add(a,a,pr[a].size());
		ans[id]=segr.query(b+1,a);
		segr.add(a,a,-pr[a].size());
	}

	for(int i=1;i<=q;++i) {
		printf("%lld\n",ans[i]);
	}
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}

Code 树状数组版本

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;

struct Fenwick {
	int n;
	vector<int> tr;
	Fenwick() {}
	Fenwick(int n) {init(n+1);}
	void init(int n){
		this->n = n;
		tr.assign(n+1,0);
	}
	void add(int pos,int x){
		while(pos<=n){
			tr[pos]+=x;
			pos+=pos&-pos;
		}
	}
	int sum(int pos){
		int res=0;
		while(pos){
			res+=tr[pos];
			pos-=pos&-pos;
		}
		return res;
	}
	int rangeSum(int l,int r){
		return sum(r)-sum(l-1);
	}
	int kth(int k){
		// tr[x] count the cnt of x
		int res=0,cnt=0;
		for(int i=20;i>=0;--i){
			res+=(1<<i);
			if(res>n || cnt+tr[res]>=k){
				res-=(1<<i);
			} else {
				cnt+=tr[res];
			}
		}
		return res+1;
	}
};

const int N = 2e5+10;

void solve()
{
	int n=read(),q=read();
	vector<vector<int>> pl(N),pr(N);
	for(int i=1;i<=n;++i) {
		int l=read(),r=read();
		pl[r].push_back(l);
		pr[l].push_back(r);
	}

	vector<array<int,3>> ql,qr;
	vector<int> ans(q+1);
	for(int i=1;i<=q;++i) {
		int a=read(),b=read();
		if(a<b) {
			ql.push_back({a,b,i});
		} else if(a>b) {
			qr.push_back({a,b,i});
		}
	}

	Fenwick fenl(N);
	sort(ql.begin(),ql.end());
	int pos=1;
	for(auto [a,b,id]:ql) {
		for(int i=pos;i<=a;++i) {
			for(auto k:pr[i]) {
				fenl.add(k,1);
			}
			fenl.add(i,-pl[i].size());
		}
		pos=a+1;
		fenl.add(a,pl[a].size());
		ans[id]=fenl.rangeSum(a,b-1);
		fenl.add(a,-pl[a].size());
	}

	Fenwick fenr(N);
	sort(qr.begin(),qr.end());
	reverse(qr.begin(),qr.end());
	pos=2e5;
	for(auto [a,b,id]:qr) {
		for(int i=pos;i>=a;--i) {
			for(auto k:pl[i]) {
				fenr.add(k,1);
			}
			fenr.add(i,-pr[i].size());
		}
		pos=a-1;
		fenr.add(a,pr[a].size());
		ans[id]=fenr.rangeSum(b+1,a);
		fenr.add(a,-pr[a].size());
	}

	for(int i=1;i<=q;++i) {
		printf("%lld\n",ans[i]);
	}
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}