【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 F P12595 出生于驾校（线段树加减乘除懒标记思想） · znzryb
## 思路讲解
使用递推方法加快Sum预处理速度。
递推代码。
```cpp
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](https://www.luogu.com.cn/record/218505364)
::: 源代码
```cpp
// 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……）
赛时因为没有采用递推所以代码比较慢。