一，前缀和
1，前缀和思想
-
新定义性： 可以对需要前缀和的条件和数目进行取舍
if (...) a[i]= a[i-1] + ..
- 叠加性：在有序的数组标的前提下，二分就能取得第k大的数，注意和其他计数的结合
- 注意大数据范围
- 数学性： 求和求积运算的一切都可以实现
例一：给定一个由大写字母构成的字符串 s，请计算其中有多少个子序列 QAQ。注意，子序列不需要连续。
-
分析：
回文性质， 固定 A 的位置，找到前后有多少 Q ，乘法原理即可
找 Q 的过程就是新定义的典例
int n,ans;
string s;
int t[N];
int main()
{
cin>>s;
n= s.size();
s = ' ' + s;
for (int i = 1; i <= n; i ++ ) t[i]= t[i-1]+(s[i]=='Q');
for (int i = 2; i < n; i ++ ) if(s[i]=='A')ans+= t[i-1]*(t[n]-t[i]);
cout<<ans;
}
2，多维前缀和
容斥求法：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
叠加求法：
- 二维前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]+=f[i][j-1];//第一次
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]+=f[i-1][j];//第二次
- 三维前缀和（多维亦然）
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=l;k++)
f[i][j][k]+=f[i][j][k-1];//第一次
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=l;k++)
f[i][j][k]+=f[i][j-1][k];//第二次
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=l;k++)
f[i][j][k]+=f[i-1][j][k];//第三次
- 对非这一维的所有维度枚举殆尽！
- 这一维度的信息只和这一维度上的递推有关
- 注意顺序，保证改变的维度从小到大
拓展：
（多维超立方体求和）
给你一个长度为
2
n
2^n
2
n
的序列
a
a
a
，每个
1
≤
K
≤
2
n
−
1
1\le K\le 2^n−1
1
≤
K
≤
2
n
−
1
，找出最大的
a
i
+
a
j
a_i+a_j
a
i
+
a
j
（
i
o
r
j
i \mathbin{\mathrm{or}} j
i
o
r
j
，
0
≤
i
<
j
<
2
n
0 \le i < j < 2^n
0
≤
i
<
j
<
2
n
）并输出。
- 可以把转换：
-
求
i∣
j
⫅
K
i|j\subseteqq K
i
∣
j
⫅
K
的问题，然后取每一个小于
KK
K
的集合里最大值即可。（难点） - 考虑把每一个二进制位作为下标，取得最大值操作变成高维前缀信息（集合最小和次小）维护（每一维只有01）
-
换句话说：题目中转移的集合就是比
kk
k
小的所有二进制数
int main()
{
cin >> n ;
rep(i,0,(1<<n)-1) cin >> f[i].x;
rep(i,0,n-1)
{
rep(j,0,(1<<n)-1) if(j&(1<<i))
{
int m1 = f[j].x;
int m2 = f[j].y;
int m3 = f[j^(1<<i)].x;
int m4 = f[j^(1<<i)].y;
if(m3>=m1) m2 = m1 ,m1 = m3;
else if(m3>m2) m2 = m3;
else if(m4>m2) m2= m4;
f[j].x = m1;
f[j].y = m2;
}
}
rep(i,1,(1<<n)-1)
{
ans = max(ans,f[i].x+f[i].y);
cout << ans << endl;
}
return 0;
}
二，差分思想
- 作用持续： 单点修改的目的是在往后的数据上造成一个扰动，这个扰动只要没用被新的单点修改扰动抵消，在前缀（…）这种具有积累效应的运算上就会持续存在
- 作用形式：差分数组，懒标记，异或运算
具体而言：
1，需要开始去区间操做的地方在差分数组上打上（作用记号），作用形式不限，叠加效应不能忽视
2，注销某一种操作是，在差分数组上打上（注销记号），注销这种操作
例一：（可能是个模拟？或者是降维）
差分套差分，跳水的影响具有周期波动和规律性，第一层差分表示影响范围，第二层表示具体影响度，初始均为0
delta 人为处理偏移量，在数组下标下处理横坐标负数
#define rep(i,j,k) for(int i= j;i<=k;i++)
int c[N],s[N];
int n,m;
signed main()
{
int delta = 1000000;
scanf("%d%d",&m,&n);
while (m--)
{
int v,x;
scanf ("%d%d",&v,&x);
c[x- 3*v+1 +delta]++;
c[x- 2*v+1 +delta]-= 2;
c[x +1 +delta]+= 2;
c[x+ 2*v+1 +delta]-= 2;
c[x+ 3*v+1 +delta]++;
}
rep(i,0,delta+n) c[i]+= c[i-1] , s[i]= s[i-1]+c[i];
rep(i,delta+1,delta+n)printf("%d ",s[i]);
}