Znzryb's Blog

P3567 [POI 2014] KUR-快递员（区间内有没有一个数出现次数超过一半）

Posted on 2025-05-27 Edited on 2026-04-06

思路讲解

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半。

AC代码

https://www.luogu.com.cn/record/218724261

源代码

// Problem: P3567 [POI 2014] KUR-Couriers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3567
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// 测试 https://www.luogu.com.cn/record/218615977 （只测了单次数据）
	// maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<int>(5e5)+7,maxm=static_cast<int>(5e5)+7;
	static const int LOGmxm=19;		// 这个版本次数一般也不会超过2**20，也就是1048576
	static const int maxn4=maxn*4+LOGmxm*maxn;
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	int arr[maxn],sum[maxn4];
	int n=0,m=0,idx=1,Cver=0,len=0;
	int li[maxn];	
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	inline void init(int ln,int lm){
		// int lmaxn4=ln*4+log2(ln)*lm+5;
		idx=1,n=ln,m=lm,Cver=0;
		root[0]=1;	// 版本0的根是1
	}
	inline int initLi(){	// 离散化操作
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p==L[node] && p==R[node]){
			return;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// 我们要查询是否有一个数出现次数超过一半
	int query(int u,int v,int l,int r,int k){
// #ifdef LOCAL
	// debug(u);
	// debug(L[u]);
	// debug(R[u]);
	// debug(sum[u]);
	// debug(v);
	// debug(L[v]);
	// debug(R[v]);
	// debug(sum[v]);
// 	
// #endif
		if(l==r){
			if(sum[v]-sum[u]>=k) return l;
			else return 0;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
// #ifdef LOCAL
    // debug(lsum);
    // debug(k);
    // cerr<<"\n";
// #endif
		int mid=l+r>>1;
		if(lsum>=k){
			return query(ls[u],ls[v],l,mid,k);
		}else{
			return query(rs[u],rs[v],mid+1,r,k);
		}
	}
};

persisTree tr;

inline void solve(){
	// N=read(),M=read();
	scanf("%lld%lld",&N,&M);
	// cin>>N>>M;
	tr.init(N,N);
	FOR(i,1,N){
		// tr.arr[i]=read();
		scanf("%d",&tr.arr[i]);
	}
	int len=tr.initLi();
	tr.build(1,1,len);
	FOR(i,1,N){
		tr.add(tr.root[i-1],i-1,tr.kth(tr.arr[i]),1);
	}
	FOR(_,1,M){
		// ll l=read(),r=read();
		ll l,r;
		scanf("%lld%lld",&l,&r);
		ll mid=(r-l+1)/2+1;
// #ifdef LOCAL
    // debug(mid);
// #endif
		int ans=tr.li[tr.query(tr.root[l-1],tr.root[r],1,len,mid)];
		// write(ans);
		// putchar('\n');
		// cout<<ans<<"\n";
		printf("%d\n",ans);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/218724163

1 1
1
1 1

*/

心路历程（WA，TLE，MLE……）

我超，这个POI的数据还是挺严格的，我的这个主席树codeforces和洛谷模版都过了，就这道题目没有过。

1
2
3

1 1
1
1 1

黑体部分，要放在比较下面，不要放在版本更新的上面，否则可能未版本更新就出去了。

// 处理静态区间第 k 小问题中，因为权值线段树，x=1
void add(int node,int ver,int p,ll x){ 	
	clone(node);
	sum[idx]+=x;
	// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
	if(root[ver]==node){	
		++Cver;
		root[Cver]=idx;
	}
	if(p==L[node] && p==R[node]){
		return;
	}
	if(p>=L[ls[node]] && p<=R[ls[node]]){
		int nals=ls[idx];
		ls[idx]=idx+1;
		add(nals,ver,p,x);
	}else{
		int nars=rs[idx];
		rs[idx]=idx+1;
		add(nars,ver,p,x);
	}
}

P3834 【模板】可持久化线段树 2

Posted on 2025-05-26 Edited on 2026-04-06

思路讲解

主要参考这段代码

https://github.com/algorithmzuo/algorithm-journey/blob/main/src/class157/Code02_PointPersistent2.java

参考题解

【算法讲解157【挺难】可持久化线段树和标记永久化】【精准空降到 45:11】 https://www.bilibili.com/video/BV1bSc6eREi4/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=2711

AC代码

https://www.luogu.com.cn/record/218615977

源代码

// Problem: P3834 【模板】可持久化线段树 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3834
// Memory Limit: 1 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
/*

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// // maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<ll>(2e5)+7,maxm=static_cast<ll>(2e5)+7;
	static const int maxn4=maxn*22;		// 这个版本次数一般也不会超过int，给个32绝对够了
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	ll arr[maxn],sum[maxn4];
	int n=0,m=0,idx=1,Cver=0,len=0;
	ll li[maxn];	
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	// vector<int> ls,rs,L,R,root,arr,li;	// 因为主席树这些数是不能复用的，我们直接就用动态数组吧。
	// persisTree(int ln,int lm){
		// n=ln,m=lm;
		// ll siz=n*4+log2(n)*m+7;
		// ls.resize(siz),rs.resize(siz),L.resize(siz),R.resize(siz),root.resize(siz);
		// arr.resize(siz);
	// }
	inline void init(int ln,int lm){
		// int lmaxn4=ln*4+log2(ln)*lm+5;
		idx=1,n=ln,m=lm,Cver=0;
		// for(int i=0;i<=lmaxn4;++i){	// 有build在，init不用干这个事情
			// ls[i]=0,rs[i]=0;
			// sum[i]=0,L[i]=0,R[i]=0;
		// }
		// for(int i=0;i<=lm;++i){
			// root[i]=0,arr[i]=0;
		// }
		root[0]=1;	// 版本0的根是1
	}
	inline int initLi(){	// 离散化操作
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		if(p==L[node] && p==R[node]){
			return;
		}
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// u v 为node，l，r为区间，k为区间第k小
	int query(int u,int v,int l,int r,int k){
		if(l==r){
			return l;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
		int mid=l+r>>1;
		if(lsum>=k){
			return query(ls[u],ls[v],l,mid,k);
		}else{
			return query(rs[u],rs[v],mid+1,r,k-lsum);
		}
	}
};

inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void write(ll x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}

persisTree tr;	// 由于太大了，该结构体只能声明与全局变量作用域

inline void solve(){
	N=read(),M=read();
	tr.init(N,N);
	FOR(i,1,N){
		tr.arr[i]=read();
	}
	int len=tr.initLi();
// #ifdef LOCAL
    // cerr << "build 1" << '\n';
// #endif
	tr.build(1,1,len);
// #ifdef LOCAL
    // cerr << "build 2" << '\n';
// #endif
	FOR(i,1,N){
		// 权值线段树单点加
		tr.add(tr.root[tr.Cver],tr.Cver,tr.kth(tr.arr[i]),1);
// #ifdef LOCAL
	// debug(tr.kth(tr.arr[i]));
    // FOR(i,1,tr.idx){
    	// cerr<<i<<" L:"<<tr.L[i]<<" R:"<<tr.R[i]<<" sum:"<<tr.sum[i]<<"\n";
    // }
    // cerr<<"\n";
// #endif
// #ifdef LOCAL
    // debug(i);
// #endif
	}
// #ifdef LOCAL
    // cerr << "success add" << '\n';
// #endif
	FOR(_,1,M){
		ll l=read(),r=read(),k=read();
		// 这个l,r是权值线段树中的值域，所以初始传入【1，2】
		ll ans=tr.query(tr.root[l-1],tr.root[r],1,len,k);
		write(tr.li[ans]),putchar('\n');
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/218615977
*/

心路历程（WA，TLE，MLE……）

https://www.luogu.com.cn/record/218612872

这个 k-lsum 要小心，记得要加，因为往r走相当于抛掉了一些东西

// u v 为node，l，r为区间，k为区间第k小
int query(int u,int v,int l,int r,int k){
	if(l==r){
		return l;
	}
	// 我们这样就知道了
	int lsum=sum[ls[v]]-sum[ls[u]];
	int mid=l+r>>1;
	if(lsum>=k){
		return query(ls[u],ls[v],l,mid,k);
	}else{    // 这个 k-lsum 要小心，记得要加，因为往r走相当于抛掉了一些东西
		return query(rs[u],rs[v],mid+1,r,k-lsum);
	}
}

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 P12594 炽声音节旋

Posted on 2025-05-26 Edited on 2026-04-06

思路讲解

字符串转化为数字函数（stoi）的使用。

https://en.cppreference.com/w/cpp/string/basic_string/stol

AC代码

源代码

心路历程（WA，TLE，MLE……）

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 H P12597 穿睡衣军训

Posted on 2025-05-25 Edited on 2026-04-06

思路讲解

子序列自动机，最重要的是next数组，可以找到从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)

struct seqAuto{	// 子序列自动机 subsequence automaton 
	// 可以处理大小写字母，数字，但是可能要改一下base以及next
	vector<vector<int>> next;
	// 从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)
	char base='a';
	seqAuto(const string &s){
		next.assign(SZ(s)+5,vector<int>(28,-1));
		ROF(i,SZ(s)-1,0){
			FOR(j,0,26){
				next[i][j]=next[i+1][j];
			}
			next[i][s[i]-base]=i;
		}
	}
	inline bool isFind(const string &s){	// 传入substr时，必须为const属性
		ll idx=0;
		FOR(i,0,SZ(s)-1){
			if(next[idx][s[i]-base]!=-1){
				idx=next[idx][s[i]-base]+1;
			}else{
				return false;
			}
		}
		return true;
	}
};

然后用双指针方式枚举子串

FOR(i,0,SZ(S)-1){	// 双指针
	FOR(j,bp,SZ(S)){
		assert(j>=i);
		ll len=j-i;
		if(!sat.isFind(S.substr(i,len))){	// pos,len
			bp=j;
			if(ans.empty() || len-1>SZ(ans.back())){
				ans.clear();
				ans.pb(S.substr(i,len-1));
			}else if(len-1==SZ(ans.back()) ){
				ans.pb(S.substr(i,len-1));
			}
			break;
		}
	}
}

AC代码

https://www.luogu.com.cn/record/218545124

源代码

// Problem: P12597 穿睡衣军训
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P12597
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
struct seqAuto{	// 子序列自动机 subsequence automaton 
	// 可以处理大小写字母，数字，但是可能要改一下base以及next
	vector<vector<int>> next;
	// 从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)
	char base='a';
	seqAuto(const string &s){
		next.assign(SZ(s)+5,vector<int>(28,-1));
		ROF(i,SZ(s)-1,0){
			FOR(j,0,26){
				next[i][j]=next[i+1][j];
			}
			next[i][s[i]-base]=i;
		}
	}
	inline bool isFind(const string &s){	// 传入substr时，必须为const属性
		ll idx=0;
		FOR(i,0,SZ(s)-1){
			if(next[idx][s[i]-base]!=-1){
				idx=next[idx][s[i]-base]+1;
			}else{
				return false;
			}
		}
		return true;
	}
};

inline void solve(){
	string S,T;
	cin>>S>>T;
	seqAuto sat(T);
	ll bp=0;
	vector<string> ans;
	S+=('z'+1);
	FOR(i,0,SZ(S)-1){	// 双指针
		FOR(j,bp,SZ(S)){
			assert(j>=i);
			ll len=j-i;
			if(!sat.isFind(S.substr(i,len))){	// pos,len
				bp=j;
				if(ans.empty() || len-1>SZ(ans.back())){
					ans.clear();
					ans.pb(S.substr(i,len-1));
				}else if(len-1==SZ(ans.back()) ){
					ans.pb(S.substr(i,len-1));
				}
				break;
			}
		}
	}
	sort(all(ans));
	cout<<ans[0]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/218545015
*/

心路历程（WA，TLE，MLE……）

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 F P12595 出生于驾校（线段树加减乘除懒标记思想）

Posted on 2025-05-25 Edited on 2026-04-06

思路讲解

使用递推方法加快Sum预处理速度。

递推代码。

ROF(k,log2(N)-1,0){  // 
	FOR(i,0,pow2[k]-1){
		// assert(pow2[k]+i<SZ(Sum[k+1]));
		Sum[k][i]=Sum[k+1][i]+Sum[k+1][pow2[k]+i];
		Sum[k][i]%=mod;
		Cnt[k][i]=Cnt[k+1][i]+Cnt[k+1][pow2[k]+i];
	}
}

AC代码

https://www.luogu.com.cn/record/218505364

源代码

// Problem: T610807 出生于驾校
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T610807?contestId=245376
// Memory Limit: 2 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(4e7)+10,INF=static_cast<ll>(1e18)+3;
constexpr int mod=998244353;
constexpr double eps=1e-8;

ll N,M,Q,K,T;
int minK, maxK;
/*

*/
typedef uint32_t ui;
ui X, Y, Z;

inline ui nextInt(ui &x = X, ui &y = Y, ui &z = Z) {
  x ^= y << (z & 31);
  y ^= z >> (x & 31);
  z ^= x << (y & 31);
  x ^= x >> 5; y ^= y << 17; z ^= z >> 6;
  return x;
}

const int lim = 998244353;
// inline std::vector<int> genArr(int n) {
  // std::vector<int> ret(n);
  // for (int i = 0; i < n; ++i) ret[i] = nextInt() % lim;
  // return ret;
// }
ll pow2[90];
vector<int> Sum[32],Cnt[32];
ll A[MAXN];

inline void solve(){
	cin>>N>>Q>> minK >> maxK;
	cin>>X>>Y>>Z;
	// A=genArr(N);	// 这样子效率其实会慢一点，直接上静态数组会快一点
	FOR(i,0,N-1){
		A[i]=nextInt() % lim;
	}
	FOR(i,0,log2(N)){	
		Sum[i].resize(pow2[i]+5,0);
		Cnt[i].resize(pow2[i]+5,0);
	}
	// 我们需要讲这个优化到 O(n+logn) 那么其实也就是O(n)
	ll mxk=log2(N);
	FOR(idx,0,N-1){		
		ll midx=idx%pow2[mxk];
		if(midx<0) midx+=pow2[mxk];
		Sum[mxk][midx]+=A[idx];
		Sum[mxk][midx]%=mod;
		++Cnt[mxk][midx];
	}
	ROF(k,log2(N)-1,0){
		FOR(i,0,pow2[k]-1){
			// assert(pow2[k]+i<SZ(Sum[k+1]));
			Sum[k][i]=Sum[k+1][i]+Sum[k+1][pow2[k]+i];
			Sum[k][i]%=mod;
			Cnt[k][i]=Cnt[k+1][i]+Cnt[k+1][pow2[k]+i];
		}
	}
	
	ll ans=0,addRec=0,mulRec=1;
	FOR(_,1,Q){
		int op = nextInt() % 3 + 1;
		if(op==1){
			int x = nextInt() % lim;
			addRec+=x;addRec%=mod;
		}else if(op==2){
			int x = nextInt() % lim;
			mulRec*=x;mulRec%=mod;
			addRec*=x;addRec%=mod;
		}else{
			int k = nextInt() % (maxK - minK + 1) + minK;
      		int p = nextInt() % (1 << k);
      		ll lans=0;
      		lans=(Sum[k][p]*mulRec+addRec*Cnt[k][p])%mod;
      		ans^=lans;
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	pow2[0]=1;
	FOR(i,1,40){
		pow2[i]=2*pow2[i-1];
	}
	solve();
	return 0;
}
/*
AC https://www.luogu.com.cn/record/218505364
*/

心路历程（WA，TLE，MLE……）

赛时因为没有采用递推所以代码比较慢。