关于 memset 的一些小问题
- 板块学术版
- 楼主Withershine
- 当前回复3
- 已保存回复3
- 发布时间2024/1/28 21:28
- 上次更新2024/1/29 01:23:52
查看原帖
被骇客银狼阻止的越权访问保存失败
关于 memset 的一些小问题
在写 P3373 【模板】线段树 2 时我用了分块算法，有一份 0 分代码是这样的：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
ll n , q , m , a[200005] , opt , x , y , k;
ll cnt1[200005] , cnt2[200005] , sum[200005];
ll L[200005] , R[200005] , block , pos[200005];
inline void build()
{
ll ql = sqrt(n);
block = n / ql;
fr(i , 1 , block)
{
L[i] = R[i - 1] + 1;
R[i] = i * ql;
}
if(R[block] != n)
{
block++;
L[block] = R[block - 1] + 1;
R[block] = n;
}
fr(i , 1 , block)
{
fr(j , L[i] , R[i])
{
pos[j] = i;
sum[i] += a[j];
cnt1[j] = 1;
}
}
}
inline void reset(ll x)
{
fr(i , L[x] , R[x])
{
a[i] = (a[i] * cnt1[x] + cnt2[x]) % m;
}
cnt1[x] = 1;
cnt2[x] = 0;
}
inline void update1(ll l , ll r , ll d)
{
ll p = pos[l] , q = pos[r];
if(p == q)
{
reset(p);
fr(i , l , r)
{
sum[p] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
return ;
}
reset(p);
fr(i , l , R[p])
{
sum[p] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
reset(q);
fr(i , L[q] , r)
{
sum[q] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
fr(i , p + 1 , q - 1)
{
sum[i] = sum[i] * d % m;
cnt1[i] = cnt1[i] * d % m;
cnt2[i] = cnt2[i] * d % m;
}
}
inline void update2(ll l , ll r , ll d)
{
ll p = pos[l] , q = pos[r];
if(p == q)
{
reset(p);
fr(i , l , r)
{
a[i] += d;
sum[p] = (sum[p] + d) % m;
}
return ;
}
reset(p);
fr(i , l , R[p])
{
a[i] += d;
sum[p] = (sum[p] + d) % m;
}
reset(q);
fr(i , L[q] , r)
{
a[i] += d;
sum[q] = (sum[q] + d) % m;
}
fr(i , p + 1 , q - 1)
{
sum[i] = (sum[i] + (R[i] - L[i] + 1) * d % m) % m;
cnt2[i] += d;
}
}
inline ll ququ(ll l , ll r)
{
ll p = pos[l] , q = pos[r] , kkk = 0;
if(p == q)
{
fr(i , l , r)
{
kkk = (kkk + a[i] * cnt1[p] % m + cnt2[p]) % m;
}
return kkk % m;
}
fr(i , l , R[p])
{
kkk = (kkk + a[i] * cnt1[p] % m + cnt2[p]) % m;
}
fr(i , L[q] , r)
{
kkk = (kkk + a[i] * cnt1[q] % m + cnt2[q]) % m;
}
fr(i , p + 1 , q - 1)
{
kkk = (kkk + sum[i]) % m;
}
return kkk % m;
}
inline void test1()
{
fr(i , 1 , n)
{
cout << a[i] << ' ';
}
cout << '\n';
fr(i , 1 , n)
{
cout << pos[i] << ' ';
}
cout << '\n';
fr(i , 1 , block)
{
cout << "block:" << i << ' ' << L[i] << ' ' << R[i] << '\n';
}
fr(i , 1 , block)
{
cout << sum[i] << ' ';
}
cout << '\n' << "cnt1\n";
fr(i , 1 , block)
{
cout << cnt1[i] << ' ';
}
cout << '\n' << "cnt2" << '\n';
fr(i , 1 , block)
{
cout << cnt2[i] << ' ';
}
cout << '\n';
}
signed main()
{
// freopen("in.in" , "r" , stdin);
// freopen("out.out" , "w" , stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q >> m;
fr(i , 1 , n)
{
cin >> a[i];
}
build();
memset(cnt1 , 1 , sizeof(cnt1));
while(q--)
{
cin >> opt;
if(opt == 1)
{
cin >> x >> y >> k;
update1(x , y , k);
}
else if(opt == 2)
{
cin >> x >> y >> k;
update2(x , y , k);
}
else
{
cin >> x >> y;
cout << ququ(x , y) << '\n';
}
}
return 0;
}
还有一份 AC 代码是这样的：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
ll n , q , m , a[200005] , opt , x , y , k;
ll cnt1[200005] , cnt2[200005] , sum[200005];
ll L[200005] , R[200005] , block , pos[200005];
inline void build()
{
ll ql = sqrt(n) * 2 / 3;
block = n / ql;
fr(i , 1 , block)
{
L[i] = R[i - 1] + 1;
R[i] = i * ql;
}
if(R[block] != n)
{
block++;
L[block] = R[block - 1] + 1;
R[block] = n;
}
fr(i , 1 , block)
{
fr(j , L[i] , R[i])
{
pos[j] = i;
sum[i] += a[j];
cnt1[j] = 1;
}
}
}
inline void reset(ll x)
{
fr(i , L[x] , R[x])
{
a[i] = (a[i] * cnt1[x] + cnt2[x]) % m;
}
cnt1[x] = 1;
cnt2[x] = 0;
}
inline void update1(ll l , ll r , ll d)
{
ll p = pos[l] , q = pos[r];
if(p == q)
{
reset(p);
fr(i , l , r)
{
sum[p] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
return ;
}
reset(p);
fr(i , l , R[p])
{
sum[p] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
reset(q);
fr(i , L[q] , r)
{
sum[q] += (d - 1) * a[i] % m;
a[i] = a[i] * d % m;
}
fr(i , p + 1 , q - 1)
{
sum[i] = sum[i] * d % m;
cnt1[i] = cnt1[i] * d % m;
cnt2[i] = cnt2[i] * d % m;
}
}
inline void update2(ll l , ll r , ll d)
{
ll p = pos[l] , q = pos[r];
if(p == q)
{
reset(p);
fr(i , l , r)
{
a[i] += d;
sum[p] = (sum[p] + d) % m;
}
return ;
}
reset(p);
fr(i , l , R[p])
{
a[i] += d;
sum[p] = (sum[p] + d) % m;
}
reset(q);
fr(i , L[q] , r)
{
a[i] += d;
sum[q] = (sum[q] + d) % m;
}
fr(i , p + 1 , q - 1)
{
sum[i] = (sum[i] + (R[i] - L[i] + 1) * d % m) % m;
cnt2[i] += d;
}
}
inline ll ququ(ll l , ll r)
{
ll p = pos[l] , q = pos[r] , kkk = 0;
if(p == q)
{
fr(i , l , r)
{
kkk = (kkk + a[i] * cnt1[p] % m + cnt2[p]) % m;
}
return kkk % m;
}
fr(i , l , R[p])
{
kkk = (kkk + a[i] * cnt1[p] % m + cnt2[p]) % m;
}
fr(i , L[q] , r)
{
kkk = (kkk + a[i] * cnt1[q] % m + cnt2[q]) % m;
}
fr(i , p + 1 , q - 1)
{
kkk = (kkk + sum[i]) % m;
}
return kkk % m;
}
inline void test1()
{
fr(i , 1 , n)
{
cout << a[i] << ' ';
}
cout << '\n';
fr(i , 1 , n)
{
cout << pos[i] << ' ';
}
cout << '\n';
fr(i , 1 , block)
{
cout << "block:" << i << ' ' << L[i] << ' ' << R[i] << '\n';
}
fr(i , 1 , block)
{
cout << sum[i] << ' ';
}
cout << '\n' << "cnt1\n";
fr(i , 1 , block)
{
cout << cnt1[i] << ' ';
}
cout << '\n' << "cnt2" << '\n';
fr(i , 1 , block)
{
cout << cnt2[i] << ' ';
}
cout << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q >> m;
fr(i , 1 , n)
{
cin >> a[i];
}
build();
while(q--)
{
cin >> opt;
if(opt == 1)
{
cin >> x >> y >> k;
update1(x , y , k);
}
else if(opt == 2)
{
cin >> x >> y >> k;
update2(x , y , k);
}
else
{
cin >> x >> y;
cout << ququ(x , y) << '\n';
}
}
return 0;
}
两份代码的唯一区别就是 0 分代码使用了 memset(cnt1 , 1 , sizeof(cnt1)); 。而 AC 代码选择了手动清空，请问一下这是为什么。
加载中...