链接
https://ac.nowcoder.com/acm/contest/923/C
题意
有 $n$ 个人，初始时都没糖果，有三种发糖操作，三种操作都是从某一个位置开始向右发到第 $n$ 个人。
从一个位置 $pos$ 开始，依次给每个人 $1$ 个糖果。
从一个位置 $pos$ 开始，依次发 $1,2,3,…n-pos+1$ 个糖果；
从一个位置 $pos$ 开始，依次发 $1,4,9,…(n-pos+1)^2$ 个糖果；
有 $m$ 轮操作，求最终每个人获得的糖果数量。
思路一
多阶差分
操作 $1$：区间加 $1$，左端加 $1$，求一次前缀和。
操作 $2$：区间加 $x$，$x$ 为当前位置与左端距离 $+1$，左端加 $1$，，求两次前缀和，第一次前缀和让区间加 $1$，第二次加上了与左端的距离。
操作 $3$：区间加 $x^2$，$x^2$ 为当前位置与左端距离 $+1$ 后的平方，左端加 $1$，求三次前缀和，第三次前缀和为等差数列和，即 $\frac{x^2}{2}+\frac{x}{2}$，考虑怎么变成 $x^2$，在开始时让左端右边一格的位置也加 $1$，求三次前缀和，$(\frac{x^2}{2}+\frac{x}{2})+(\frac{x^2}{2}-\frac{x}{2})=x^2$。
代码一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=1e9+7;
const int N=1e5+5;
LL cnt1[N],cnt2[N],cnt3[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
while(T--) {
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cnt1[i]=cnt2[i]=cnt3[i]=0;
for(int i=1;i<=m;i++) {
int o,p;cin>>o>>p;
if(o==1) ++cnt1[p];
else if(o==2) ++cnt2[p];
else if(o==3) ++cnt3[p],++cnt3[p+1];
}
for(int i=1;i<=n;i++) {
cnt3[i]=(cnt3[i-1]+cnt3[i])%MOD;
cnt2[i]=(cnt2[i-1]+cnt2[i]+cnt3[i])%MOD;
cnt1[i]=(cnt1[i-1]+cnt1[i]+cnt2[i])%MOD;
}
for(int i=1;i<=n;i++) cout<<cnt1[i]<<" \n"[i==n];
}
return 0;
}
|
思路二
我们可以对每个位置 $x$ 维护 $ax^2+bx+c$ 的系数。
操作 1：$[pos,n]$ 的 $c$ 加 $1$。
操作 2：$[pos,n]$ 的 $c$ 加 $1-pos$，$b$ 加 $1$。
操作 3：$[pos,n]$ 的 $c$ 加 $(1-pos)^2$，$b$ 加 $2-2pos$，$a$ 加 $1$。
用树状数组维护。
代码二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=1e9+7;
const int N=1e5+5;
int n;
LL a[N],b[N],c[N];
void update(LL *a,int x,LL v) {
for(int i=x;i<=n;i+=i&-i) a[i]=((a[i]+v)%MOD+MOD)%MOD;
}
LL query(LL *a,int x) {
LL ret=0;
for(int i=x;i;i-=i&-i) ret=((ret+a[i])%MOD+MOD)%MOD;
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
while(T--) {
int m;cin>>n>>m;
for(int i=1;i<=n;i++) a[i]=b[i]=c[i]=0;
for(int i=1;i<=m;i++) {
int o;LL p;cin>>o>>p;
if(o==1) {
update(c,p,1);
}
else if(o==2) {
update(c,p,1-p);
update(b,p,1);
}
else if(o==3){
update(c,p,(1-p)*(1-p));
update(b,p,2-2*p);
update(a,p,1);
}
}
for(int i=1;i<=n;i++) {
LL res=0;
res=(res+query(c,i))%MOD;
res=(res+query(b,i)*i%MOD)%MOD;
res=(res+query(a,i)*i%MOD*i%MOD)%MOD;
cout<<res<<" \n"[i==n];
}
}
return 0;
}
|